4 ms·

@mbostock: Why is there Dart code in the project? Just because that's where you borrowed one of the sort functions from? Thanks for another useful library!

by drewda 15y ago

mbostock 15y ago
Yep. Typed arrays don't have a built-in sort method, and even the built-in array.sort is extremely slow. I ported Dart's dual-pivot quicksort implementation, which reduced the time to sort 1M floats from ~2.5s to ~350ms (timed in Node v0.6.2). https://github.com/square/tesseract/blob/master/src/quicksort.js https://github.com/square/tesseract/blob/master/src/quicksor...
- drewda 15y ago
  Good to know. I'll have to consider switching away from Underscore's sort, which is probably equally slow. By the way, quicksort.js is code you wrote, right? I assume that's too nice and concise to be from the Dart generator...
  - jashkenas 15y ago
    Underscore doesn't have a "sort" apart from the native Array.prototype.sort, but it does have a "sortBy", which is something else entirely.
    - drewda 15y ago
      The sortBy method is just producing an integer array that is then sorted using each browser's implementation of Array.prototype.sort. Is that a proper reading of the code?
      - jashkenas 15y ago
        Bingo. You got it.
  - mbostock 15y ago
    Right; I ported it from the Dart implementation, not from the generated JavaScript.
- jasondavies 15y ago
  For sorting numbers, you might also want to look at Radixsort.js, which takes O(n) time, although it isn't in-place like quicksort: https://github.com/jasondavies/radixsort.js https://github.com/jasondavies/radixsort.js I haven't finished implementing the Float64Array version, but it beats everything else I've compared it with even for relatively small sizes e.g. my benchmark is 65,536 floats and it's already around 2.5x faster than native sort (using Node.js)! Admittedly, Float32Array vs. native sorting of 64-bit floats is not a fair comparison, but you could argue that many applications would get away fine with 32-bit floats anyway. :)
  - jasondavies 15y ago
    Got inspired and it now supports Float64Array. :)

@mbostock: Why is there Dart code in the project? Just because that's where you borrowed one of the sort functions from? Thanks for another useful library!

by drewda 15y ago

@mbostock: Why is there Dart code in the project? Just because that's where you borrowed one of the sort functions from? Thanks for another useful library!

mbostock 15y ago

Yep. Typed arrays don't have a built-in sort method, and even the built-in array.sort is extremely slow. I ported Dart's dual-pivot quicksort implementation, which reduced the time to sort 1M floats from ~2.5s to ~350ms (timed in Node v0.6.2). https://github.com/square/tesseract/blob/master/src/quicksort.js https://github.com/square/tesseract/blob/master/src/quicksor...

drewda 15y ago
Good to know. I'll have to consider switching away from Underscore's sort, which is probably equally slow. By the way, quicksort.js is code you wrote, right? I assume that's too nice and concise to be from the Dart generator...
- jashkenas 15y ago
  Underscore doesn't have a "sort" apart from the native Array.prototype.sort, but it does have a "sortBy", which is something else entirely.
  - drewda 15y ago
    The sortBy method is just producing an integer array that is then sorted using each browser's implementation of Array.prototype.sort. Is that a proper reading of the code?
    - jashkenas 15y ago
      Bingo. You got it.
- mbostock 15y ago
  Right; I ported it from the Dart implementation, not from the generated JavaScript.
jasondavies 15y ago
For sorting numbers, you might also want to look at Radixsort.js, which takes O(n) time, although it isn't in-place like quicksort: https://github.com/jasondavies/radixsort.js https://github.com/jasondavies/radixsort.js I haven't finished implementing the Float64Array version, but it beats everything else I've compared it with even for relatively small sizes e.g. my benchmark is 65,536 floats and it's already around 2.5x faster than native sort (using Node.js)! Admittedly, Float32Array vs. native sorting of 64-bit floats is not a fair comparison, but you could argue that many applications would get away fine with 32-bit floats anyway. :)
- jasondavies 15y ago
  Got inspired and it now supports Float64Array. :)