for-in evaluation order

Wes Garland wes at
Mon Dec 27 09:54:33 PST 2010

On Mon, Dec 27, 2010 at 8:04 AM, Dmitry A. Soshnikov <
dmitry.soshnikov at> wrote:

> Can you also show a memory representation (at lower level) of "dense" and
> "sparse" (?) data. It will help to understand the advantages of choosing the
> needed order by implementers. It's not required to show it right now, but,
> if possible -- when you'll have a time to show it.

I haven't looked at this code in SpiderMonkey for a very long time, but
IIRC, here are the highlights:

   - All ECMAScript values are stored in a type called "jsval", which is
   basically a tagged variant type
   - jsvals can represent integers, doubles (firefox 4 - older stores double
   pointers), string pointers, object pointers, and bools
   - Firefox 4 uses 64-bit jsvals and a bit more specialization information
   in the tags; older uses 32-bit jsvals
   - Key fact: regular arrays are basically just objects, but dense arrays
   have a highly specialized implementation as of firefox 3
   - dense arrays are arrays with few holes and numeric indices
   - dense arrays are represented internally essentially as C arrays of
   jsval with matching indices. So a lookup is very very cheap. ("matching
   indices" might be a slight lie, I think there might be an offset for arrays
   big leading holes etc)
   - regular object properties are stored in "slots", which are really just
   elements in a C array of jsvals
   - there is a map which allows us to look up which slot a property is
   stored in
   - this map (and the slots) are populated in first-write (declaration)
   - I believe this implementation is the origin of the defacto enumeration
   order relied on by the web; the enumerator simply traverses the map in
   storage order

So you see, looking up an index in a dense array is really cheap - you take
the value of the index, convert it to a C int (usually just a bit shift),
multiply it by the size of the jsval, add that to the pointer to the start
of the storage, and voila - you have a pointer to the jsval which represents
the value stored.  You do not have the overhead of traversing the map to
determine the offset, nor the overhead of *storing* the map.

Andreas mentioned the possibility of an object representation which has both
a map/slots and a dense array component - this is interesting, as it makes
representing user-defined array-like objects more efficient --- I believe
that adding a length property in the current implementation forces a
non-dense representation of the array.

I think Mark's suggestion here is very sensible.  My gut tells me that it
has a low probability of breaking the web, yet it offers room for
implementers to provide a fast path for numeric object indices while
offering an opportunity to codify standard practice.


Wesley W. Garland
Director, Product Development
PageMail, Inc.
+1 613 542 2787 x 102
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the es-discuss mailing list