5 ms·

Show HN: QuadSort, Esoteric Fast Sort

78 points by Exorust 4y ago

tuukkah 4y ago
TLDR: A visualisation of how QuadSort adaptively combines various novel strategies to achieve the best performance on a wide variety of inputs: https://github.com/scandum/quadsort#visualization https://github.com/scandum/quadsort#visualization Benchmarks of how it beats qsort, Timsort, pdqsort etc.: https://github.com/scandum/quadsort#benchmark-quadsort-vs-stdstable_sort-vs-timsort https://github.com/scandum/quadsort#benchmark-quadsort-vs-st... Is it called esoteric just because it's complex?
- seanmcdirmid 4y ago
  It has a lot of moving parts. It is considered esoteric because it would be difficult to put this kind of thing into successful production.
- scandum 4y ago
  Quadsort's author here. This is the first time I've heard quadsort being called esoteric. It isn't much more complex than Timsort. It is however challenging to port ~1000 lines of code that can be tedious to debug. If you make one simple error/typo you could be stuck for hours in debugging hell. Hence I recently published piposort, which is ~150 lines and pretty basic, while still offering excellent performance. Not as good as quadsort, but it could make for a stepping stone in a porting effort. https://github.com/scandum/piposort https://github.com/scandum/piposort
  - tuukkah 4y ago
    Good point, so it's not more esoteric than Timsort which is used in production a lot. With quadsort, fluxsort, piposort etc., you have an impressive coverage of the design space of sorting algorithms!
whiterock 4y ago
looks awesome. making this the default sort would surely save lots of co_2.
- SideQuark 4y ago
  Not if it does lots more memory accesses, which is not clear from the page. For example, mergesort has nicer lower bound than quicksort, but quicksort has significantly better constant value hidden in the O(n log n), so quicksort is much lower energy cost (in general - both can be fiddled with, but if I recall, quicksort is still better after all the shenanigans you can apply). From a quick look at the code, line 248 of quidsort.c looks like an 8 way switch per 4 elements - this will likely destroy branch prediction, making pipeline refills cost significantly more CPU cycles than quicksort or merge sort. The code throughout looks like this type of large branching situations. If you want to save CO2, disregard standard complexity and actually measure energy usage - many things can have nice complexities and hide terrible behavior on modern hardware.
  - tuukkah 4y ago
    > Not if it does lots more memory accesses, which is not clear from the page. They say it reduces comparisons, moves and temporary allocation. To me this sounds like fewer memory accesses, although they note that quicksort can use L1 cache more optimally. > quicksort is still better after all the shenanigans you can apply According to the benchmarks, this is better than the quicksorts (qsort and Timsort). > this will likely destroy branch prediction But this is branchless where it matters, which is confirmed by the benchmarks. I do agree it would be interesting to measure the actual energy efficiency to see how well it matches the benchmark results.
    - scandum 4y ago
      Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood. While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions into 0.84 branch mispredictions. My upcoming release of quadsort 1.1.5.4 will improve that further. This is a difficult topic to comment on for someone who isn't 100% in the know, and I often make incorrect assumptions myself. It would be interesting indeed to get the actual energy efficiency, but quadsort being 2-3x faster than timsort on random data pretty much guarantees it is. I'm not aware of an easy method to measure energy consumption, but it would be a better metric in this day and age. As for mergesort vs quicksort, this is pretty much a draw and it heavily depends on data type and comparison type. Fluxsort so far appears to confirm that a hybrid mergesort/quicksort is the best overall by taking advantage of the strengths of both algorithms. Adaptation is coming along slowly but steadily. Several people have started incorporating my branchless bidirectional merge and branchless stable partition concepts, among other things, as fluxsort contains quite a few novelties. My work on binary searching and array rotations could be even more important to reducing the energy footprint.
