shapes and insertion order

[David Herman]

IIUC, we give objects different shapes if they have the same properties but different insertion order. This has kind of bothered my subconscious for a while, and I think I understand why now: I suspect a lot of JS code actually isn't sensitive to insertion order. I wanted to ask here: would it be a) possible b) useful to represent insertion order as a separate piece of meta-data, to cut down on the number of shapes and stop distinguishing superficially different uses of a type?

Rough sketch of one possible approach: a Shape stores the n properties in alphabetical order, or better in order by JSAtom address, regardless of insertion order. Then you have a separate OrderMap data structure, that has n slots, each with an index into the Shape. Each instance of the object would have a pointer to a Shape and a pointer to an OrderMap.

Maybe it's just a non-starter to have an additional pointer slot in every object. Maybe you can aggressively memoize OrderMaps, since they aren't actually tied to a specific Shape. I.e., you could reuse OrderMaps between all Shapes of size n. And then maybe you could store OrderMap pointers in a smaller number of bits, if there's room to shove that in some free space somewhere else in the object representation.

I'm sure I'm too far from how engines work and this is probably less than half-baked. But it just seemed to me like the for-in enumeration order is not conceptually a part of the "class" of a JS object, and since it's so easy to have multiple code paths that accidentally insert properties in different orders, it seems too easy to accidentally have a collection of different shapes for objects that are actually all part of the same conceptual "class." I find this happens in my code all the time, where I have conditionals like:

function C(...) {
if (...) {
this.foo = ...
this.bar = ...
} else {
this.bar = ...
this.foo = ...
}
}

Also, I could imagine this might tax enumeration, since it has to go through the OrderMap indirection. But if this made ordinary property accesses faster, maybe it'd be worth it? Again, I'm probably embarrassing myself showing off my ignorance. But that'd be nothing new. :-P

Dave

[David Herman]

On Apr 21, 2012, at 2:07 PM, David Herman wrote:

> Each instance of the object

Each object instance

Dave

[Boris Zbarsky]

On 4/21/12 5:07 PM, David Herman wrote:
> Also, I could imagine this might tax enumeration, since it has to go through the OrderMap indirection. But if this made ordinary property accesses faster, maybe it'd be worth it? Again, I'm probably embarrassing myself showing off my ignorance. But that'd be nothing new. :-P

This would only make ordinary property access faster if we kept the
invariant that a Shape determines the names corresponding to the slots
of an object, right? And that would mean that property addition would
need to memmove the slots array around as needed, because instead of
just putting the new prop at the end we'd need to put it somewhere in
the middle, in general.

And _that_ would make adding N properties to an object take O(N^2) time,
unless I'm missing something.

That might be OK, since N is typically small, and we could "deoptimize"
to just adding at the end for large N...

Plus of course having to maintain the order map. The upshot would be
possibly faster property reads and somewhat slower property additions,
right? Might be interesting to measure.

-Boris

[David Herman]

On Apr 21, 2012, at 2:19 PM, Boris Zbarsky wrote:

> On 4/21/12 5:07 PM, David Herman wrote:
>> Also, I could imagine this might tax enumeration, since it has to go through the OrderMap indirection. But if this made ordinary property accesses faster, maybe it'd be worth it? Again, I'm probably embarrassing myself showing off my ignorance. But that'd be nothing new. :-P
>
> This would only make ordinary property access faster if we kept the invariant that a Shape determines the names corresponding to the slots of an object, right? And that would mean that property addition would need to memmove the slots array around as needed, because instead of just putting the new prop at the end we'd need to put it somewhere in the middle, in general.

Ah right, very good point.

> And _that_ would make adding N properties to an object take O(N^2) time, unless I'm missing something.

Yeah, that sounds right.

> That might be OK, since N is typically small, and we could "deoptimize" to just adding at the end for large N...
>
> Plus of course having to maintain the order map. The upshot would be possibly faster property reads and somewhat slower property additions, right? Might be interesting to measure.

Yeah, the set of things I don't know here is quite large, including (but not limited to):

- would this actually lead to faster property reads?
- does it make sense to favor reads over writes? my preferred style of programming says yes, but I have no illusions that everyone likes to program like me
- does the web actually have a lot of shape duplication due to accidental property order disagreement?

Andreas suggested I could measure the latter question fairly easily by printing out a bunch of shape trees for real-world web pages. That's something we could measure without having to implement any new object representations, at least. Maybe next week I can get someone to show me how to do that measurement.

Thanks,
Dave