1928666 - Create Map/Set data lazily and allocate the objects in JIT code

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P2)

Description

[Jan de Mooij [:jandem]]

After bug 1927464 it should be feasible to delay allocation of the malloc buffer to the first put operation. Many Map and Set objects stay empty (> 13% on Speedometer 3) so in these cases we can eliminate the remaining malloc/free.

This will also let us inline Map and Set constructor calls in JIT code. When the constructor is called with an iterable argument we'll still need to do a VM call, but on Speedometer 3 in > 94% of cases there's no argument so we should be able to inline the whole operation.

Eventually we could probably also call the MapConstructorInit and SetConstructorInit self-hosted functions directly from JIT code instead of through C++ (these are used when an iterable is passed to the Map/Set constructor, although for Set we also have a fast path in C++).

Comment 1

[Jan de Mooij [:jandem]]

The changes in comment 0 make allocating empty Map and Set objects much faster. For the micro-benchmark below I get:

old:                172 ms
delay buffer alloc:  36 ms
use template obj:    31 ms
JIT allocation:      16 ms

This is with patches that delay the buffer allocation to the first put and perform the object allocation in JIT code. This micro-benchmark is not adding any entries so we don't have to call into C++ at all.

With an s.add(1) we're still faster but we now have to allocate the buffer so the improvement is much smaller (best of 5 runs, numbers are pretty noisy):

old:                195 ms
delay buffer alloc: 193 ms
use template obj:   187 ms
JIT allocation:     164 ms

It's still an improvement and we can optimize that malloc call more as the next step.

function f() {
  var res = 0;
  var t = new Date;
  for (var i = 0; i < 1_000_000; i++) {
    var s = new Set();
    res += s.size;
  }
  print(new Date - t);
  return res;
}
f();

Comment 2

[Jan de Mooij [:jandem]]

I ended up rewriting the patch stack to first simplify GC handling of Map/Set objects and this also makes nursery-allocating the buffer easier. For the micro-benchmark in comment 1 these additional changes make no difference because it does no buffer allocation anyway:

old: 172 ms
new:  16 ms (same as comment 1)

But with s.add(1) we're now also a lot faster:

old: 198 ms
new:  45 ms (was 164 ms in comment 1)

The micro-benchmark in bug 1926525 improves to 108 ms, 4x faster than before the changes in these bugs.

After this we can squeeze out more performance by optimizing the calls to Map.prototype.set/Set.prototype.add in the JITs with a VM function or callWithABI.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 1 - Replace OrderedHashTableImpl::all with forEach methods. r?jonco!

This is a bit more ergonomic and faster. Ranges are now only used for the JS iterator
objects and this makes it easier to reason about them.

As a follow-up we could move the Range fields into reserved slots of the iterator
objects and avoid the separate allocation.

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 2 - Remove Range::onTableDestroyed. r?jonco!

onTableDestroyed iterates over all ranges and this is blocking us from doing
background finalization of Map and Set objects.

Note that Range no longer stores a pointer to the table and the methods instead
take the Map or Set object as argument. This makes invalidating the ranges less
valuable than it was before.

Comment 5

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 3 - Use background finalization for Map/Set objects. r?jonco!

This also has a few other changes to avoid triggering pre-barrier assertions
off-thread when finalizing the object or updating pointers for compacting GC.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 4 - Support nursery-allocated buffer for Map/Set objects. r?jonco!

This changes how the buffer is allocated/freed to be more similar to other objects with
nursery-allocated buffers. The finalizer is no longer called for nursery Map/Set
objects but we rely on the nursery's malloc buffer handling instead.

Nursery-allocating this buffer is a large speedup. We just have to fix up the hash table
chains after moving the buffer in memory.

Comment 7

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 5 - Change with-nursery-memory lists to with-nursery-ranges lists. r?jonco!

After the previous patch we no longer need to sweep all nursery allocated
Map and Set objects after a minor GC. We only need to register and sweep
objects that had a nursery-allocated iterator.

This renames HasNurseryMemory to HasRegisteredNurseryRanges to avoid confusion with
OrderedHashTableImpl::hasNurseryRanges.

Comment 8

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 6 - Allocate the buffer lazily on the first put operation. r?jonco!

On Speedometer 3 more than 10% of Map/Set objects stay empty, so allocating
the buffer lazily is more efficient and saves some memory. This also makes it
easier to allocate the objects from JIT code.

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 7 - Add Map/Set template objects to optimize allocation. r?jonco!

This is similar to how we optimize allocation of arguments objects.

The next patch will also use these template objects for JIT code.

Comment 10

[Jan de Mooij [:jandem]]

Attachment: Bug 1928666 part 8 - Inline Map/Set constructor calls in JIT code. r?jonco!

