Show HN: QuadSort, Esoteric Fast Sort

by Exorust • 3 years ago

78 23 3 years ago

tuukkah6• 3 years 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

Benchmarks of how it beats qsort, Timsort, pdqsort etc.: https://github.com/scandum/quadsort#benchmark-quadsort-vs-st...

Is it called esoteric just because it's complex?

seanmcdirmid• 3 years 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.

scandum3• 3 years 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

tuukkah6• 3 years 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• 3 years ago

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

SideQuark4• 3 years 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.

tuukkah6• 3 years 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.

plq2• 3 years 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• 3 years ago

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• 3 years 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.

plq2• 3 years 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 :)

st_goliath• 3 years 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• 3 years 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• 3 years 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.

tuukkah6• 3 years 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#...

sayogo1227• 3 years ago

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

Show HN: QuadSort, Esoteric Fast Sort

Related Stories