797401 - Array concatenation 9 times slower in Firefox than in Chrome

Status: NEW

(Core :: JavaScript Engine, defect)

Description

[Tobias (:Tobbi) Markus]

This test case tests Array concatenation and push in Chrome and Firefox:
http://jsperf.com/concat-vs-push4

I found Firefox to be 9x slower than Chrome.

Comment 1

[Tobias (:Tobbi) Markus]

Attachment: Test results in Firefox Nightly

Comment 2

[Tobias (:Tobbi) Markus]

Attachment: Test result in Chrome 22.0.1229.79

Comment 3

[Boris Zbarsky [:bzbarsky]]

Are you testing with ion on or off?  I see much slower concat() with ion.

But in any case, see bug 609896.

Comment 4

[Tobias (:Tobbi) Markus]

I am testing with javascript.options.ion.content;true. Let me re-test with ion shut off.

Comment 5

[Tobias (:Tobbi) Markus]

Attachment: Test Result in Firefox Nightly; Ion off

Comment 6

[Tobias (:Tobbi) Markus]

Indeed, with Ion disabled, I get 3x the speed I get with Ion enabled.

Comment 7

[Jan de Mooij [:jandem]]

Yeah JM+TI has a fast-path for array.concat on two dense arrays... We should port this to Ion.

I ported the array.push, array.pop and array.shift paths, concat is the last one we still have to inline.

Comment 8

[Till Schneidereit [:till]]

I re-tested this, with promising, but mixed, results:
Nightly is 2x-4x as fast as Chrome Canary for all push tests, and roughly 50% faster for concat 10. Concat 100 is about as fast as Canary, but from there, it all goes downhill: 7x slower for concat 1000, 23x slower for concat 10,000.

Terrence, I assume that this has to do with memory allocation and not so much with the speed we execute the concat operation at?

Comment 9

[Terrence Cole [:terrence]]

Use of realloc on anything larger than a few KiB is pretty much guaranteed to be essentially O(1) these days. There is probably a log(N/big) traversal to update the page tables somewhere in the kernel, but never a copy. This sort of catastrophic slowdown with scale is almost certainly concat and not the allocator.

Comment 10

[Mike Hommey [:glandium]]

(In reply to Terrence Cole [:terrence] from comment #9)
> Use of realloc on anything larger than a few KiB is pretty much guaranteed
> to be essentially O(1) these days.

If you're talking about jemalloc, that's not true.

Comment 11

[Terrence Cole [:terrence]]

(In reply to Mike Hommey [:glandium] from comment #10)
> (In reply to Terrence Cole [:terrence] from comment #9)
> > Use of realloc on anything larger than a few KiB is pretty much guaranteed
> > to be essentially O(1) these days.
> 
> If you're talking about jemalloc, that's not true.

Ah, so it is! Their explanation seems sound too.

Maybe it would make sense for us to move to a page allocator for large elements vectors so we can use rmemap efficiently ourself? I'll do some profiling once my current queue is a bit lower.

Comment 12

[Mike Hommey [:glandium]]

mremap is also linux-only. That wouldn't make realloc O(1) on mac and windows.

Comment 13

[Terrence Cole [:terrence]]

(In reply to Mike Hommey [:glandium] from comment #12)
> mremap is also linux-only. That wouldn't make realloc O(1) on mac and
> windows.

Wow, I assumed there would be a direct equivalent on both systems, given the obvious advantage of having a free realloc.

Comment 14

[Terrence Cole [:terrence]]

Even if we can't use the realloc trick, we can tune our own realloc growth algorithms to do better here still.