1914502 - Scalar replace Object.keys

Status: NEW

(Core :: JavaScript Engine: JIT, enhancement, P2)

Description

[Iain Ireland [:iain]]

shallowEqual (see below) is one of the hottest functions in React. It is the highest leverage difference between SM and JSC. There are multiple React-based benchmarks in sp3, and lots of important websites use React. We should try to make it faster.

function shallowEqual(objA, objB) {
  if (objectIs(objA, objB)) return !0;
  if ("object" !== typeof objA || null === objA || "object" !== typeof objB || null === objB) return !1;
  var keysA = Object.keys(objA),
    keysB = Object.keys(objB);
  if (keysA.length !== keysB.length) return !1;
  for (keysB = 0; keysB < keysA.length; keysB++) if (!hasOwnProperty$1.call(objB, keysA[keysB]) || !objectIs(objA[keysA[keysB]], objB[keysA[keysB]])) return !1;
  return !0;
}

JSC is faster than we are because they cheaply allocate the result of Object.keys using a copy-on-write array (backed by the same storage as their for-in code), to avoid having to make a copy of the actual keys. I think we can do even better. Cheap allocations are good, but not allocating at all is even better. With some work, I think we can use scalar replacement to entirely avoid allocating in the happy path.

In this comment I sketched out a plan for doing this using the NativeIterator cached on the shape by for-in enumeration:

Rough sketch: we generate a specialized MIR node for Object.keys. In scalar replacement, we look for cases where the only uses of the result are Object.keys(o).length and/or Object.keys(o)[idx]. (We could support more cases if they came up elsewhere.) Object.keys(o) becomes MObjectToIterator. MIteratorLength and MLoadIteratorElement should be relatively simple to implement.

The major obstacle that might sink the whole scheme is figuring out how to close the iterator afterwards. We keep track of which iterators are currently in use because deleting a property during a for-in can mutate the iterator contents. For actual for-in loops, we have bytecode ops and trynotes to ensure that iterators are always closed appropriately. We would need a different approach if we're handling iterators that aren't present in the original bytecode.

If we could make this work, we would be able to eliminate the allocation of the Object.keys arrays, and replace one of the megamorphic loads with a faster version. The megamorphic hasProp and the second megamorphic load are harder to eliminate because they're using keys from one object to access another object.

I think we have a solution for the iterator-closing obstacle in bug 1868857, so we're no longer blocked.

I have a more detailed design doc here.

js-perf-next: Somebody other than me should look over the design and make sure it works. After that, the next step is to polish up the WIP patches in bug 1868857.

Comment 1

[Iain Ireland [:iain]]

One good first step might be to test a modified version of React that uses for-in enumeration, and see how much that improves performance.

Comment 2

[Debadree Chatterjee]

Hello iain!

This seems like a interesting bug, just for learning wanted to read the doc you attached! in case it may not be internal only could i have requested to access to read it! in case i understand things here would love to try out experiments regarding it since i am trying to understand the JIT more!

Thank you!

Comment 3

[Iain Ireland [:iain]]

Oops, no good reason for not making that doc public. You should have access now.

Comment 4

[Nicolas B. Pierron [:nbp]]

If I understand correctly, the goal of this improvement would be to replace Object.keys(obj)[index] by an iterator over the properties of obj?
Relying on Bug 1845728 which already does a similar thing for Object.keys(obj).length ?

I guess this suppose multiple predicates:

• Having a length which is equal (lengthA == lengthB)
• Having a loop which goes from 0 to length.
• Having the loop index only used for accessing the keys and nothing else.
  • Being able to restore the loop index in case of bailouts.
  • Being able to destroy the iterator on bailouts. (we have it for exception but not for bailouts)
• Having no mutation of the keys. (similar to MArrayLength::foldsTo)
• ???

Then the transformation will replace the loop by an iterator loop, where

• { Note: No optimization is possible on OSR. (same for Bug 1845728) }
• Insert an iterator in the entry block of the loop.
• Replace the += 1 instruction by an iterator-next instruction.
• Insert an iterator-close at the end of the loop, and early exit return path.
• Replace obj[keys[index]] by the iterator read of live values.
• Replace the index by the iterator in the snapshot / resume point.
  • We would need an extra recover function to recover the index from the iterator.
  • Probably destroy the iterator from the recover function (?)
• { Let MArrayLength::foldsTo replace the only remaining use of Object.keys(obj) }

So, I do not think this looks like a scalar replacement case nor GVN, but this sounds like we might want to introduce a new phase before GVN, or after by moving the existing MArrayLength::foldsTo to this new transformation phase.

Comment 5

[Iain Ireland [:iain]]

Close, but not quite. We don't have to rewrite the entire loop.

There are more details in the design doc, but I'll sketch it out here too.

