528399 - write a pldi paper on the property tree

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Comment 1

[Andreas Gal :gal]

Its that time of the year again. PLDI is upon us. The deadline is Friday next week. The suggested topic is our property tree. We describe its basic mechanism and function, use the tons of probes we have to measure its efficiency and general web and benchmark behavior wrt to objects and properties (gregor's part). We can also talk about recent additions like the middle delete business. The mechanism hasn't been described academically afaict and hence hasn't been evaluated academically, so there should be a decent space for this paper. Worst case we can a nice documentation of the property tree out of it. I added a couple of people who I think are interested to help. Please feel free to opt out if you are busy or not interested. I will propose an abstract in the bug. It has to be uploaded tomorrow.

Comment 2

[Andreas Gal :gal]

Marking the bug confidential since PLDI is double blind and we don't want to be found on google (yeah, lame, I know). We will open this up after the review cycle.

Comment 3

[Nicholas Nethercote [inactive]]

I know nothing about the property tree, but a lot about academic papers in general.  I'm happy to do lots of reviewing.

Re anonymity, unless we take the step of avoiding mentioning Mozilla, TraceMonkey, etc by name it'll be very clear who the authors are.  I've seen people do that, eg. call their system "X" in the anonymous submission.

Comment 4

[Nicholas Nethercote [inactive]]

Not that it's necessarily worth going to those lengths -- some papers are just hard to anonymize.

Comment 5

[Andreas Gal :gal]

Yeah, we did that last time too. And its of course completely pointless. If you read the paper as a reviewer and didn't know that JS + Tracing == Mozilla then you must have lived behind the moon. But lets follow their rules.

Comment 6

[Andreas Gal :gal]

Ok here is the proposed abstract.

Property Trees: An Efficient Object Property Lookup Mechanism for JavaScript

JavaScript is a dynamically typed programming language widely used in browser-based web applications. JavaScript provides programmers with a simple expandable set of properties as its basic object type, and provides a prototype-based inheritance mechanism to compose complex object hierarchies from this basic object type. The lack of static typing of objects and the generality of prototype-based inheritance create a challenge for efficient execution of JavaScript code. We present a mechanism that allows dynamic inference of object shapes at runtime using a property tree. We show that the object shape information obtained through building and maintaining the property tree can be used to speed up property access in a JavaScript virtual machine by up to 400% for certain property access-heavy benchmarks.

I went back to JavaScript in the title. Its less general, but JS is hot right now, and it allows us including prototype-based inheritance into the mix directly in the abstract. Comments?

Comment 7

[Andreas Gal :gal]

Outline (taken from last year's draft)

\section{Introduction}

% what we do and why, in a few words

\section{JavaScript}

% whats javascript and why its not irrelevant

\subsection{Objects in JavaScript}

% semi formal description, prototype chain (Luke?)

\subsection{Scopes as Objects}

% semi formal description of the complexities of
% objects being used as scopes / call objects
% parent relation, proto chain mix, O^2 lookup and such

\section{Na\"ive Property Access}

% show 3-4 different ways properties can be accessed using prop cache hit cases
% as examples (the different ways we can hit), show why its expensive
% argue size, argue speed

\section{Property Tree}

% ``to address size issue, we use a property tree'', explain property tree,
steal the fslot discussion from the code (that huge comment), fslot/dslot

\section{Property Cache}

% now performance, show how the cache can be used in various ways to do
% direct access
% multithreading issues

\section{Dynamic Compilation}

% how does tracing work, embedding prop cache into native code directly

\section{Related Work}

\section{Benchmarks}

% we need a ton of numbers, can borrow from the prop cache bug
% students can make pretty graphs, but we need the raw data
                                     
\section{Conclusions}

\section{Future Work}

Comment 8

[David Anderson [:dvander] - inactive, e-mail if emergency]

"from this basic object type" reads a little awkward since the phrase is repeated, maybe the second instance could go

Comment 9

[David Mandelin [:dmandelin]]

(In reply to comment #6)
> Ok here is the proposed abstract.

By the way, do they evaluate these initial abstracts, or is it just an announcement to them that you are working on a paper? If the latter, I suppose it doesn't have to perfect. But I started half of a detailed readthrough, so I might as well finish. :-)
 
> Property Trees: An Efficient Object Property Lookup Mechanism for JavaScript

Random alternative *if* you want the language-general version:

Property Trees: An Efficient Property Access Implementation for Dynamic Language Objects

> JavaScript is a dynamically typed programming language widely used in
> browser-based web applications. 

Sounds good.

> JavaScript provides programmers with a simple
> expandable set of properties as its basic object type, and provides a
> prototype-based inheritance mechanism to compose complex object hierarchies
> from this basic object type. 

This sentence is really long. One solution is splitting up the two main parts (whatever grammarians call 'em). But I think it could also be tweaked a bit more to bring out the key points, which I think are something like:

- The set of properties can change while running
- Objects have a prototypes and lookups must search them (and the prototype can also change while running)

Those presumably are what make this problem hard.

> The lack of static typing of objects and the
> generality of prototype-based inheritance create a challenge for efficient
> execution of JavaScript code. 

OK, here is what I was asking for. So I would suggest rewriting the previous sentence and this one to state the true problem in a sharp way: we want efficient object property access mechanisms for a language where objects have a dynamic associative array of properties and a prototype chain of objects.

> We present a mechanism that allows dynamic
> inference of object shapes at runtime using a property tree. 

Good, except that you haven't defined shape yet. And, in fact, I think the idea of shape is perhaps an important part of the solution and deserves more emphasis as a really cool idea in its own right. So you have 2 big ideas here: (a) introducing the concept of shape as a way to work with these dynamic objects, and (b) implementing inferring and using shapes.

> We show that the
> object shape information obtained through building and maintaining the property
> tree can be used to speed up property access in a JavaScript virtual machine by
> up to 400% for certain property access-heavy benchmarks.

Perfect.

> I went back to JavaScript in the title. Its less general, but JS is hot right
> now, and it allows us including prototype-based inheritance into the mix
> directly in the abstract.

I'm bad at questions like this, because I don't have the belief that papers are only good if they cover whole classes of languages. I wonder if there is a middle path where you can make it clear that this is applicable beyond JS but is mostly presented in terms of JS.

Comment 10

[Luke Wagner [:luke]]

On the subject of "shape" in the abstract, it is worth keeping in mind that there is a previous meaning of "shape" understood by the PLDI audience different than what we mean (http://en.wikipedia.org/wiki/Shape_analysis_%28software%29).

Comment 11

[Jeff Walden [:Waldo]]

  We present a mechanism that allows dynamic inference of object shapes at
  runtime using a property tree. We show that the object shape information
  obtained through building and maintaining the property tree can be used to
  speed up property access in a JavaScript virtual machine by up to 400% for
  certain property access-heavy benchmarks.

"shape" isn't defined yet (and shouldn't be), which makes comment 10 even more vexing.  I think this captures the flavor of "shape" reasonably well without needing to use the specific term:

  We present a mechanism that efficiently records the internal structuring of
  storage for properties in an object.  We show that using this information we
  can speed up property accesses and common sequences of property additions by
  up to 400% in some property access benchmarks.

Hope that helps some, I'm still not quite happy with it.

Comment 12

[David Mandelin [:dmandelin]]

(In reply to comment #11)
>   We present a mechanism that allows dynamic inference of object shapes at
>   runtime using a property tree. We show that the object shape information
>   obtained through building and maintaining the property tree can be used to
>   speed up property access in a JavaScript virtual machine by up to 400% for
>   certain property access-heavy benchmarks.
> 
> "shape" isn't defined yet (and shouldn't be), which makes comment 10 even more
> vexing.  I think this captures the flavor of "shape" reasonably well without
> needing to use the specific term:
> 
>   We present a mechanism that efficiently records the internal structuring of
>   storage for properties in an object.  We show that using this information we
>   can speed up property accesses and common sequences of property additions by
>   up to 400% in some property access benchmarks.
> 
> Hope that helps some, I'm still not quite happy with it.

Hmmmm. Not confusing shape analysis people is a good thing. But it seems nice to have a snappy term for the concept. Carefully defining "shape" is one option. Is "shape" the standard term in the existing literature (if any)? What about "pseudoclass" or some other "x-class" term?

Comment 13

[Luke Wagner [:luke]]

(In reply to comment #12)
> Is "shape" the standard term in the existing literature (if any)? What
> about "pseudoclass" or some other "x-class" term?

At least with program analysis folk; e.g. Section 2.6 of Principles of Program Analysis.

Comment 14

[Jeff Walden [:Waldo]]

Nothing against snappy terms, it just seems to me that there isn't space to introduce one whose basic meaning isn't blindingly obvious in the abstract.  Defining and using shape in the paper (on the assumption that we won't find a notably better term) itself seems great.

Comment 15

[Brendan Eich [:brendan]]

From jsinterp.h:

/*
 * Property cache with structurally typed capabilities for invalidation, for
 * polymorphic callsite method/get/set speedups.  For details, see
 * <https://developer.mozilla.org/en/SpiderMonkey/Internals/Property_cache>.
 */

I wrote the first sentence, it is a mouthful. Jorendorff did most of the work at MDC documenting it.

The structurally typed capabilities (value capabilities, not obj-cap reference capabilities) are the 24-bit shape numbers, in one case with 8 bits of (scope, proto) chain coordinates appended.

So the precedent is structural types, but prototype and scope chaining (with some tight restrictions on scope chain membership and aliasing) are novel to JS and this code, AFAIK.

Pierce's TAPL covers structural types thoroughly.

Cc'ing Dave Herman who knows all this stuff better than I do.

/be

Comment 16

[Jeff Walden [:Waldo]]

Another possibility:

"We present a mechanism to efficiently infer structural types for objects with time-varying sets of properties.  This mechanism can speed up property additions and accesses by up to 400% in some property access benchmarks."

Comment 17

[Andreas Gal :gal]

Property Trees: An Efficient Object Property Lookup Mechanism for Dynamic Languages

JavaScript is a dynamically typed programming language widely used in
browser-based web applications. As with many dynamic languages, JavaScript objects are in essence associate arrays and lack static typing. Object properties can be added and removed at runtime and JavaScript provides a prototype-based inheritance mechanism to compose complex object hierarchies.
As a result, property lookups in JavaScript imply a search along this prototype chain and can be expensive. We present a mechanism that allows to dynamically infer structural types for objects using a property tree. We show that using this inferred type information we can speed up property accesses and common sequences of property additions by up to 400% in some property access benchmarks.

Comment 18

[Jeff Walden [:Waldo]]

Property Trees: An Efficient Object Property Lookup Mechanism for Dynamic
Languages

JavaScript is a dynamically typed programming language widely used in
browser-based web applications. As with many dynamic languages, JavaScript
objects are essentially associative arrays that lack static typing; object
properties can be added and removed at runtime.  JavaScript also provides a
prototype-based inheritance mechanism to create complex object hierarchies.
As a result, property lookups in JavaScript imply a potentially slow search 
of the objects along the prototype chain. We present Property Trees, an efficient mechanism to dynamically infer structural types for objects. We show
that, using this inferred type information, we can speed up property accesses
and common sequences of property additions by up to 400% in some benchmarks.

Comment 19

[David Anderson [:dvander] - inactive, e-mail if emergency]

"objects are essentially associative arrays" 
---------------^ I try to avoid "in essence" or "essentially". It sounds hand-wavy. But I can't offer an alternative other than dropping it or "based on".

- "; object properties can be added and removed at runtime."
+ ". Object layout is dynamic and properties can be added and removed at runtime."


- "imply a potentially slow search of the objects along the prototype chain"
+ "imply a potentially slow search along each of the objects on a given prototype chain."
or
+ "imply a potentially slow search of each object along the prototype chain"

Comment 20

[Andreas Gal :gal]

Ok, here is the current version I uploaded:

JavaScript is a dynamically typed programming language widely used in browser-based web applications. As with many dynamic languages, JavaScript objects are essentially associative arrays that lack static typing; object properties can be added and removed at runtime.  JavaScript also provides a prototype-based inheritance mechanism to create complex object hierarchies. As a result, property lookups in JavaScript imply a potentially slow search of the objects along the prototype chain. We present property trees as an efficient technique to dynamically infer structural types for objects. We show that, using this inferred type information, we can speed up property accesses
and common sequences of property additions by up to 400% in some benchmarks.

Comment 21

[Roy Frostig :froystig]

Attachment: procache.stats on facebook

I #defined JS_PROPERTY_CACHE_METERING 1 in jsinterp.h and fiddled around on Facebook for half an hour.  This is the resulting propcache.stats log.

Running regular optimized m-c trunk build from earlier today, on Linux.

I kept it to one tab and avoided any fancy browser features so as to prevent noise coming from the chrome JS end.  Also, both chrome and content JIT were off for this.

I'll do GMail next, maybe some other Google apps (docs, reader).  Any other suggestions?

Also, feel free to give feedback on whether this log is sufficiently long (for one website), or if I should be wasting more time wandering about the interwebs.

Comment 22

[Roy Frostig :froystig]

Comment on attachment 412372 [details]
procache.stats on facebook

Making the attachment text/plain.  Apologies for bugspam.

Comment 23

[Roy Frostig :froystig]

Attachment: summarize-stats.py

Python script that reads in a propcache.stats file, parses it, and outputs a summary of the tallies and hit rates across reported propcache purges.

Here's what the script reports on the previously posted Facebook experiment:


    feature                    mean                  stddev
-----------------------------------------------------------
      fills            29656.029126            28299.459626
    nofills             1738.174757             1737.092104
    rofills                0.184466                0.587038
   disfills             3663.097087             4741.542583
   oddfills                0.000000                0.000000
   modfills             6688.883495             5237.324927
 brandfills              538.495146              413.940427
   noprotos               29.621359               28.550455
 longchains                0.000000                0.000000
   recycles            26418.854369            27857.624172
 pcrecycles              926.883495              798.624926
      tests           282095.941748           257364.162091
     pchits           225758.883495           224089.018366
protopchits            23501.815534            36179.385765
   initests             8321.456311            14482.360053
  inipchits             6410.689320            14331.094886
inipcmisses             1910.766990             2465.097986
   settests             7991.475728             7435.200926
  addpchits             1455.805825             1996.777968
  setpchits             4392.378641             4213.313778
setpcmisses               39.893204               78.686784
slotchanges                0.000000                0.000000
  setmisses             2135.757282             2298.239721
   idmisses            38342.621359            33401.910693
   komisses             1147.446602             1714.129164
   vcmisses               17.271845               34.965779
     misses            39507.339806            34230.805398
    flushes                0.990291                0.098053
   pcpurges              204.184466              624.091647

mean hit rates: pc 81.728888% (proto 7.752616%), set 75.683756%, ini 63.396329%, full 86.337846%
stddev of hit rates: pc 2.104800% (proto 0.571883%), set 2.951817%, ini 14.773722%, full 1.621273%

Comment 24

[Roy Frostig :froystig]

Attachment: propcache.stats on gmail

Here's GMail.  Summary is:

    feature                    mean                  stddev
-----------------------------------------------------------
      fills            76370.603774            62642.071813
    nofills             4446.830189             3850.183832
    rofills                0.000000                0.000000
   disfills              521.886792             2057.714272
   oddfills                0.000000                0.000000
   modfills            27496.528302            21893.744248
 brandfills              447.830189              442.621766
   noprotos               65.000000              108.902068
 longchains                0.000000                0.000000
   recycles            72691.679245            62189.023740
 pcrecycles             8398.452830             7173.568170
      tests           468295.226415           392930.665289
     pchits           365211.283019           312651.430646
protopchits            20578.679245            19688.668697
   initests              685.924528              870.989740
  inipchits              354.056604              453.976411
inipcmisses              331.867925              635.663968
   settests            35860.698113            29997.638448
  addpchits            18519.811321            16341.610545
  setpchits            10636.301887             9801.018720
setpcmisses               12.792453               24.797564
slotchanges                0.000000                0.000000
  setmisses             6572.471698             5583.993400
   idmisses            68080.528302            56568.394201
   komisses            12625.339623             9938.181167
   vcmisses              970.226415             1550.751183
     misses            81676.094340            66650.050605
    flushes                1.018868                0.136059
   pcpurges             2096.679245             2093.282723

mean hit rates: pc 76.826679% (proto 4.443869%), set 80.365728%, ini 43.593010%, full 81.493585%
stddev of hit rates: pc 1.905998% (proto 0.993435%), set 3.245352%, ini 10.892412%, full 1.558320%

Comment 25

[Roy Frostig :froystig]

Attachment: propcache.stats on gmail

Posted the wrong GMail log above --- what I had up had the first two purge stats cut off (so the summary is a bit off as well).  Here's the right one.

Google Calendar is the next experiment.  I'll post all the summaries together at the end instead of sticking them in each attached log's comment.

Comment 26

[Roy Frostig :froystig]

Attachment: propcache.stats on gcalendar

Google Calendar.

Comment 27

[Nicholas Nethercote [inactive]]

All the above abstracts seem pretty good to me, as a starting point.

(In reply to comment #9)
>
> By the way, do they evaluate these initial abstracts, or is it just an
> announcement to them that you are working on a paper? If the latter, I suppose
> it doesn't have to perfect.

It's the latter.

(In reply to comment #18)
> Property Trees: An Efficient Object Property Lookup Mechanism for Dynamic
> Languages

"Property Trees: Fast Object Property Lookup for Dynamic Languages" is snappier.

What are the contributions of the paper?  I strongly prefer papers that make them explicit in the introduction.

If you haven't seen it, Simon Peyton Jones' "How to write a good research paper" slideset is excellent, as are the other presentations here:
http://research.microsoft.com/en-us/um/people/simonpj/papers/giving-a-talk/giving-a-talk.htm

Comment 28

[Gregor Wagner [:gwagner]]

Attachment: chain length example from DLS keynote talk

I started with something similar to slide 27 from 
http://www.cs.purdue.edu/homes/jv/talks/dls09.pdf

My data for gmail for example look like:
mean proto-lookup depth 0.429607, std. deviation 1.15647, max 11
        [     0]:  5482072 *******
        [     1]:   671407 ******
        [     2]:   132078 ******
        [     3]:   176372 ******
        [     4]:   169635 ******
        [     5]:    56107 *****
        [     6]:    33348 *****
        [     7]:    18376 *****
        [     8]:    10310 *****
        [     9]:     6687 ****
        [    10]+      779 ***

Comment 29

[Roy Frostig :froystig]

Attachment: propcache.stats on greader

Google Reader.

Comment 30

[Roy Frostig :froystig]

Attachment: propcache.stats on bubblemark

BubbleMark (http://bubblemark.com/dhtml.htm) with bubble count set to 32.

Comment 31

[Boris Zbarsky [:bzbarsky]]

What about bubblemark at 128?  As I recall that currently blows out the propcache...

Comment 32

[Gregor Wagner [:gwagner]]

I started a Google Doc spreadsheet for the lookup chain length:

http://spreadsheets.google.com/ccc?key=0Ap0dQpNVB5kGdG5XQ19icDZmSC1kNUJGa3JpbV8zNFE&hl=en

Comment 33

[Brendan Eich [:brendan]]

(In reply to comment #30)
> Created an attachment (id=412487) [details]
> propcache.stats on bubblemark
> 
> BubbleMark (http://bubblemark.com/dhtml.htm) with bubble count set to 32.

We should remeasure next week with a proper fix for bug 497789 (I'll attach one on Monday).

/be

Comment 34

[Gregor Wagner [:gwagner]]

Attachment: prototype test case

I was playing around with a test case to measure prototype chain lookup time.
For small changes in the code (variable declarations, array lookup...) I noticed big performance differences. (+-30%). I just want to make sure I measure the prototype chain walk and not some other influence.  
The results are in the second sheet of my GDocs spreadsheet.

Comment 35

[Andreas Gal :gal]

The paper repository is setup:

http://hg.mozilla.org//users/agal_mozilla.com/papers

directory "pldi-2010"

Comment 36

[Jeff Walden [:Waldo]]

(In reply to comment #2)
> Marking the bug confidential since PLDI is double blind and we don't want to be
> found on google (yeah, lame, I know). We will open this up after the review
> cycle.

http://hg.mozilla.org/users/agal_mozilla.com/papers quite publicly spills the beans unless it's possible for IT to make this restricted somehow, but I say it's not worth the effort to maintain a pretense of anonymity.  How about we unhide and quit pretending this bug's privacy means anything?  ;-)

Also:

https://bugzilla.mozilla.org/robots.txt
http://hg.mozilla.org/robots.txt

sez spider-paranoid reasoning is flawed anyway.  :-)

Comment 37

[Andreas Gal :gal]

Yeah I guess Waldo is right. What the hell. Lets be rebels :)

Unhiding.

Comment 38

[Andreas Gal :gal]

7 pages of content in the paper. Call for editing of the existing text. We have about 16 hours left, so please have at it. I think the property tree part's English is too dense and needs to be uncompressed up a bit. All sorts of edits are welcome. I will write the intro now, and I am hoping that Gregor and Roy will do a lot of work on the benchmarks section. We need a bunch of graphs.

Comment 39

[Andreas Gal :gal]

I did a couple simplifications to the description:

* I claim we always teleport and embed the object identity where we find the property. Is this correct? It seems only the JIT really does this, not the interpreter.

* I dropped the method guarantee (joined function objects) because its missing in the formal language introduction. Should we add it?

Comment 40

[Roy Frostig :froystig]

Attachment: propcache.stats experiment summaries

I promised earlier in the week to have summaries for all of the propcache.stats experiments in one place, so here they are.  Let me know if something looks funky, as I might be making false assumptions about what the tallies in the logs mean.  In these, I am subtracting from the counts in every flush the corresponding counts in previous flush, so the stats for average, stddev, min, max are over deltas.  I'm almost certain this is the right way to read these.  (Brendan?)

I'll be in the Mtn. View office tomorrow as soon as I can be.  Email me or post in bug what kind of graphs you'd like to see if you have ideas before then.

Comment 41

[Graydon Hoare :graydon]

I'm kinda nervous that this paper goes into way too much fussy detail about spidermonkey-isms or at best js-isms. It's presented (initially) as a report on the property-tree (which is not much different in theory than a hidden-class system) but then goes off on this long elaboration of secondary systems (property cache, shapes, branded scopes). It seems somewhat off-track.

Comment 42

[Brendan Eich [:brendan]]

(In reply to comment #39)
> I did a couple simplifications to the description:
> 
> * I claim we always teleport and embed the object identity where we find the
> property. Is this correct?

For function-valued properties of branded scopes, cached when first called, yes.

Lately (modulo outstanding bug 529837), also for joined function objects stored as methods (JSOP_SETMETHOD, JSOP_INITMETHOD fed from JSOP_LAMBDA with a null closure -- null upvar set -- as its immediate), also.

> It seems only the JIT really does this, not the interpreter.

Any PCVAL_IS_OBJECT entry seems to match what you are describing here.

> * I dropped the method guarantee (joined function objects) because its missing
> in the formal language introduction. Should we add it?

This could be added for sure -- by the deadline, or could it come after?

/be

Comment 43

[Roy Frostig :froystig]

Attachment: propcache.stats experiment summaries

Ran a few more experiments (GDocs, 280slides et al) to have a complete overlap with Gregor's set of test subjects.

Comment 44

[Andreas Gal :gal]

We just submitted the paper to PLDI. bz and roy are proof reading. I will refresh the upload in a bit. Deadline is midnight.

Comment 45

[Andreas Gal :gal]

Attachment: Final version of the paper as submitted (with author list, the original submission was double blind).

Comment 46

[Andreas Gal :gal]

Fixed. We can re-open for the camera ready version if it gets accepted :)

Comment 47

[Brendan Eich [:brendan]]

(In reply to comment #42)
> > * I claim we always teleport and embed the object identity where we find the
> > property. Is this correct?
> > It seems only the JIT really does this, not the interpreter.
> 
> Any PCVAL_IS_OBJECT entry seems to match what you are describing here.

The exact issue Andreas raised was "teleporting" as in putting the target object in the cache entry's value directly, akin to burning the object in on-trace as an immediate (constant object pointer). But this would bloat the cache entry size from 4 to 5 words, making indexing into the direct-mapped cache more costly.

So the cache stays smaller at the price of js_FullTestPropertyCache walking over and up the scope and proto chain links to traverse, encoded in the low 2 nybbles of JSPropCacheEntry::vcap.

This is too detailed to get into in the paper, and it looks like you guys wisely left it out. Teleportation all around!

/be

Comment 48

[Brendan Eich [:brendan]]

I mailed this out but should have stuck it here:

Sorry I was afk so much yesterday, sick wife and kids (that fun continued today :-/). Here are some things I noticed that need fixing:

3.4: Are N (nodes in tree) and P (properties in scopes) defined before used? Looks like not; later N=beta*P but there are no initial unrelated definitions. Could define as the jsscope.h comment does, or hoist the beta-based relation and talk about compression via sharing nodes in the tree earlier.

"binary tree" is wrong -- the tree is n-ary, and L=2 comes from the leftmost-child/right-sibling linkage.

4.1: Why not define "slot" as the "array index of the property value" to avoid confusion between property, property value, and array index of the property value.

4.4: "In case of a sealed scope, the new cached access information instructs the VM to silently ignore the property set, as dictated by the language specification." No, sealed scope throws read-only error on set/change/clear.

4.5: Shadowing logic is misstated: the write barrier does not check every time a property is set, only for those sets targeting objects that are on prototype or scope chains; and purging does not walk and reshape every older prototype or scope object -- instead we find the first prototype object that has a property of the same id that is being set (and therefore about to be shadowed) and reshape *that* object, breaking from the loop or loops (if walking up scope and proto chains).

4.6: Branding section lies: we brand on first call to a function-valued property, not on assignment.

4.8: "... so the property cache (and the just-in-time compiler code cache) are emptied" -- s/are/is/ -- or else re-word to avoid passive voice and is/are perplex: "so we purge the property cache (and the ... code cache)."

"Just as Self V8 does not use unique shapes ..." -- s/as Self/as in Self's implementation,/ -- note comma is needed.

"... existing work has suggested to constraint dynamic behavior ..." s/to constraint/constraining/

6: "2^12 property cache slots" -- s/slots/entries/ to avoid value slot confusion.

It looks like "foreshadowing" is never defined. It is also misused to mean a consequence of starting all empty objects with shape 0, which implies switching to directly-referenced object identity instead of shape as the half of the key used when checking for grand-proto or other "vcap tag >= 2" cases. This makes such cases fill and miss constantly when the objects in question have the same shape but different identities. There may be no foreshadowing along any of their deep proto chains, however -- but we pessimize by switching to identity keys.

This will be fixed very soon (bug 497789). We can update the paper then.

Another thing the paper fails to note, in this light, is the difference between (1) a direct hit and a first-level prototype hit, where no intervening object can hold a foreshadowing property along one path from one of two same-shaped objects; and (2) the grand-proto and equivalent or higher cases (scope skip 1, proto skip 1, etc.) where such foreshadowing can occur.

The fix coming in bug 497789 gives each empty scope a shape that depends on its prototype chain. Thanks to jorendorff's work introducing JSEmptyScope, we're very close now. The consequence will be moving the property tree from the JSRuntime into each JSEmptyScope, however! Still a runtime-wide resource, just split up to make distinct nodes and therefore shapes, for what are today the same node and shape shared among two paths in the tree by objects with different (and foreshadowing-capable) prototype chains.

/be