689745 - consider specializing 32-bit slot representation when all property values are non-doubles

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

While 64-bit fatvals make sense for stack values and parameters, they are kindof lame for object properties on 32-bit systems since you only need the full 64 bits when the value is a double.  With the growing importance of 32-bit ARM, it seems like we may need to care about 32-bit for a long time so we should consider not wasting half our slots memory (which about:memory shows is significant).

Heap doubles (what v8 does; what we used to do) are annoying and you die on numeric kernels that involve array/object access.

A less lame alternative is to specialize an object's slot representation to be 32-bits when it doesn't actually contain any doubles.  Then, if an object gets its first double, the slots are fattened up to standard 64-bit jsvals.  Thus, js::Value would be unchanged but there would be a new js::NonDoubleValue and the type of obj->slots/elements would be union { Value *; NonDoubleValue * };

I haven't thought through this in detail, but at first glance it seems like the doesn't-contain-doubles property can be tied into type inference as a TypeObjectFlag and handled in the usual style of TI.

Even more generally we could consider specializing object slots representation to only ints, objects, etc.  To wit, skimming svn logs, it seems like v8 is landing patches to support a new "SmiArray" which I assume is an array that only contains ints.

I don't have any concrete plans, I just wanted to collect discussion and put the idea on the map.

Comment 1

[Brian Hackett [Laid off!]]

The main thing I'd want to avoid here is 31 bit integers.  So rather than think about double vs. non-double, how about 'known non-double type' vs. 'unknown or double type'.

What I think could work (have thought some about this, but vaguely) is an idea Brendan had to embed information about property types into the object's shape.  Not necessarily the type tag itself, but enough information that combined with the payload the value's type could be determined.  i.e. you would have shapes for properties whose type is 'object or null', or 'object or undefined', but not 'int or undefined'.  An object can mix together thin and fat properties, but indexes must either all be thin or all be fat.

The main thing to watch out for would be shape thrashing due to changes in payload types.  And, yeah, bits on the TypeSet for properties and TypeObjectFlag for indexed state can track changes here dynamically and keep JIT accesses really fast.

Comment 2

[Luke Wagner [:luke]]

(In reply to Brian Hackett from comment #1)
> What I think could work (have thought some about this, but vaguely) is an
> idea Brendan had to embed information about property types into the object's
> shape.

Hmm, good point.  That was the original plan for fatvals but it got bumped due to time and...

> The main thing to watch out for would be shape thrashing due to changes in
> payload types.

...fear of this.  With TypeObjects, it seems like we could do smart things, though.

Comment 3

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

I really hope we do something like this.

Rather than storing the slot number in a shape, we could just store an offset. That way, we could mix thin and fat stuff in a single object (which I think Brian alluded to). The GC marking code would get a bit more complex, but we'd also be touching less memory, so hopefully it would balance out.

The reason I really like this idea is because it gets us closer to being able to do concurrent GC (where the GC runs at the same time as JS code). As Luke pointed out a long time ago, we can't atomically write a 64-bit value on 32-bit architectures efficiently. But if pointers usually fit into 32-bits, then this isn't a problem. There are still all sorts of other barriers to concurrent GC that would have to be overcome, but this is one of the most fundamental ones.

Comment 4

[Nicholas Nethercote [inactive]]

This reminds me of bug 566767.

Comment 5

[Luke Wagner [:luke]]

Thinking about this a bit more, there is another attractive strategy (this time pre-vetted by Brian) that will hopefully use TI to address problems mentioned in 566767:

TI already tracks and tells us "this array is packed and contains a single type of element".  So, when it says that for some non-double type, we can just store the elements as unboxed 32-bit elements.  The jit code and VM thus know how to interpret obj->elements by looking at obj->typeObject.  For hot array functions, where v8 currently wins b/c they copy half as many bytes (can't find any bugs atm, but I know several have been filed), this would put us back on equal footing.

The big remaining question is: what happens when a typed-packed-array gets a second type?  If we just change the dense element's typeset in the TypeObject, then jit/v code will expect the slots to be normal boxed 64-bit values so we'd need to find *every* object with the given TypeObject and box/inflate its elements.  That would be bad.  Instead, we can change the type specificity lattice for elements by adding a new less-specific type:

  maybe-boxed < boxed < packed-boxed < packed-typed
  ^^^^^^^^^^^

Next, every object has in its flags (or in its shape's flags) a bit indicating "unboxed" or not.  If a type object is "boxed" or greater on the lattice, then this bit never needs to be tested (that is, no different than right now).  When the type is maybe-boxed, a test is necessary to determine how to extract the element.  The whole point is that when a single object with a given TypeObject takes on a second type, only that object's elements need to be inflated: the TypeObject changes the element's typeset to be maybe-boxed and thus all other objects (still with the "unboxed" bit set) remain valid for access by jit/vm code.  This hopefully mitigates the risk of big expensive mis-speculations.

My remaining questions:
 - how much of our slot use is elements of packed-typed arrays with a single known type (or could be, with bug 586842) and thus how much memory would this save?
 - how often would a packed-typed TypeObject degrade to maybe-boxed?
 - how much faster would jit array access get?  (since we already avoid storing type tags when the target property's type is known, I think the only win would be cache effects?)

Comment 8

[Luke Wagner [:luke]]

I think this was all subsumed by the unboxed object optimization.