902822 - Array.indexOf become very slow in firefox 23, 8 times slower than before

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Sam]

User Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.7; rv:23.0) Gecko/20100101 Firefox/23.0 (Beta/Release)
Build ID: 20130730113002

Steps to reproduce:

var array = [];
var i = 0;
while(i++ < 10000){
    array.push(i);
}
i = 0;
var time = Date.now();
while(i++ < 1000){
array.indexOf(5000);
}
console.log(Date.now() - time);

and the resullt is : 
    firefox 23 - 1107ms
    firefox 11 - 79ms
    chrome - 62ms
    opera - 193ms



Actual results:

Array.indexOf become very slow in firefox 23, about 8 times slower than before

Comment 1

[Till Schneidereit [:till]]

Looking

Comment 2

[André Bargull [:anba]]

Some intermediary results (not the latest source, built on 5th Aug):

Using `array.indexOf(5000, 0)` instead of `array.indexOf(5000)` is way faster (~60ms instead of ~280ms for me).

And --ion-eager with `array.indexOf(5000)` is ~390ms and with `array.indexOf(5000, 0)` ~900ms.

Comment 3

[André Bargull [:anba]]

With the latest source everything works fine, execution time is ~30ms to ~50ms for me. Only --ion-eager is still slow.

Comment 4

[Alice0775 White]

There are strange regression behavior
#1 If the JS code evaluated in Web Console: 
  Regressed by: Bug 784294

#2 If the JS code evaluated in HTML document
#2-1 Regressed(from 40ms to 450ms) by: 
  cb36ad241f80	Brian Hackett — Merge m-i to ionmonkey
#2-2 Significant regressed(from 450ms to 1600ms) by:
  4bba65656e46	Jan de Mooij — Bug 858551 part 2 - Optimize calls from Ion to Baseline code. r=djvj
#2-3 Slightly improoved(from 1600ms to 1400ms) by:
  Bug 865259


#1 If the JS code evaluated in Web Console:
Good 120ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/7ae5ff606cf2
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20.0 Firefox/20.0 ID:20121121153752
Bad  1600ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/37c36aa6f563
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:20.0) Gecko/20.0 Firefox/20.0 ID:20121121165251
Pushlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=7ae5ff606cf2&tochange=37c36aa6f563
Regressed by: Bug 784294


#2 If the JS code evaluated in HTML document

#2-1
Regression window(m-c)
Good 40ms:
http://hg.mozilla.org/mozilla-central/rev/591caa6e37af
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130423 Firefox/23.0 ID:20130423095633
Bad 450 ms:
http://hg.mozilla.org/mozilla-central/rev/8b1a7228674a
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130423 Firefox/23.0 ID:20130423120807
Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=591caa6e37af&tochange=8b1a7228674a

Regression window(m-i)
Good 40ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/a97e447e504f
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130422 Firefox/23.0 ID:20130423043634
Bad 450 ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/c3a204a6b498
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130423 Firefox/23.0 ID:20130423044135
Pshlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=a97e447e504f&tochange=c3a204a6b498

Suspected: 
cb36ad241f80	Brian Hackett — Merge m-i to ionmonkey


#2-2
Significant Regression window(m-c)
Bad 450 ms:
http://hg.mozilla.org/mozilla-central/rev/1c5977e8d52f
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130424 Firefox/23.0 ID:20130424051650
Bad 1400ms:
http://hg.mozilla.org/mozilla-central/rev/07e17dd7813b
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130424 Firefox/23.0 ID:20130424131851
Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=1c5977e8d52f&tochange=07e17dd7813b

Significant Regression window(m-i)
Bad 450 ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/781a47680e34
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130424 Firefox/23.0 ID:20130424033751
Bad 1600ms
http://hg.mozilla.org/integration/mozilla-inbound/rev/4bba65656e46
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130424 Firefox/23.0 ID:20130424040349
Pushlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=781a47680e34&tochange=4bba65656e46

Suspected: 
4bba65656e46	Jan de Mooij — Bug 858551 part 2 - Optimize calls from Ion to Baseline code. r=djvj


#2-3
Slightly improove window(m-c)
Bad 1600ms
http://hg.mozilla.org/mozilla-central/rev/40dafc376794
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130427 Firefox/23.0 ID:20130427083404
Bad 1400ms:
http://hg.mozilla.org/mozilla-central/rev/9d8977cbbfc6
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130427 Firefox/23.0 ID:20130427182505
Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=40dafc376794&tochange=9d8977cbbfc6

