1030083 - Eliminate `index in array` checks for packed arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Till Schneidereit [:till]]

As discussed on IRC, this would speed up all self-hosted array extras that invoke a callback for each element in an array but skip holes.

For Array#indexOf and #lastIndexOf, we use the IsPackedArray intrinsic to check if we can omit the `if (k in O)` check, but for methods that invoke a callback that doesn't work as the callback might delete items in the array.

I'm not sure how common it is in user code to have this type of check, so a self-hosting-only solution might be ok. If it doesn't make too much of a difference implementation-wise, a general solution would be preferable, of course.

Comment 1

[Hannes Verschore [:h4writer]]

Taking. Had a look this afternoon while other things where compiling.

1) Current state: This gets translated into a MInArray, which is actually quite fast. In most cases that only emits branch in the loop itself. The retrieval of other things (initlength/elements) are hoisted above the loop.

2) Possible improvement: We can do something similar like symbolic range analysis with MBoundsCheck, but on MInArray. That should make it possible to see MInArray is always true (if the function is inlined). Removing that branch entirely.

Comment 2

[Hannes Verschore [:h4writer]]

Attachment: WIP

This should do the trick

Comment 3

[Hannes Verschore [:h4writer]]

Attachment: Speculate the InArray check will not fail

Comment 4

[Hannes Verschore [:h4writer]]

Comment on attachment 8450064 [details] [diff] [review]
Speculate the InArray check will not fail

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

::: js/src/jit/IonBuilder.cpp
@@ +10122,5 @@
>      // Get the elements vector.
>      MElements *elements = MElements::New(alloc(), obj);
>      current->add(elements);
>      MInitializedLength *initLength = MInitializedLength::New(alloc(), elements);
>      current->add(initLength);

There is a newline here. Bugzilla is eating it?

Comment 5

[Jan de Mooij [:jandem]]

Comment on attachment 8450064 [details] [diff] [review]
Speculate the InArray check will not fail

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

Nice idea!

::: js/src/jit/IonBuilder.cpp
@@ +10123,5 @@
>      MElements *elements = MElements::New(alloc(), obj);
>      current->add(elements);
>      MInitializedLength *initLength = MInitializedLength::New(alloc(), elements);
>      current->add(initLength);
> +    // If there is no holeCheck, speculate the InArray check will not fail.

Uber comment nit: // If there are no holes, ...

(Yes it's weird, I see the newline in the "raw" patch but not in the review interface :)

Comment 6

[Hannes Verschore [:h4writer]]

Improves the following snippit from 520ms to 400ms

>  function test(arr) {
>     for (var i=0; i<100000000; i++) {
>         var total = 1;
>         if (i%10 in arr) {
>             total += arr[i%10];
>         }
>     }
>     return total;
> }
>
> test([1,2,3,4,5,6,7,8,9,01,12,12])

Comment 7

[Hannes Verschore [:h4writer]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/aa88d3878dbd

Comment 8

[Tim Taubert [:ttaubert] (inactive)]

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