performance - Fastest way to sort 32bit signed integer arrays in JavaScript?

Question

_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
*/
function radixSort(intArr) {
    var cpy = new Int32Array(intArr.length);
    var c4 = [].concat(_radixSort_0); 
    var c3 = [].concat(_radixSort_0); 
    var c2 = [].concat(_radixSort_0);
    var c1 = [].concat(_radixSort_0); 
    var o4 = 0; var t4;
    var o3 = 0; var t3;
    var o2 = 0; var t2;
    var o1 = 0; var t1;
    var x;
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        t3 = (intArr[x] >> 8) & 0xFF;
        t2 = (intArr[x] >> 16) & 0xFF;
        t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
        c4[t4]++;
        c3[t3]++;
        c2[t2]++;
        c1[t1]++;
    }
    for (x=0; x<256; x++) {
        t4 = o4 + c4[x];
        t3 = o3 + c3[x];
        t2 = o2 + c2[x];
        t1 = o1 + c1[x];
        c4[x] = o4;
        c3[x] = o3;
        c2[x] = o2;
        c1[x] = o1;
        o4 = t4;
        o3 = t3;
        o2 = t2;
        o1 = t1;
    }
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        cpy[c4[t4]] = intArr[x];
        c4[t4]++;
    }
    for(x=0; x<intArr.length; x++) {
        t3 = (cpy[x] >> 8) & 0xFF;
        intArr[c3[t3]] = cpy[x];
        c3[t3]++;
    }
    for(x=0; x<intArr.length; x++) {
        t2 = (intArr[x] >> 16) & 0xFF;
        cpy[c2[t2]] = intArr[x];
        c2[t2]++;
    }
    for(x=0; x<intArr.length; x++) {
        t1 = (cpy[x] >> 24) & 0xFF ^ 0x80;
        intArr[c1[t1]] = cpy[x];
        c1[t1]++;
    }
    return intArr;
}

EDIT:

So far, the best/only major optimization brought to light is JS typed arrays. Using a typed array for the normal radix sort's shadow array has yielded the best results. I was also able to squeeze a little extra out of the in place quick sort using JS built in stack push/pop.

---

latest jsfiddle benchmark

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSort(intArr): 172 ms
radixSortIP(intArr): 1738 ms
quickSortIP(arr): 661 ms
200k
radixSort(intArr): 18 ms
radixSortIP(intArr): 26 ms
quickSortIP(arr): 58 ms

It appears standard radix sort is indeed king for this work-flow. If someone has time to experiment with loop-unrolling or other modifications for it I would appreciate it.

I have a specific use case where I'd like the fastest possible sorting implementation in JavaScript. There will be large (50,000 - 2mil), unsorted (essentially random), integer (32bit signed) arrays that the client script will access, it then needs to sort and present this data.

I've implemented a fairly fast in place radix sort and in place quick sort jsfiddle benchmark but for my upper bound array length they are still fairly slow. The quick sort performs better on my upper bound array size while the radix sort performs better on my lower bound.

defaultSort is the built-in JavaScript array.sort with an integer compare function

Intel C2Q 9650, 4GB, FireFox 3.6
2mil
radixSortIP(intArr): 5554 ms
quickSortIP(arr): 1796 ms
200k
radixSortIP(intArr): 139 ms
quickSortIP(arr): 190 ms
defaultSort(intArr): 354 ms

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSortIP(intArr): 990 ms
quickSortIP(arr): 882 ms
defaultSort(intArr): 3632 ms
200k
radixSortIP(intArr): 28 ms
quickSortIP(arr): 68 ms
defaultSort(intArr): 306 ms

---

Questions

• Is there a better implementation of any sorting algorithm that would meet my use case/needs?
• Are there any optimizations that can be made to my in place radix/quick sort implementations to improve performance?
• • Is there an efficient way to convert my in place radix sort from a recursive to iterative function? Memory and execution speed.

---

Goal

• I am hoping these answers will help me get ~20-30% performance improvement in my benchmark test.

---

Clarifications/Notes

• "DEFINE FAST" I would prefer a general case where it runs well on all modern browsers, but if there is a browser specific optimization that makes a significant improvement that may be acceptable.
• The sorting COULD be done server side, but I'd prefer to avoid this because the JS app may become a standalone (paired with some off the shelf proprietary app that will stream sensor data to a file).
• JavaScript may not be the best language for this but it's a requirement.
• I've already asked this question https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript an incorrect answer was up-voted and the question was closed.
• I've attempted using multiple browser window instances as a makeshift multi-threading; it didn't pan out. I'd be interested in useful info regarding spawning multiple windows for concurrency.

Answer 1

I've tested typed arrays, the QSIP version seems to be good in modern browsers:

2 000 000 elements

          QSIP_TYPED | RDXIP_TYPED |  QSIP_STD | RDXIP_STD
----------------------------------------------------------
Chrome  |    300          1000          600        1300
Firefox |    550          1500          800        1600    

http://jsfiddle.net/u8t2a/35/

Support (source: http://caniuse.com/typedarrays):

 IE 10+   |   FF 4+  |  Chrome 7+  |  Safari 5.1+  |  Opera 11.6+