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.

Are you testing with ion on or off? I see much slower concat() with ion. But in any case, see bug 609896.

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

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

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.

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?

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.

(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.

(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.

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

(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.

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