18 ms·

*for scar execution. SIMD and GPGPU record-breaking parallel implementations use radix, bitonic, etc.

by alecco 7y ago

anticensor 7y ago
> for scar execution. Do you mean scalar execution?
- alecco 7y ago
  yep
hinkley 7y ago
The thing that always bothers me about these sort tests is that once I got out of college I've hardly ever sorted numbers, either because the data isn't numeric or the API I'm calling does it for me. I'm sorting text, or I'm sorting dates. Or I'm doing a compound sort, where it's dates, then text, then numbers. It's rare to me to see a benchmark where the compare() operation is accounted for. It is not difficult at all for the complexity of the compare() operation to trend toward log(n), causing an algorithm with a tighter upper bound on number of comparisons but high constant overhead to perform better. I presume we can vectorize string comparisons at this point? How would we handle compound sorts with SIMD operations?
- nwallin 7y ago
  Or if I am actually sorting stuff, I'm using the sort provided by the standard library. I don't think I've ever implemented a sort outside of an academic context. Used them plenty of times, but I couldn't imagine not using the standard library. Schools talk about sorting algorithms because it's instructive, not because they're important problems. You can explain the problem in thirty seconds, and even if you explain it badly, everyone will have an intuitive understanding of the problem. Then you can show students intuitive algorithms of insertion sort and selection sort and they'll understand the algorithm. Then you time it. Then you show them weird non intuitive algorithms like heap sort or quicksort and show that they're a ton faster. Not a lot faster, but like way way way faster. Then your students understand they'll need to carefully consider their algorithms and all the ramifications moving forward. If you start a CS101 student with a hard algorithms problem they'll switch majors. And that will be your fault for being a shitty teacher, not their fault for being lazy or dumb.

*for scar execution. SIMD and GPGPU record-breaking parallel implementations use radix, bitonic, etc.

by alecco 7y ago

*for scar execution. SIMD and GPGPU record-breaking parallel implementations use radix, bitonic, etc.

anticensor 7y ago

> for scar execution. Do you mean scalar execution?

alecco 7y ago
yep

hinkley 7y ago

The thing that always bothers me about these sort tests is that once I got out of college I've hardly ever sorted numbers, either because the data isn't numeric or the API I'm calling does it for me. I'm sorting text, or I'm sorting dates. Or I'm doing a compound sort, where it's dates, then text, then numbers. It's rare to me to see a benchmark where the compare() operation is accounted for. It is not difficult at all for the complexity of the compare() operation to trend toward log(n), causing an algorithm with a tighter upper bound on number of comparisons but high constant overhead to perform better. I presume we can vectorize string comparisons at this point? How would we handle compound sorts with SIMD operations?

nwallin 7y ago
Or if I am actually sorting stuff, I'm using the sort provided by the standard library. I don't think I've ever implemented a sort outside of an academic context. Used them plenty of times, but I couldn't imagine not using the standard library. Schools talk about sorting algorithms because it's instructive, not because they're important problems. You can explain the problem in thirty seconds, and even if you explain it badly, everyone will have an intuitive understanding of the problem. Then you can show students intuitive algorithms of insertion sort and selection sort and they'll understand the algorithm. Then you time it. Then you show them weird non intuitive algorithms like heap sort or quicksort and show that they're a ton faster. Not a lot faster, but like way way way faster. Then your students understand they'll need to carefully consider their algorithms and all the ramifications moving forward. If you start a CS101 student with a hard algorithms problem they'll switch majors. And that will be your fault for being a shitty teacher, not their fault for being lazy or dumb.