Slightly improove window(m-i)
Bad 1600ms
http://hg.mozilla.org/integration/mozilla-inbound/rev/fe381d10084f
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130426 Firefox/23.0 ID:20130426140003
Bad 1400ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/171ed33b6622
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:23.0) Gecko/20130426 Firefox/23.0 ID:20130426140804
Pushlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=fe381d10084f&tochange=171ed33b6622
Slightly improoved by:Bug 865259

Comment 5

[Alice0775 White]

Attachment: the JS code in html script tag

Comment 6

[Alice0775 White]

And
#3 Improved, but still slower than Fx22.
Improved (m-c)
Bad 1400ms:
http://hg.mozilla.org/mozilla-central/rev/b30552dbb013
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20130515 Firefox/24.0 ID:20130515105929
Bad 500ms:
http://hg.mozilla.org/mozilla-central/rev/19cc1efe8097
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20130515 Firefox/24.0 ID:20130515181606
Pushlog:
http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=b30552dbb013&tochange=19cc1efe8097

Improved (m-i)
Bad 1400ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/975667697d0b
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20130514 Firefox/24.0 ID:20130514141530
Bad 500ms:
http://hg.mozilla.org/integration/mozilla-inbound/rev/b880a068345e
Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20130514 Firefox/24.0 ID:20130514143830
Pushlog:
http://hg.mozilla.org/integration/mozilla-inbound/pushloghtml?fromchange=975667697d0b&tochange=b880a068345e
Improved by
bf0bcf4ecf28	Hannes Verschore — Bug 870814 - IonMonkey: Enable native dense int32 when cache isn't monitored, r=jandem

Comment 7

[Till Schneidereit [:till]]

Attachment: Optimize Array#indexOf and Array.lastIndexOf

For me, the test script runs in ~155ms (on an rMBP@2.7Ghz).

With the attached patch, it runs in ~52ms, i.e. 3x as fast. This is exactly on par with Safari 6.0.5, but ~6x as slow as V8 3.18.5.

I'm pretty sure that a lot of the remaining time is empty-loop performance. Changing the testcase to look for a value that's not contained in the array makes the duration go up to ~104ms (as expected). Changing Array#indexOf to not do anything in the main loop makes the test take ~54ms. So half of the time spent is just overhead from looping, IINM.

Using --ion-eager makes all times go up by ~10%.

Comment 8

[Till Schneidereit [:till]]

Attachment: Optimize Array#indexOf and Array.lastIndexOf

For me, the test script runs in ~155ms (on an rMBP@2.7Ghz).

With the attached patch, it runs in ~52ms, i.e. 3x as fast. This is exactly on par with Safari 6.0.5, but ~6x as slow as V8 3.18.5.

I'm pretty sure that a lot of the remaining time is empty-loop performance. Changing the testcase to look for a value that's not contained in the array makes the duration go up to ~104ms (as expected). Changing Array#indexOf to not do anything in the main loop makes the test take ~54ms. So half of the time spent is just overhead from looping, IINM.

Using --ion-eager makes all times go up by ~10%.

Comment 9

[Till Schneidereit [:till]]

Nice, bzexp timed out, but still did the export without telling me ...

@jandem, my ability to diagnose the remaining issues here is somewhat limited. Can you take a look at comments 4, 6, and 7 and see if anything sticks out as an obvious source of regression?

Specifically, it looks like bug 501189 should have fixed empty-loop performance, but I'm not seeing that here.

Comment 10

[André Bargull [:anba]]

--ion-eager seems to suffer from missing type information, that means adding `>>> 0` and `+` etc. brings the `array.indexOf(5000,0)` version on a par with `array.indexOf(5000)`.

And I'm not sure whether the attached patch was just meant the show the current shortcomings or as an actual patch. Because if it is the latter, Proxies get in the way. :/

Comment 11

[Till Schneidereit [:till]]

