487599 - NativeArray: improve performance of sort([fn]) using java's Arrays.sort(..)

Status: RESOLVED FIXED

(Rhino Graveyard :: Core, defect)

Description

[Marc]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.8) Gecko/2009032711 Ubuntu/8.04 (hardy) Firefox/3.0.8
Build Identifier: 

NativeArray currently implement sort by itself whereas it could make usage of java.util.Arras#sort as done is provided patch.

With following code:

var t = [1, 5, 2, 1, 9];
var nbComp = 0;
var compare = function(x, y) { print((nbComp++) + ": " + x + "<>" + y); return x - y; };
t.sort(compare);

current implementation needs to call the compare function 11 times:
--- output with current implementation ---
0: 9<>1
1: 9<>5
2: 2<>9
3: 9<>1
4: 5<>1
5: 5<>1
6: 2<>5
7: 5<>1
8: 1<>1
9: 2<>1
10: 2<>1
11: 1<>1

with provided patch, the compare function is called only 6 times!
--- output with patched implementation using java's Array.sort ---
0: 1<>5
1: 5<>2
2: 1<>2
3: 5<>1
4: 2<>1
5: 1<>1
6: 5<>9

Ok, this example is not necessary representative but my guess is that a JDK method like Arras.sort contains when not all necessary optimizations, surely more than Rhino's implementation.


Reproducible: Always

Comment 1

[Marc]

Attachment: Patch using Arrays.sort for NativeArray.sort

This patch removes all custom sort logic to use JDK's Arrays.sort method. With this patch applied, I get exactly the same errors running ant junit-all than without the patch.

Note:
I've removed handling of arrays with length greater than Integer.MAX_VALUE first because I think that it is not a real use case and second because it is not tested by any test and a feature that is not tested doesn't exist! ;-)

Comment 2

[Attila Szegedi]

Overall, it looks good to me. Few minor points:

1. removing handling of arrays with length equal to Integer.MAX_VALUE should be okay. Maximum length for JS native arrays is 2^32-1 anyway. It's true that sort() function can be transferred to another objects as well, but even if it were, the definition of sort is such that it only operates on ToUInt32(this.[[Get]]("length")).

2. The testing for undefined values should also be performed in the case where you don't have a comparator function.

3. storing the Undefined.instance and Scriptable.NOT_FOUND in a local variable won't really help performance. The anonymous inner Comparator class will have them stored in compiler-emitted synthetic instance fields, so they'll be accessed using GETFIELD JVM instruction on the comparator object, instead of a GETSTATIC on Undefined and Scriptable classes - not much if any performance boost. They certainly won't be accessed as local variables with ALOAD, if that's what your intent was...

Comment 3

[Marc]

2. You're right.

3- It just a rest of the old code that I haven't completely clean up. I'm quite sure as well that it has no impact on the performance: the JVM is surely able to make the best decision here.

I'll make the tow changes and upload a new version of the patch.

Comment 4

[Marc]

Attachment: the same with the minor improvements suggested by Attila

Comment 5

[Norris Boyd]

You shouldn't have to copy into a working array if "denseOnly" is true.

It would be nice to have the code work for sparse arrays. That appears to be the intent of the heapsort code (I didn't write it), but it doesn't appear to work from my brief testing, so I'm fine with removing it.

Thanks for the contribution.

Comment 6

[Attila Szegedi]

(In reply to comment #5)
> 
> It would be nice to have the code work for sparse arrays.

The existing heapsort code was also first copying a sparse array to a temporary array, didn't it? In this regard at least, the new code is not any worse :-)

It would be nice though if java.util.Collections.sort(List) weren't implemented in terms of Arrays.sort() (it too copies the list to an array first), so we could then delegate sorting of sparse arrays to java.util.Collections.sort(List) with a List adapter... 

BTW, did you hear that Josh Bloch checked in an implementation of timsort as a replacement for mergesort for Arrays.sort() in Java 7? See <http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124>

Comment 7

[Norris Boyd]

Having the code work efficiently with very sparse arrays would be nice but shouldn't hold up this change. I hadn't heard of timsort, sounds promising.

Comment 8

[Marc]

Ping!

What about applying this patch as you seem to agree on it.

Comment 9

[Norris Boyd]

Committed, thanks.

Checking in src/org/mozilla/javascript/NativeArray.java;
/cvsroot/mozilla/js/rhino/src/org/mozilla/javascript/NativeArray.java,v  <--  NativeArray.java
new revision: 1.101; previous revision: 1.100
done