search

lorenzhs / ssssort

Super Scalar Sample Sort in modern C++
MIT License
20 stars 4 forks source link

Investigate better base case sorters #4

Closed lorenzhs closed 8 years ago

lorenzhs commented 8 years ago

Something from Martin Aumüller's exhaustive investigation of quicksort variants (including multi-pivot) maybe? http://eiche.theoinf.tu-ilmenau.de/quicksort-experiments/ (they're GPL though)

Morwenn commented 8 years ago

You might want to have a look at pattern-defeating quicksort, which uses a new partitioning scheme and a few pattern-breaking schemes that happen to work pretty well on real-world data.

It's zlib licensed if that matters.

lorenzhs commented 8 years ago

Thanks, that looks interesting - I'll have a look

lorenzhs commented 8 years ago

It's about the same as std::sort in most benchmarks, but significantly faster in the last three. Nice! I'll have to look into license compatibility but it looks like it shouldn't be a problem.

Morwenn commented 8 years ago

Actually, there a new branch on pdqsort using a partition function less affected by cache misses. The algorithm is now twice as fast as std::sort on average.

lorenzhs commented 8 years ago

Oh cool it implements blocked quicksort now? I tried that as a base case before (didn't push, the paper authors' implementation is GPLv3), and it definitely makes ssssort faster. On its own its speed is comparable to ssssort (sometimes faster, sometimes not) but without the memory overhead. See https://arxiv.org/abs/1604.06697, they compare to my implementation.

BlockQS is definitely very interesting.

Morwenn commented 8 years ago

Yep, it uses ideas from BlockQuicksort's partition, but still uses its own original tweaks to avoid bad partitions as much as possible.

lorenzhs commented 8 years ago

The pdq branch has this covered now