374740 - Array.join() is slow for large arrays - can easily be made much better - solution attached

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Duncan Loveday]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a3pre) Gecko/20070319 Minefield/3.0a3pre
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9a3pre) Gecko/20070319 Minefield/3.0a3pre

The performance of Array.join() is very poor for large arrays. This can be massively improved by re-defining Array.prototype.join as in the attached test case. 

Reproducible: Always

Steps to Reproduce:
1. Open the attached fastjoin.html in Firefox
2.
3.
Actual Results:  
Two timings are reported via alert boxes, one with the standard join and one with the proposed replacement join. The time for the replacement join is much quicker.

Expected Results:  
Ideally the standard Array.join() operation would be at least as quick as the replacement, either by adopting it directly or some equivalent or better approach.

IE6 runs the test case in near zero time - I reckon they must implement Array.join() natively, it is fantastically quick.

Firefox normal a.join() is about the same as "var str=''; for (var n=0;n<a.length;n++) str+=a[n];"

This can easily be bettered even at the javascript level using the attached code but is still much slower than IE6. We don't like things that run better in IE (and there are not many of them)...

Comment 1

[Duncan Loveday]

Attachment: test HTML source

Comment 2

[Duncan Loveday]

Perhaps I should have explained: The attached code works by recursively cutting a large array (greater than a threshold size) in half, joining the two halves and concatenating the results. Therefore, performance for small arrays should be the same as the native code plus a tiny overhead for the test on the length and the fact that the native call is wrapped in another function.

Comment 3

[Igor Bukanov]

I suspect the reason for that bad behavior is that we realloc for each element in the join implementation the buffer for the resulting string. I think if we just prealocate an array for elements, convert them to strings and then build the result using single malloc, the code should be on pair with MSIE implementation.

Comment 4

[Duncan Loveday]

It sounds almost TOO easy....

Don't know what the priority of this would be. It might be worth noting that using a construct like [value1, value2, value2, .....].join("") is something people often do in IE since it is orders of magnitude faster doing it the conventional way (str=value1+value2+value3; or str+=value; str+=value2; str+=value3;). So there might be significant numbers of people who would benefit from a fix in this area, I am certainly one.

Comment 5

[Aiko]

join() being too slow and realloc happy is already covered by bug 200505...

Comment 6

[Duncan Loveday]

Can I get a build with that patch in and test it ?

Bug 200505 talks about 35% improvements whereas I get at least 1000% even with my javascript change and i.e. is orders of magnitude faster than even this. But then again I've deliberately put huge arrays in the test case.

Comment 7

[Igor Bukanov]

I will update the patch in bug 200505 and for now make this bug to depend on it to verify the examples here.

Comment 8

[Igor Bukanov]

I am not working on the bug.

Comment 9

[Duncan Loveday]

Hey - what did you guys do ?

Look at the numbers below

                Native join        With my prototype
FF2.0.0.11      13s                782ms
FF3 Beta 3      12.8s              540ms
Current trunk   70ms               175ms

I think you could say that's WFM !

Comment 10

[Brian Crowder]

This is fixed by shavarrays, most likely.  Bug 322889