1198377 - Consider moving parts of (Weak)Map and (Weak)Set initialization to self hosted code

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, defect)

Description

[André Bargull [:anba]]

Attachment: WIP patch, needs clean up

Moving steps 7-9 of 23.1.1.1 Map, 23.2.1.1 Set, 23.3.1.1 WeakMap and 23.4.1.1 WeakSet to self-hosted code improved performance a lot (in micro benchmarks).

For example this code:
---
function fromMap() {
  var arraySize = 1000;
  var iter = 1000;

  var m = new Map(new Array(arraySize).fill(null).entries());
  var d = Date.now();
  for (var i = 0; i < iter; ++i) new Map(m);
  return Date.now() - d;
}
---

Takes ~280ms instead of ~590ms when the initialization loop is executed in self-hosted code. There is a slight regression for array input values, because that case is currently optimized through ForOfIterator. 

---
function fromArray() {
  var arraySize = 10;
  var iter = 100000;

  var m = [...new Array(arraySize).fill(null).entries()];
  var d = Date.now();
  for (var i = 0; i < iter; ++i) new Map(m);
  return Date.now() - d;
}
---

Takes ~280ms with self-hosted initialization and ~230ms without. Note that the array size is only 10, for larger array sizes self-hosting gets faster again. If necessary the array case can be excluded from self-hosting and stay in native code.

Comment 1

[Till Schneidereit [:till]]

Comment on attachment 8652450 [details] [diff] [review]
WIP patch, needs clean up

Review of attachment 8652450 [details] [diff] [review]:
-----------------------------------------------------------------

This is really nice!

How much more code is this compared to what we have now? It's hard to tell because no code is actually removed. That'd be my only worry: that we have substantially more code, not all of it all that trivial.

Also, how does the self-hosted implementation fare when used with different types? I.e., a builtin iterable and a custom one, and the Array case, say. It might be that it gets significantly slower because it has to deoptimize, but I'm not sure.

