Closed Bug 1380961 Opened 5 years ago Closed 5 years ago

Array.prototype.indexOf/lastIndexOf is faster when the optional fromIndex argument is provided

Categories

(Core :: JavaScript Engine: JIT, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla56
Tracking Status
firefox56 --- fixed

People

(Reporter: anba, Assigned: jandem)

Details

Attachments

(3 files)

This µ-benchmark completes in 345ms for me when called without the optional fromIndex argument, but only needs 125ms when the fromIndex argument is provided. Similar performance differences are observable for Array.prototype.lastIndexOf. 

---
function f() {
    var a = Array(10).fill(0).map((v, k) => k + 1);
    var q = 0;
    var t = Date.now();
    for (var i = 0; i < 10000000; ++i) {
        var p = a.indexOf(0);
        q += p;
    }
    return [Date.now() - t, q];
}
print(f());
---

With the attached patch, the µ-benchmark always completes in ~125ms. Does it make sense to simply apply the patch as-is, or is it more useful to determine why Ion doesn't optimize Array.prototype.indexOf/lastIndexOf correctly when the lastIndex argument isn't present?
Attached patch bug1380961.patchSplinter Review
Tom and I were talking about indexOf/lastIndexOf in SF.

I think we should consider rewriting them in C++ - these functions are very polymorphic and don't really benefit from self-hosting like, say, Array.prototype.map. Self-hosting hurts us on some of the six-speed tests.

One issue is that the Vanilla* Speedometer tests use indexOf on a NodeList (a DOM proxy), so we might want to add a special path for proxies.
Attached patch HackSplinter Review
Here's a very hackish patch I wrote in SF to show what this might look like. For instance if we're searching for an object/symbol, we can just compare the Values (the bit pattern) directly.
That said, I do want to understand what's causing the Ion perf issue in comment 0 :)
Flags: needinfo?(jdemooij)
So in the slow case, we end up with a double instead of int32 type for |k|. My best guess is that we don't have type information for ToInteger(arguments[1]) + 0 so we pretend it's a double and that then flows into |n| and |k|.

Digging more.
Attached patch PatchSplinter Review
So on this line:

    var n = arguments.length > 1 ? ToInteger(arguments[1]) + 0 : 0;

We have empty types for ToInteger(arguments[1]), because it's never executed. We then specialize the addition as double, because SimpleArithOperand returns true when the instruction has an empty type set.

This patch just changes SimpleArithOperand to return false when we don't have type information.
Assignee: nobody → jdemooij
Status: NEW → ASSIGNED
Flags: needinfo?(jdemooij)
Attachment #8886559 - Flags: review?(nicolas.b.pierron)
Comment on attachment 8886559 [details] [diff] [review]
Patch

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

I was a little worried with this change, as we should produce a MCall for the binary operation.
On the other hand, this branch never got used and any call penalize the branch toward being pruned by Branch Pruning.
Thus removing this branch will cause "n" to become a constant.
Attachment #8886559 - Flags: review?(nicolas.b.pierron) → review+
Pushed by jandemooij@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f763d7564c56
Fix SimpleArithOperand to return false if the TypeSet is empty. r=nbp
This improved some six-speed tests, especially this one: https://arewefastyet.com/#machine=29&view=single&suite=six-speed&subtest=map-set-lookup-es5

Also a small win on sunspider crypto-aes. This will probably help a lot of things.
According to AWFY apparently this patch improved Dromaeo overall result by ~10%, but none of the subtest graphs show an improvement!
https://hg.mozilla.org/mozilla-central/rev/f763d7564c56
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla56
You need to log in before you can comment on or make changes to this bug.