On Mon, Dec 27, 2010 at 8:04 AM, Dmitry A. Soshnikov <
dmitry.soshni...@gmail.com> 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)
order
- 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.
Wes
--
Wesley W. Garland
Director, Product Development
PageMail, Inc.
+1 613 542 2787 x 102
_______________________________________________
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
