Hi
i'm currently facing a performance issue that i can reproduce with the following test case

var table = [/* +800k integers */]
const t0 = performance.now();
const o = {}
for (var i of table) {
	o[i] = {};
}
const t1 = performance.now();
console.log(`${t1- t0} ms`);

(see table.js in attachment for the actual table)

This logs +30s on Firefox in my tests.
For comparison, it runs in under 200ms in Chrome (103.0.5060.134)

The profiler indicates that all the time is spent in this stack

[52%] [js::ShapePropertyIter<js::NoGC>::operator++(int)
[98%] static js::NativeObject::maybeDensifySparseElements(JSContext*, JS::Handle<js::NativeObject *>)
[99%] js::NativeSetProperty<js::Qualified>(JSContext*, JS::Handle<js::NativeObject *>, JS::Handle<JS::PropertyKey>, JS::Handle<JS::Value>, JS::Handle<JS::Value>, JS::ObjectOpResult&)
[99%] js::SetObjectElement(JSContext*, JS::Handle<JSObject *>, JS::Handle<JS::Value>, JS::Handle<JS::Value>, bool)
[99%] static js::jit::IonSetPropertyIC::update(JSContext*, JS::Handle<JSScript *>, [99%] js::jit::IonSetPropertyIC*, JS::Handle<JSObject *>, JS::Handle<JS::Value>, JS::Handle<JS::Value>)
[99%] 0x30cc9365305
[100%] http://127.0.0.1:3333/test_case.js

See profile at : https://share.firefox.dev/3SeZeP4

I noted that if for ... of is replaced by for ... in in this test case, the performance problem disappear, and the code runs in about 400ms.

See profile at : https://share.firefox.dev/3Q648vS

I'm attaching the full test case

Reproduced on
Firefox 103.0 (buildid: 20220731212434)
Firefox 105.0a1 (buildid: 20220731212434)

The Bugbug bot thinks this bug should belong to the 'Core::JavaScript Engine' component, and is moving the bug to that component. Please correct in case you think the bot is wrong.

The for-in test adds the properties 0...table.length - 1, whereas the for-of test adds the properties from table's content. Changing the for-in to match the for-of test makes it just as slow:

for (let i in table) {
  o[table[i]] = {};
}

Thanks a lot for the great test case!

This has to do with sparse elements: we try to densify them when adding a sparse element iff the slot span is a power-of-two, but if we grab slots from the slot free list instead of allocating a new slot, the slot span can be the same power-of-two for a long time and we get quadratic behavior.

The power-of-two heuristic in maybeDensifySparseElements doesn't work well if
we're getting slots from the slot free list, because in that case the slot span
can be the same power-of-two for a long time and adding elements becomes
quadratic.

This patch avoids the problem by only trying to densify if we're using the last
slot. That still handles the common initialization pattern this code was written
to handle.

Dictionary slots currently never shrink: when removing properties we put the slots
on the dictionary free list. If we know there are no slotful properties left, however,
we can free the slots and reset the free list.

This is mostly nice for densifying because we can usually free all slots in that case.

The patch also fixes a minor issue in NativeObject::shrinkSlots, because this code
is now used for dictionary objects for the first time.

Depends on D153436

This also adds testing functions to allocate and check objects with many reserved slots.

Depends on D153437

The attached patches improve this from > 17.7 seconds to 0.24 seconds in the JS shell.

As a workaround/fix, consider using a Map instead. This has similar performance for me on this test case and is probably a better fit for this use case.

A Map will do indeed.
Thanks.

https://hg.mozilla.org/mozilla-central/rev/5c8ef63db5fc
https://hg.mozilla.org/mozilla-central/rev/3766c1004d20
https://hg.mozilla.org/mozilla-central/rev/d26462ccbfa0