(In reply to André Bargull from comment #10)
> And I'm not sure whether the attached patch was just meant the show the
> current shortcomings or as an actual patch. Because if it is the latter,
> Proxies get in the way. :/

Can you explain what you mean by that?

Comment 12

[André Bargull [:anba]]

A Proxy with a "has" trap can observe the missing "in" operation:
---
js> p = new Proxy(["eins","zwei","drei"], {has: (t,pk) => {print("has: "+pk); return pk in t}, get:(t,pk) => t[pk]})
["eins", "zwei", "drei"]
js> p.indexOf("zwei")
has: 0
has: 1
1
---

(Note: the "get" trap is only necessary because `new Proxy([0],{}).length` reports `0` instead of `1` in SpiderMonkey - is that a known limitation/bug?)

Comment 13

[Till Schneidereit [:till]]

Those proxies ...

Thanks for the explanation, that makes a lot of sense. Sadly. Looks like this should be a test in test262: I cribbed the optimization from v8, which will also fail this once they enable direct proxies.

Comment 14

[Till Schneidereit [:till]]

After conferring with jandem and testing in a 32bit shell, things look a bit murky:

With my (now known-wrong) patch, we're as fast as or slightly faster than v8 on 32bit, but still ~6x as slow on 64bit. I have no idea what causes such a huge difference.

Comment 15

[André Bargull [:anba]]

Is there a "is-dense-array" intrinsic for self-hosted code? Because without holes and only data properties on a plain array, you can apply that optimisation and remove the "in" operation. And as mentioned in comment 10, type information is missing.

Comment 16

[Till Schneidereit [:till]]

Oh, right! And the v8 people were smarter than I gave them credit for: they do have such an intrinsic and guard their optimized path by that.

We should have one, too.

Comment 17

[Chris Peterson [:cpeterson]]

This bug is probably the cause of bug 884475 (underscore.js performance regression on lodash.js microbenchmark in Firefox 23).

btw, Chrome is about 10x faster than Firefox on the lodash.js benchmark.

Comment 18

[Jeff Walden [:Waldo]]

(In reply to André Bargull from comment #12)
> (Note: the "get" trap is only necessary because `new Proxy([0],{}).length`
> reports `0` instead of `1` in SpiderMonkey - is that a known limitation/bug?)

Bug 827449 almost certainly.

Comment 19

[Till Schneidereit [:till]]

As it turns out, using external self-hosted JS via MOZ_SELFHOSTEDJS[1] apparently causes some severe deoptimizations. I don't know what happens there, exactly, but when doing a full compile and using the embedded self-hosted code, I get 8ms instead of 52ms.

So, introducing an IsDenseArray intrinsic and adapting the attached patch to use it should get our performance back to where we want it to be.


[1]: https://developer.mozilla.org/en-US/docs/SpiderMonkey/Internals/self-hosting#Testing_self-hosted_code_without_recompiling

Comment 20

[André Bargull [:anba]]

(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #18)
> Bug 827449 almost certainly.

It's bug 895223 for direct proxies, but bug 895223 comment 4 mentions bug 827449. :)

Comment 21

[bhavana bajaj [:bajaj]]

Till, what are the next steps here to resolve this in Fx24 ? Its hard for me to understand how it is impacting real world audience ? Are there any websites that are known to hit this, for this to make it into tracking list as this does not look like a recent regression.

Comment 22

[bhavana bajaj [:bajaj]]

Clearing the tracking flags for now given this is an old regression.Till as discussed via email feel free to renom if needed based on your findings related to comment#21.

Comment 23

[Till Schneidereit [:till]]

Urgh, I'm truly sorry for not following up any earlier - this dropped off my radar again.

That being said, I don't think that the regression is bad enough to uplift a fix. The really bad regression from comment 0 seems to only affect code run from the console. For code run in content scripts, we're a bit slower in 24 and 25, and much faster in 26.

I'm also not convinced that comment 17 is right, because the changes in lodash-benchmark results form version to version don't really map to changes in Array#indexOf performance.

I did file bug 911578 for getting a potential speedup for Array#indexOf and other array extras, but think we don't need to do anything else, here.

Comment 24

[agamemnus]

Here is a benchmark. indexOf is **17.25x** the speed of a manual loop in Firefox 25. In Chrome 31 and IE 10, it is "only" 2x the speed. (?!?)

http://jsperf.com/indexof-versus-manual-array-search

Comment 25

[Till Schneidereit [:till]]

With bug 911578 landed, I get scores of ~4000 vs. ~9400, so the manual version is ~2.3x faster. I'll look into some minor optimizations that should still be possible, but some difference will always be there, because indexOf has to deal with edge cases that your manual code can ignore.

Comment 26

[Guilherme Lima]

On the jsperf I get

Nightly 36
indexOf - 2800
manual - 4300

Chrome 38
indexOf - 5150
manual - 4300

Comment 27

[Till Schneidereit [:till]]

indexOf is now running exactly the same inner loop as an optimal manual version, so it's just as fast as that. I tried a few tricks like unrolling the loop a few times, but nothing improved performance.

On the benchmark from comment 0, we're now at 6ms on my machine, compared to 13ms-16ms for JSC (Safari) and v8 (Chrome).

I'd say we're done here.