plq 4y ago
> WSL 2 gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04) Why not run the benchmarks in an environment that matters? Latest stable gcc is 12 and I wouldn't think anybody runs production code on WSL.
- Twirrim 4y ago
  https://gist.github.com/twirrim/f25fc35939c521a096d64c20eb348960 https://gist.github.com/twirrim/f25fc35939c521a096d64c20eb34... I gave it a quick short, Intel(R) Core(TM) i7-8665U, Ubuntu 22.04, gcc 11.3.0.
- CoolCold 4y ago
  > I wouldn't think anybody runs production code on WSL. I wouldn't be so sure - just couple of days ago, on WSL subreddit was a question on setting it up on Windows Server 2019/2022 and that sounds quite worrying for me, that someone actually _DOES_ it.
  - plq 4y ago
    > someone actually _DOES_ it. Sure, but my point stands: It still doesn't matter as a production platform :) hncat 34568832 | sed "s/runs production code on WSL/cares about WSL as a production platform/g" if you will. edit: https://github.com/plq/hncat https://github.com/plq/hncat :)
- st_goliath 4y ago
  > ... I wouldn't think anybody runs production code on ... famous last words. There ought to be something like rule 34 for software: "If it can conceivably be used in that way, somebody's doing just that in production, somewhere safety critical."
j_not_j 4y ago
Uses the wolfsort benchmark, which uses a time-based seed for the pseudo-random-number generator "rand". These are therefore unreproducible results (for the randomized inputs). The results are very interesting and generally follow the rule that bigger hand-optimized code can be faster code.
- DennisP 4y ago
  Maybe not precisely reproducible, but they ran each test a hundred times so it should be possible to reproduce it well enough in statistical terms.
- tuukkah 4y ago
  In the code it looks like the seed to the benchmark can be provided as the 4th command line argument if necessary: https://github.com/scandum/quadsort/blob/master/src/bench.c#L631 https://github.com/scandum/quadsort/blob/master/src/bench.c#...
sayogo1227 4y ago
Are there any other examples of such hand crafted algorithms that perform better than theoretically best algorithms?

78 points by Exorust 4y ago

TLDR: A visualisation of how QuadSort adaptively combines various novel strategies to achieve the best performance on a wide variety of inputs: https://github.com/scandum/quadsort#visualization https://github.com/scandum/quadsort#visualization Benchmarks of how it beats qsort, Timsort, pdqsort etc.: https://github.com/scandum/quadsort#benchmark-quadsort-vs-stdstable_sort-vs-timsort https://github.com/scandum/quadsort#benchmark-quadsort-vs-st... Is it called esoteric just because it's complex?

seanmcdirmid 4y ago
It has a lot of moving parts. It is considered esoteric because it would be difficult to put this kind of thing into successful production.
scandum 4y ago
Quadsort's author here. This is the first time I've heard quadsort being called esoteric. It isn't much more complex than Timsort. It is however challenging to port ~1000 lines of code that can be tedious to debug. If you make one simple error/typo you could be stuck for hours in debugging hell. Hence I recently published piposort, which is ~150 lines and pretty basic, while still offering excellent performance. Not as good as quadsort, but it could make for a stepping stone in a porting effort. https://github.com/scandum/piposort https://github.com/scandum/piposort
- tuukkah 4y ago
  Good point, so it's not more esoteric than Timsort which is used in production a lot. With quadsort, fluxsort, piposort etc., you have an impressive coverage of the design space of sorting algorithms!

whiterock 4y ago

looks awesome. making this the default sort would surely save lots of co_2.

