Closed Bug 1030083 Opened 5 years ago Closed 5 years ago

Eliminate `index in array` checks for packed arrays

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla33

People

(Reporter: till, Assigned: h4writer)

References

Details

Attachments

(1 file, 1 obsolete file)

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.
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.
Assignee: general → hv1989
Attached patch WIP (obsolete) — Splinter Review
This should do the trick
Attachment #8448550 - Attachment is obsolete: true
Attachment #8450064 - Flags: review?(jdemooij)
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 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 :)
Attachment #8450064 - Flags: review?(jdemooij) → review+
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])
https://hg.mozilla.org/mozilla-central/rev/aa88d3878dbd
Status: NEW → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla33
You need to log in before you can comment on or make changes to this bug.