1782487 - javascript : poor performance on massive object update

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[rsystancia]

Attachment: full test case

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)

Comment 1

[BugBot [:suhaib / :marco/ :calixte]]

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.

Comment 2

[André Bargull [:anba]]

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]] = {};
}

Comment 3

[Jan de Mooij [:jandem]]

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.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1782487 part 1 - Only densify sparse elements if the added property uses the last slot. r?jonco!

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.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1782487 part 2 - Free dictionary slots if possible after densifying or removing properties. r?jonco!

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

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Bug 1782487 part 3 - Add some tests. r?jonco!

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

Depends on D153437

Comment 7

[Jan de Mooij [:jandem]]

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.

Comment 8

[rsystancia]

A Map will do indeed.
Thanks.

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/5c8ef63db5fc
part 1 - Only densify sparse elements if the added property uses the last slot. r=jonco
https://hg.mozilla.org/integration/autoland/rev/3766c1004d20
part 2 - Free dictionary slots if possible after densifying or removing properties. r=jonco
https://hg.mozilla.org/integration/autoland/rev/d26462ccbfa0
part 3 - Add some tests. r=jonco

Comment 10

[Sandor Molnar[:smolnar]]

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