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

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[André Bargull [:anba]]

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?

Comment 1

[André Bargull [:anba]]

Attachment: bug1380961.patch

Comment 2

[Jan de Mooij [:jandem]]

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.

Comment 3

[Jan de Mooij [:jandem]]

Attachment: Hack

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.

Comment 4

[Jan de Mooij [:jandem]]

That said, I do want to understand what's causing the Ion perf issue in comment 0 :)

Comment 5

[Jan de Mooij [:jandem]]

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.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Patch

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.

Comment 7

[Nicolas B. Pierron [:nbp]]

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.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/f763d7564c56
Fix SimpleArithOperand to return false if the TypeSet is empty. r=nbp

Comment 9

[Jan de Mooij [:jandem]]

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.

Comment 10

[Guilherme Lima]

According to AWFY apparently this patch improved Dromaeo overall result by ~10%, but none of the subtest graphs show an improvement!

Comment 11

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

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