We can now inline new Map() and new Set() and allocate the objects directly from
JIT code. We don't optimize if there's an iterable argument, but this could be supported
later on.

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/d44f1938c3a2
part 1 - Replace OrderedHashTableImpl::all with forEach methods. r=jonco
https://hg.mozilla.org/integration/autoland/rev/235fea09919f
part 2 - Remove Range::onTableDestroyed. r=jonco
https://hg.mozilla.org/integration/autoland/rev/2939207fc517
part 3 - Use background finalization for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/d7713878ca50
part 4 - Support nursery-allocated buffer for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/445eb44a0bac
part 5 - Change with-nursery-memory lists to with-nursery-ranges lists. r=jonco
https://hg.mozilla.org/integration/autoland/rev/8785cdc16361
part 6 - Allocate the buffer lazily on the first put operation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/4dfb23b1d7e2
part 7 - Add Map/Set template objects to optimize allocation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/214e2313ee58
part 8 - Inline Map/Set constructor calls in JIT code. r=jonco

Comment 12

[pstanciu]

https://hg.mozilla.org/mozilla-central/rev/d44f1938c3a2
https://hg.mozilla.org/mozilla-central/rev/235fea09919f
https://hg.mozilla.org/mozilla-central/rev/2939207fc517
https://hg.mozilla.org/mozilla-central/rev/d7713878ca50
https://hg.mozilla.org/mozilla-central/rev/445eb44a0bac
https://hg.mozilla.org/mozilla-central/rev/8785cdc16361
https://hg.mozilla.org/mozilla-central/rev/4dfb23b1d7e2
https://hg.mozilla.org/mozilla-central/rev/214e2313ee58

Comment 13

[Mayank Bansal]

31% improvement on six-speed-map-set-es6
30% on six-speed-map-set-object-es6
3.8% overall on Ares6!
9% on jetstream2-WSL-gemoetric

Comment 14

[Florin Bilt]

(In reply to Pulsebot from comment #11)

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/d44f1938c3a2
part 1 - Replace OrderedHashTableImpl::all with forEach methods. r=jonco
https://hg.mozilla.org/integration/autoland/rev/235fea09919f
part 2 - Remove Range::onTableDestroyed. r=jonco
https://hg.mozilla.org/integration/autoland/rev/2939207fc517
part 3 - Use background finalization for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/d7713878ca50
part 4 - Support nursery-allocated buffer for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/445eb44a0bac
part 5 - Change with-nursery-memory lists to with-nursery-ranges lists.
r=jonco
https://hg.mozilla.org/integration/autoland/rev/8785cdc16361
part 6 - Allocate the buffer lazily on the first put operation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/4dfb23b1d7e2
part 7 - Add Map/Set template objects to optimize allocation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/214e2313ee58
part 8 - Inline Map/Set constructor calls in JIT code. r=jonco

Perfherder has detected a awsy performance change from push 214e2313ee58ff49d144f0d627a69b2f9d7d8ad5.

Improvements:

Ratio	Test	Platform	Options	Absolute values (old vs new)
0.39%	Base Content JS	linux1804-64-shippable-qr	fission	1,522,320.00 -> 1,516,333.33

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

If you need the profiling jobs you can trigger them yourself from treeherder job view or ask a sheriff to do that for you.

You can run these tests on try with ./mach try perf --alert 42662

For more information on performance sheriffing please see our FAQ.

Comment 15

[Florin Bilt]

(In reply to Pulsebot from comment #11)

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/d44f1938c3a2
part 1 - Replace OrderedHashTableImpl::all with forEach methods. r=jonco
https://hg.mozilla.org/integration/autoland/rev/235fea09919f
part 2 - Remove Range::onTableDestroyed. r=jonco
https://hg.mozilla.org/integration/autoland/rev/2939207fc517
part 3 - Use background finalization for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/d7713878ca50
part 4 - Support nursery-allocated buffer for Map/Set objects. r=jonco
https://hg.mozilla.org/integration/autoland/rev/445eb44a0bac
part 5 - Change with-nursery-memory lists to with-nursery-ranges lists.
r=jonco
https://hg.mozilla.org/integration/autoland/rev/8785cdc16361
part 6 - Allocate the buffer lazily on the first put operation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/4dfb23b1d7e2
part 7 - Add Map/Set template objects to optimize allocation. r=jonco
https://hg.mozilla.org/integration/autoland/rev/214e2313ee58
part 8 - Inline Map/Set constructor calls in JIT code. r=jonco

Perfherder has detected a browsertime performance change from push 214e2313ee58ff49d144f0d627a69b2f9d7d8ad5.

Improvements:

Ratio	Test	Platform	Options	Absolute values (old vs new)	Performance Profiles
4%	ares6	windows11-64-shippable-qr	fission webrender	15.72 -> 15.03	Before/After
4%	ares6	windows11-64-shippable-qr	fission webrender	15.67 -> 14.99	Before/After

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

If you need the profiling jobs you can trigger them yourself from treeherder job view or ask a sheriff to do that for you.

You can run these tests on try with ./mach try perf --alert 42726

For more information on performance sheriffing please see our FAQ.