StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFastest way to sort 32bit signed integer arrays in JavaScript?
text
Body
copied!<pre><code>_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; } </code></pre> <h3>EDIT:</h3> <p>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.</p> <hr> <p><a href="http://jsfiddle.net/u8t2a/61/" rel="nofollow noreferrer">latest jsfiddle benchmark</a></p> <pre><code>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 </code></pre> <p><strong>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.</strong> </p> <p>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. </p> <p>I've implemented a fairly fast in place radix sort and in place quick sort <a href="http://jsfiddle.net/u8t2a/10/" rel="nofollow noreferrer">jsfiddle benchmark</a> 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.</p> <pre><code>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 </code></pre> <hr> <h2>Questions</h2> <ul> <li>Is there a better implementation of any sorting algorithm that would meet my use case/needs?</li> <li>Are there any optimizations that can be made to my in place radix/quick sort implementations to improve performance?</li> <li><ul> <li>Is there an efficient way to convert my in place radix sort from a recursive to iterative function? Memory and execution speed.</li> </ul></li> </ul> <hr> <h2>Goal</h2> <ul> <li>I am hoping these answers will help me get ~20-30% performance improvement in my benchmark test.</li> </ul> <hr> <h2>Clarifications/Notes</h2> <ul> <li>"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.</li> <li>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).</li> <li>JavaScript may not be the best language for this but it's a requirement.</li> <li>I've already asked this question <a href="https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript">https://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript</a> an incorrect answer was up-voted and the question was closed.</li> <li>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.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload