Vectorized and performance-portable Quicksort

I&#x27;m the co-author of one of the papers referenced in the blogpost, (Fast Quicksort Implementation Using AVX Instructions), we did write the AVX512 code back in 2015, just had nowhere to run it, at least publicly. The paper also very explicitly says that the lookup tables can be instead replaced by the AVX512 compress instructions. The code for that paper is available in <a href="https:&#x2F;&#x2F;github.com&#x2F;vkrasnov&#x2F;avx_qsort" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;vkrasnov&#x2F;avx_qsort</a>

I wonder how fast it is compared to djbsort <a href="https:&#x2F;&#x2F;github.com&#x2F;jart&#x2F;cosmopolitan&#x2F;blob&#x2F;master&#x2F;libc&#x2F;nexgen32e&#x2F;djbsort-avx2.S" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;jart&#x2F;cosmopolitan&#x2F;blob&#x2F;master&#x2F;libc&#x2F;nexgen...</a> and longsort <a href="https:&#x2F;&#x2F;github.com&#x2F;jart&#x2F;cosmopolitan&#x2F;blob&#x2F;e011973593407f576d6e613222a18e04cf19b483&#x2F;libc&#x2F;str&#x2F;longsort.c#L66" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;jart&#x2F;cosmopolitan&#x2F;blob&#x2F;e011973593407f576d...</a> djbsort is outrageously fast for 32-bit ints with avx2 (which unlike avx512 it&#x27;s the avx we can reliably use in open source). But there&#x27;s never been a clear instruction set to use on Intel &#x2F; AMD for sorting 64-bit ints that&#x27;s reliably fast. So if this thing can actually sort 64-bit integers 10x faster on avx2 I&#x27;d be so thrilled.

Looks like djb is giving it a spin: <a href="https:&#x2F;&#x2F;twitter.com&#x2F;hashbreaker&#x2F;status&#x2F;1533201734369103872" rel="nofollow">https:&#x2F;&#x2F;twitter.com&#x2F;hashbreaker&#x2F;status&#x2F;1533201734369103872</a>

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I&#x27;ve found it heard to make the &quot;plunge&quot;.

Author here, happy to discuss.

SIMD based sorting isn&#x27;t new, e.g. djbsort: <a href="https:&#x2F;&#x2F;sorting.cr.yp.to&#x2F;" rel="nofollow">https:&#x2F;&#x2F;sorting.cr.yp.to&#x2F;</a>. I find it strange the paper doesn&#x27;t cite it or compare to it at all.<p>EDIT: to be fair it does seem that Bramas&#x27; first published work on SIMD sorting (that I could find) predates djbsort, <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1704.08579" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1704.08579</a>. A comparison would still be nice though.

I love work like this and SIMD-JSON which vectorizes what &quot;should be&quot; sequential form problems to find massive performance gains

This might interest someone: &quot;Vectorized Operations extension for PostgreSQL&quot;<p><a href="https:&#x2F;&#x2F;github.com&#x2F;postgrespro&#x2F;vops" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;postgrespro&#x2F;vops</a>

This is great, and can definitely improve sort performance in database and big data projects. I can immediately imagine this is a perfect match to my project of columnar processing engine TiFlash (<a href="https:&#x2F;&#x2F;github.com&#x2F;pingcap&#x2F;tiflash" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pingcap&#x2F;tiflash</a>).

Not having played with SIMD much myself, does leveraging these instructions for an intensive operation like a sort push other workloads out of the CPU more aggressively than operating on 32 or 64 bits at a time would?<p>In other words, do you have to be more careful when integrating these wide operators to preserve some resources for other operations?

Man, I was thinking about this problem and came up with some weird solutions.<p>I&#x27;ve actually thought all this stuff has already been solved?<p>Is there a point in still trying to improve efficiency of sorting?<p>I can do that! I&#x27;d love such a challenge if there was a point to it!

What would it take for something like this to make it into Postgres?

Re-implementation of stuff with SIMD is always amazing to me. I have done stuff with SIMD before: 4 element float vector operations; basic arithmetic on arrays of floats.<p>Those are things that are super simple, once you get past the scary mystique of SIMD.<p>It’s stuff like this that should be getting all the witch burning :D

Will browsers start using this code for typed array sorting? Maybe they already do?

Are there instructions for building &amp; reproducing the performance results?

SpaceChem players have known this for years

This works only with integers, right? Then radix sort is gonna be still faster on sufficiently large inputs…

This code is worth a clean assembly port.

If P=NP, it only going to be possible because of vectorizing&#x2F;vectorization.

&gt; By comparison, the standard library reaches 58&#x2F;128&#x2F;117 MB&#x2F;s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers.<p>That&#x27;s pretty disingenuous. The standard implementation is known to be terribly slow because of constraints. They should compare against current state of the art.

Quote: &quot;Today we&#x27;re sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort....&quot; and proceeds to explain about SIMD instructions.<p>Well, to me sounds that C++ std::sort is simply lacking an optimization which can very easy be implemented in next iteration of the compiler&#x2F;linker. I had high hopes this would be a really breakthrough algorithm, not lack of a simple optimization using some instruction set that compiler&#x2F;linker didn&#x27;t implement. If they want, CPU vendors would make an even more awesome and faster instruction set, let&#x27;s say SIMD2, which would leave this one in the dust.