SideQuark 4y ago
Not if it does lots more memory accesses, which is not clear from the page. For example, mergesort has nicer lower bound than quicksort, but quicksort has significantly better constant value hidden in the O(n log n), so quicksort is much lower energy cost (in general - both can be fiddled with, but if I recall, quicksort is still better after all the shenanigans you can apply). From a quick look at the code, line 248 of quidsort.c looks like an 8 way switch per 4 elements - this will likely destroy branch prediction, making pipeline refills cost significantly more CPU cycles than quicksort or merge sort. The code throughout looks like this type of large branching situations. If you want to save CO2, disregard standard complexity and actually measure energy usage - many things can have nice complexities and hide terrible behavior on modern hardware.
- tuukkah 4y ago
  > Not if it does lots more memory accesses, which is not clear from the page. They say it reduces comparisons, moves and temporary allocation. To me this sounds like fewer memory accesses, although they note that quicksort can use L1 cache more optimally. > quicksort is still better after all the shenanigans you can apply According to the benchmarks, this is better than the quicksorts (qsort and Timsort). > this will likely destroy branch prediction But this is branchless where it matters, which is confirmed by the benchmarks. I do agree it would be interesting to measure the actual energy efficiency to see how well it matches the benchmark results.
  - scandum 4y ago
    Quadsort makes more comparisons than timsort, but it has far better branch prediction for random data and far less overhead under the hood. While a switch might seem bad, in the case of random data quadsort turns 1.5 branch mispredictions into 0.84 branch mispredictions. My upcoming release of quadsort 1.1.5.4 will improve that further. This is a difficult topic to comment on for someone who isn't 100% in the know, and I often make incorrect assumptions myself. It would be interesting indeed to get the actual energy efficiency, but quadsort being 2-3x faster than timsort on random data pretty much guarantees it is. I'm not aware of an easy method to measure energy consumption, but it would be a better metric in this day and age. As for mergesort vs quicksort, this is pretty much a draw and it heavily depends on data type and comparison type. Fluxsort so far appears to confirm that a hybrid mergesort/quicksort is the best overall by taking advantage of the strengths of both algorithms. Adaptation is coming along slowly but steadily. Several people have started incorporating my branchless bidirectional merge and branchless stable partition concepts, among other things, as fluxsort contains quite a few novelties. My work on binary searching and array rotations could be even more important to reducing the energy footprint.

plq 4y ago

> WSL 2 gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04) Why not run the benchmarks in an environment that matters? Latest stable gcc is 12 and I wouldn't think anybody runs production code on WSL.

Twirrim 4y ago
https://gist.github.com/twirrim/f25fc35939c521a096d64c20eb348960 https://gist.github.com/twirrim/f25fc35939c521a096d64c20eb34... I gave it a quick short, Intel(R) Core(TM) i7-8665U, Ubuntu 22.04, gcc 11.3.0.
CoolCold 4y ago
> I wouldn't think anybody runs production code on WSL. I wouldn't be so sure - just couple of days ago, on WSL subreddit was a question on setting it up on Windows Server 2019/2022 and that sounds quite worrying for me, that someone actually _DOES_ it.
- plq 4y ago
  > someone actually _DOES_ it. Sure, but my point stands: It still doesn't matter as a production platform :) hncat 34568832 | sed "s/runs production code on WSL/cares about WSL as a production platform/g" if you will. edit: https://github.com/plq/hncat https://github.com/plq/hncat :)
st_goliath 4y ago
> ... I wouldn't think anybody runs production code on ... famous last words. There ought to be something like rule 34 for software: "If it can conceivably be used in that way, somebody's doing just that in production, somewhere safety critical."

j_not_j 4y ago

Uses the wolfsort benchmark, which uses a time-based seed for the pseudo-random-number generator "rand". These are therefore unreproducible results (for the randomized inputs). The results are very interesting and generally follow the rule that bigger hand-optimized code can be faster code.

DennisP 4y ago
Maybe not precisely reproducible, but they ran each test a hundred times so it should be possible to reproduce it well enough in statistical terms.
tuukkah 4y ago
In the code it looks like the seed to the benchmark can be provided as the 4th command line argument if necessary: https://github.com/scandum/quadsort/blob/master/src/bench.c#L631 https://github.com/scandum/quadsort/blob/master/src/bench.c#...

sayogo1227 4y ago

Are there any other examples of such hand crafted algorithms that perform better than theoretically best algorithms?