Vectorized and performance-portable Quicksort

I've read parts 1-5, there doesn't seem to be a part6. Thanks again for the link, it is regrettable that there is duplication of effort. His approach is quite similar to ours (including HeapSort, sorting network, unrolled in-place partition), and re-invents what he calls "double-pumped partitioning" (introduced by Bramas).

Copying the blog post to arxiv and citing some related work so it comes up in alerts and cited-by searches would [have made/make] this good work visible to a wider circle, including the algorithms community.

It's nice to see a C++ version, this will be easier for me to benchmark, and it also seems to support other built-in types now, as well as AVX2+AVX-512 (though not other platforms). A quick list of differences based on reading the blog:

* Nifty idea for simplifying the branch in partition. (We also found that branchless code is worse)

* Major effort to make all reads vector-aligned. This could make a difference especially on AVX-512. I had tried two variants but it was difficult to make this safe for asan (no out of bounds reads allowed).

* The lookup table is 2KB, which could be halved using 32-bit broadcast + variable shift instead of PDEP.

* The sorting network seems to be half the size and bitonic. I haven't yet compared the number of permute instructions (not obvious from the source because it's generated).

* The pivot is only a median of three. We use a much larger sample.

Thanks for your post! Let me explain my problem, which fits right to it. It works as an example, too.

So, in freepascal there's some subpar pattern matching/string search function. It annoyed me so greatly, I've started researching into the "state of the art" and apparently they're all crap. My fixed size pattern matching solution fits into less than 256 bytes, not counting setup code, which is minimal.

And here start the problems for me, because I have no way of actually comparing my solution to "the state of the art", because "the state of the art" doesn't offer me downloadable, compiled benchmarks I can just run to compare stuff to my own and learning a new language (like, i don't speak C and certainly never will), installing a compiler, getting through all the walls that inevitably be in my way to getting it to run, etc ... totally breaks my timebudget and thus I drop the problem.

Basically, what I'm looking for is:

Give me a problem that's worth tackling, with a defined set of parameters and a compiled solution I can compare my own against and I will beat it eventually. I've tried doing this on my own, but that's just a big no-go on many levels, so I'm dependent on someone handing something to me.

Like ... the QuickSort. I have no way of comparing my potential own solution against "the state of the art", which is - as far as I know - pretty much all that's holding me back.

Response here because I'm not on Twitter: https://github.com/google/highway/issues/736

In short, what is being compared is O(1) djbsort sorting network, vs our full quicksort with pivot sampling, partitioning, then sorting network.

This is because our sorting network size is 16 * elements_per_vector i.e. 128 in this configuration.

Yes, this is discussed in section 4.2 of our paper: https://arxiv.org/pdf/2205.05982.pdf

In short, it turns out not to help for single core with vectors, but a few initial passes of ips4o (with 64..256-way partitioning) is faster for parallel sorts.