Object.keys(obj) returns an array of strings. We want to avoid allocating the array. The array doesn't escape the function here, so we only need to support two things: Object.keys(obj).length, and Object.keys(obj)[i]. What we ideally want is a pre-existing array of strings, cached per-shape, so we can look up the length and elements efficiently without needing an allocation. Fortunately, that's exactly what we already have to support for-in enumeration.

MObjectToIterator returns a PropertyIteratorObject, which is a thin wrapper around a NativeIterator. A NativeIterator has a trailing array of property key strings, starting with own properties, so we can easily support Object.keys(obj)[i]. To support Object.keys(obj).length, we would need to make a small change to store the number of own properties in a NativeIterator (right now NativeIterator::initialPropertyCount includes enumerable properties on the prototype chain). If we bail out, we can recreate the Object.keys array from the NativeIterator.

The iterator closing problem is not that we have to do anything in particular at the end of the Object.keys loop. The issue is that we have a mechanism to prevent multiple for-in enumerations from using the same NativeIterator at once, because SuppressDeletedProperties can mutate the NativeIterator property list if a property is deleted while we're inside the for-in loop. The key observation that makes this all work is that Object.keys just wants to ignore all property deletion. Right now, SuppressDeletedProperties removes the property key from the NativeIterator entirely. If we instead use low-bit tagging to mark deleted properties (bug 1868857), then for-in enumeration can skip tagged properties, Object.keys can simply ignore the isDeleted bit, and everything works out.

So the steps are:

1. Use tag bits instead of removal to suppress deleted properties (bug 1868857).
2. Store numOwnProperties in NativeIterator.
3. Implement scalar replacement, transforming:
   a) MObjectKeys -> MObjectToIterator (or more likely a new MFastObjectKeys node, since we want to recover this one and don't want to do any of the iterator initialization code)
   b) MArrayLength/MInitializedLength -> MIteratorLength
   c) MLoadElement -> MLoadIteratorElement

Then we could do some follow-up work to optimize obj[Object.keys(obj)[i]] and hasOwnProperty(obj, Object.keys(obj)[i]) in the same way that we do inside for-in loops (bug 1799025).

Framed this way, I think scalar replacement is a reasonable approach. Thoughts?

Comment 6

[Nicolas B. Pierron [:nbp]]

(In reply to Iain Ireland [:iain] from comment #5)

Framed this way, I think scalar replacement is a reasonable approach. Thoughts?

I am not sure this is what "scalar replacement" is supposed to be used for as it is supposed to replace allocation content with scalar representation of the allocated content. A part from this bike-shedding issue …

How do you distinguish between previously deleted properties and newly deleted properties on bailout, where the keys array has to be reconstructed from the iterator?

Comment 7

[Nicolas B. Pierron [:nbp]]

(In reply to Nicolas B. Pierron [:nbp] from comment #6)

How do you distinguish between previously deleted properties and newly deleted properties on bailout, where the keys array has to be reconstructed from the iterator?

I guess this is the same issue of Object.keys(o).length and handled by checking that there is no object-field aliasing until the last use of the value.

Comment 8

[Iain Ireland [:iain]]

(In reply to Nicolas B. Pierron [:nbp] from comment #6)

(In reply to Iain Ireland [:iain] from comment #5)

Framed this way, I think scalar replacement is a reasonable approach. Thoughts?

I am not sure this is what "scalar replacement" is supposed to be used for as it is supposed to replace allocation content with scalar representation of the allocated content. A part from this bike-shedding issue …

The allocation in this case is the array containing the result of Array.keys. In the same way that we can elide the allocation of the arguments object by replacing arguments[i] with a node that knows how to look up an argument by index, we can elide hte allocation of the return value of Object.keys by replacing Object.keys(obj)[i] with a node that knows how to look up a key by index.

How do you distinguish between previously deleted properties and newly deleted properties on bailout, where the keys array has to be reconstructed from the iterator?

From the point of view of Object.keys, no property of a NativeIterator is ever deleted.

We cache NativeIterator on the shape. Whenever we get a NativeIterator for an object, it contains exactly the set of properties that the object currently has.

We only delete properties in a NativeIterator if we've already started a for-in enumeration, and we delete a property that we haven't reached yet. So this example should print "x" and "z".

let obj = {x:1, y:2, z:3};
for (var prop in obj) { 
  print(prop); 
  delete obj.y;
}

But deleting a property from an object doesn't affect a call to Object.keys that has already happened. So if we're eliding the allocation of the result array, we want to make sure our backing storage is immutable.

If we represent deletion in a NativeIterator by tagging deleted keys, then this is easy: we just ignore the tags. As long as you're ignoring the tag bits, a NativeIterator is an immutable snapshot of the properties that existed on the object when we obtained it. When we bail out, we just create an array whose elements are the own properties in the NativeIterator.