(Note that I didn't read through absolutely everything in the patch. The f+ is for the approach in general, which we could probably use in more situations.)

Comment 2

[André Bargull [:anba]]

(In reply to Till Schneidereit [:till] from comment #1)
> How much more code is this compared to what we have now? It's hard to tell
> because no code is actually removed. That'd be my only worry: that we have
> substantially more code, not all of it all that trivial.

Without the array iteration fast path:  9 files changed, 157 insertions(+), 231 deletions(-)
With the array fast path [1, 2]: 9 files changed, 306 insertions(+), 137 deletions(-)

[1] This still includes 3 copies of the method IsOptimizedArrayForOf function, each 20 LOC. 
[2] Ignoring white space changes: 9 files changed, 216 insertions(+), 47 deletions(-)


> Also, how does the self-hosted implementation fare when used with different
> types? I.e., a builtin iterable and a custom one, and the Array case, say.
> It might be that it gets significantly slower because it has to deoptimize,
> but I'm not sure.

The numbers didn't change with mixed input types.

Comment 3

[André Bargull [:anba]]

Attachment: collection_min.patch

WIP Patch without array fast path

Comment 4

[André Bargull [:anba]]

Attachment: collection_array.patch

WIP Patch with array fast path

Comment 5

[André Bargull [:anba]]

Attachment: collection_array.patch

Comment 6

[André Bargull [:anba]]

Attachment: benchmark script

Comment 7

[André Bargull [:anba]]

Attachment: benchmark results

Benchmark results. SM (new) includes the changes from bug 1288541, so we can see its synergies when combined with this patch.

Comment 8

[Till Schneidereit [:till]]

Comment on attachment 8783340 [details] [diff] [review]
collection_array.patch

Review of attachment 8783340 [details] [diff] [review]:
-----------------------------------------------------------------

Those are convincing numbers! Thank you for the detailed analysis, and the great patch.

I have a few nits below, but overall, this looks absolutely great.

(Btw, I just notice that your patch header looks weird, with the name garbled with some seemingly UTF-8 related stuff. Might be a display issue only, but worth checking.)

::: js/src/builtin/Map.js
@@ +20,5 @@
> +
> +    // Step 7 (not applicable).
> +
> +    // Step 8.
> +    for (;;) {

Please use `while (true)` here. If that's slower for some unfathomable reason, please file a bug about that.

::: js/src/builtin/MapObject.h
@@ +221,4 @@
>      static bool is(HandleValue v);
>      static bool is(HandleObject o);
>  
> +    static bool isOptimizableInit(JSContext* cx, Handle<SetObject*> setObject,

Add MOZ_MUST_USE to this.

::: js/src/builtin/Set.js
@@ +20,5 @@
> +
> +    // Step 7 (not applicable).
> +
> +    // Step 8.
> +    for (;;) {

Please use `while (true)` here.

::: js/src/builtin/WeakMap.js
@@ +20,5 @@
> +
> +    // Step 7 (not applicable).
> +
> +    // Step 8.
> +    for (;;) {

Please use `while (true)` here.

@@ +35,5 @@
> +        var nextItem = next.value;
> +
> +        // Step 8.d.
> +        if (!IsObject(nextItem))
> +            ThrowTypeError(JSMSG_INVALID_MAP_ITERABLE, "Map");

This should be "WeakMap", right?

::: js/src/builtin/WeakSet.js
@@ +2,5 @@
>   * License, v. 2.0. If a copy of the MPL was not distributed with this
>   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
>  
> +// ES2017, 23.4.1.1 WeakSet, steps 6-8
> +function WeakSetConstructorInit(iterable) {

Given that this function is entirely identical, is there any reason not to just use the Set version for WeakSet, too?

@@ +20,5 @@
> +
> +    // Step 7 (not applicable).
> +
> +    // Step 8.
> +    for (;;) {

Please use `while (true)` here.

::: js/src/builtin/WeakSetObject.cpp
@@ +74,4 @@
>  }
>  
>  bool
> +WeakSetObject::isOptimizableInit(JSContext* cx, Handle<WeakSetObject*> weakSetObject,

It'd be nice to fold this into a templated function for both Set and WeakSet. The slight difference around checking for the canonical add function doesn't seem to add too much complexity for that.

@@ +116,1 @@
>  WeakSetObject::construct(JSContext* cx, unsigned argc, Value* vp)

The same is probably true for construct, but that's largely preexisting, so feel free to ignore.

Comment 9

[André Bargull [:anba]]

(In reply to Till Schneidereit [:till] from comment #8)
> I have a few nits below, but overall, this looks absolutely great.

\o/


> (Btw, I just notice that your patch header looks weird, with the name
> garbled with some seemingly UTF-8 related stuff. Might be a display issue
> only, but worth checking.)

Yes, I know. It's a git patch, I just need to convert it to a proper mercurial patch.


> ::: js/src/builtin/Map.js
> @@ +20,5 @@
> > +
> > +    // Step 7 (not applicable).
> > +
> > +    // Step 8.
> > +    for (;;) {
> 
> Please use `while (true)` here. If that's slower for some unfathomable
> reason, please file a bug about that.

I'd be shocked if `while (true)` is slower. :-)

> 
> @@ +35,5 @@
> > +        var nextItem = next.value;
> > +
> > +        // Step 8.d.
> > +        if (!IsObject(nextItem))
> > +            ThrowTypeError(JSMSG_INVALID_MAP_ITERABLE, "Map");
> 
> This should be "WeakMap", right?

Sure.


> 
> ::: js/src/builtin/WeakSet.js
> @@ +2,5 @@
> >   * License, v. 2.0. If a copy of the MPL was not distributed with this
> >   * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> >  
> > +// ES2017, 23.4.1.1 WeakSet, steps 6-8
> > +function WeakSetConstructorInit(iterable) {
> 
> Given that this function is entirely identical, is there any reason not to
> just use the Set version for WeakSet, too?

It may have an impact on performance when both Set and WeakSet are used, because the code is no longer monomorphic?

Comment 10

[André Bargull [:anba]]

Attachment: collection_array.patch

Updated patch, carrying r+ from Till.

Comment 11

[Till Schneidereit [:till]]

> It may have an impact on performance when both Set and WeakSet are used, because the code is no longer monomorphic?

Good point. If only JS had a good (any) templating or macro mechanism ... It doesn't, so let's keep this as-is.

> Yes, I know. It's a git patch, I just need to convert it to a proper mercurial patch.

I recently started using git-cinnabar, and it's pretty great:
https://github.com/glandium/git-cinnabar/wiki/Mozilla:-A-git-workflow-for-Gecko-development

I even started using reviewboard, because `git mozreview push` is a pretty nice workflow for requesting reviews.

Comment 12

[André Bargull [:anba]]

Attachment: bug1198377.patch

Patch needed bit-unrotting, carrying r+ from Till.

Changes compared to the previous patch:
(1) Added support for JSOP_NEW to DecompileArgumentFromStack (jsopcode.cpp) to avoid test regressions in "devtools/client/webconsole/test/browser_console_addonsdk_loader_exception.js".
(2) Added missing Rooted to WeakSet constructor to avoid hazard failure.


Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=3d55e89b2945

Previous try without changes 1-2: https://treeherder.mozilla.org/#/jobs?repo=try&revision=d609e58adf73

Comment 13

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/a045ca98c52c
Move Map/Set constructor initialization to self-hosted code. r=till

Comment 14

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/5e62b27c11b2
Backed out changeset a045ca98c52c for suspicion that this cause windows 7 reftest crashes

Comment 15

[Carsten Book [:Tomcat]]

sorry had to back this out since this seems to caused crashes like https://treeherder.mozilla.org/logviewer.html#?job_id=37170195&repo=mozilla-inbound

Comment 16

[André Bargull [:anba]]

(In reply to Carsten Book [:Tomcat] from comment #15)
> sorry had to back this out since this seems to caused crashes like
> https://treeherder.mozilla.org/logviewer.html#?job_id=37170195&repo=mozilla-
> inbound

The Reftest crashes aren't reproducible for me, so probably some other patch caused them:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=222fa970af13163936d335d3c51afc81e5268227

Comment 17

[Till Schneidereit [:till]]

They could theoretically be new intermittent failures introduced by this patch. I have a hard time imagining that, though, so my guess is that it's actually a new intermittent introduced by some other patch.

Setting checkin-needed again on that basis.

Comment 18

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/b6f1126059ef
Move Map/Set constructor initialization to self-hosted code. r=till

Comment 19

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

Sorry, had to back this out for asserting in for-in-iterator-1.js:

https://hg.mozilla.org/integration/mozilla-inbound/rev/32a726cdfabd58fe7569cffb22f1a6c3abba27a8

Push with failure: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=b6f1126059ef32ac61c7974e14e3ac7e79722e4b
Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=37252575&repo=mozilla-inbound

[task 2016-10-07T14:21:23.364345Z] TEST-PASS | js/src/jit-test/tests/ion/fold-in.js | Success (code 0, args "--baseline-eager")
[task 2016-10-07T14:21:23.816706Z] /home/worker/workspace/build/src/js/src/jit-test/tests/ion/for-in-iterator-1.js:27:5 Error: Assertion failed: got true, expected false
[task 2016-10-07T14:21:23.816802Z] Stack:
[task 2016-10-07T14:21:23.816860Z]   @/home/worker/workspace/build/src/js/src/jit-test/tests/ion/for-in-iterator-1.js:27:5
[task 2016-10-07T14:21:23.816891Z] Exit code: 3
[task 2016-10-07T14:21:23.816919Z] FAIL - ion/for-in-iterator-1.js
[task 2016-10-07T14:21:23.817032Z] TEST-UNEXPECTED-FAIL | js/src/jit-test/tests/ion/for-in-iterator-1.js | /home/worker/workspace/build/src/js/src/jit-test/tests/ion/for-in-iterator-1.js:27:5 Error: Assertion failed: got true, expected false (code 3, args "--ion-eager --ion-offthread-compile=off")
[task 2016-10-07T14:21:23.817067Z] INFO exit-status     : 3
[task 2016-10-07T14:21:23.817096Z] INFO timed-out       : False
[task 2016-10-07T14:21:23.817169Z] INFO stderr         2> /home/worker/workspace/build/src/js/src/jit-test/tests/ion/for-in-iterator-1.js:27:5 Error: Assertion failed: got true, expected false
[task 2016-10-07T14:21:23.817204Z] INFO stderr         2> Stack:
[task 2016-10-07T14:21:23.817262Z] INFO stderr         2> @/home/worker/workspace/build/src/js/src/jit-test/tests/ion/for-in-iterator-1.js:27:5

Comment 20

[André Bargull [:anba]]

(In reply to Sebastian Hengst [:aryx][:archaeopteryx] from comment #19)
> Sorry, had to back this out for asserting in for-in-iterator-1.js:

Filed bug 1308721 for jonco to investigate.

Comment 21

[André Bargull [:anba]]

Attachment: bug1198377.patch

Updated patch to apply cleanly on inbound. Carrying r+ from Till.

Comment 22

[André Bargull [:anba]]

Re-requesting checkin-needed now that bug 1308721 is fixed.

Comment 23

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/d4fe7282fee5
Move Map/Set constructor initialization to self-hosted code. r=till

Comment 24

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/d4fe7282fee5