1502905 - Iterator cache should support dense elements (Firefox is 3.5x slower than Chrome)

Status: NEW

(Core :: JavaScript Engine, enhancement, P3)

Description

[Jan de Mooij [:jandem]]

See bug 505818 comment 17 and comment 18 for a testcase and some analysis.

Comment 1

[Mayank Bansal]

Testcase from https://bugzilla.mozilla.org/show_bug.cgi?id=505818#c17

Nightly: https://share.firefox.dev/47wxKMr (7 seconds with profiler)
Chrome: https://share.firefox.dev/3YS8HzH (2 seconds)

Comment 2

[Mayank Bansal]

Attachment: testcase from 505818#c17 .html

Comment 3

[Iain Ireland [:iain]]

Here's a potential plan that would allow us to support caching iterators with packed dense elements.

We add two extra fields to NativeIterator: one that counts how many (packed dense) elements the object being iterated has, and one that counts how many we haven't visited yet. When we try to get an iterator for an object, if the object has less than StaticStrings::INT_STATIC_LIMIT packed dense elements (currently 256), then we initialize numElements and numUnvisitedElements to the same number.

We add an extra check in MoreIter: before returning any of the strings stored in the property list, we check to see if numUnvisitedElements is non-zero. If it is, then we compute the index of the next unvisited element (numElements - numUnvisitedElements), then look up that string in the static strings table and return it, decrementing numUnvisitedElements by 1.

(As a future extension, if we wanted to support more than 256 elements, we could maybe have a shared cache that we fill with numeric strings on-demand.)

We would still not cache an object if it has a prototype with an indexed property.

One tricky part is making sure we get deletion right. It almost works to just check for the hole value, but unfortunately we have to distinguish between the case where the property was deleted (and should not be enumerated) vs the case where the property became sparse (eg Object.defineProperty(obj, 2, { value: 0, writable: false }). But I think it should be fine to set a flag on the iterator if any unvisited dense elements are deleted, check for that flag when iterating, and fall back to a slow path that does a callWithABI to look at the shape. We can clear the flag at the end of iteration.

This adds a single branch in MoreIter to cases we currently support. When loading a cached iterator in maybeLoadIteratorFromShape, we already have to check for indexed properties, so nothing changes there.

The indices optimization already supports objects with own dense elements. I think we would only have to modify MacroAssembler::extractCurrentIndexAndKindFromIterator to make this new approach play nicely with the indices optimization. We do have to be a bit careful, because we advance the iterator first and extract the index/kind later, so when we're reading the final element we will see numUnvisitedElements = 0, but since we won't start advancing the properties cursor until we're done with elements, we could instead just compare propertyCursor to propertiesBegin (which is cheap because we already compute the difference). If the two pointers are equal, then we must still be looking at elements.