Are there instructions for building & reproducing the performance results?
Vectorized and performance-portable Quicksort
91–100 of 147 posts
Re: Vectorized and performance-portable Quicksort
#92Author here, happy to discuss.
Well done, Jan!
Re: Vectorized and performance-portable Quicksort
#93I'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 https://github.com/vkrasnov/avx_qsort
Re: Vectorized and performance-portable Quicksort
#94Earlier quoted context omitted.
On 12th gen they disabled it on the P cores too even with E cores disabled with a microcode update. A lot of newer systems don't have access to the older microcode, and microcode doesn't typically let you downgrade.
There are workarounds for downgrading microcode, because the CPU itself doesn't actually have non-volatile storage for microcode updates and relies on the motherboard firmware to upload updates on each boot (and motherboard firmware can often be downgraded, possibly after changing a setting to allow that). Which is probably why Intel has changed to disabling AVX512 using fuses in more recently manufactured Alder Lake…
My point with "a lot of newer systems" was that there are motherboards now that completely lack a version of their firmware with the microcode that allows avx-512. There's nothing to downgrade to without an exploit to allow making your own firmware images with mixed and matched components.
Re: Vectorized and performance-portable Quicksort
#95Earlier quoted context omitted.
> it's the avx we can reliably use in open source I'm not sure what you mean by that. You can't assume the presence of AVX or AVX2 without explicitly checking for it, because Intel was still disabling those features on new low-end Pentium and Celeron parts at least a recently as Comet Lake (2020). Sure, AVX2 support is much more widespread than AVX512 support, but that has nothing to do with open-source and it's a bi…
Some of us like to think of ourselves writing open source as serving the public interest. It's hard to do that if you're focusing on an ISA the public doesn't have. I haven't seen any consumer hardware that has AVX512.
Lots of consumer hardware has AVX512 (I have an 11th gen Intel laptop CPU that has it).
Regardless, Clang and GCC both support function multi-versioning where you supply multiple versions of a function and specify which CPU features each implementation needs, and the best version of the function will be selected at runtime based on the results of cpuid. For example, you can use this to write a function that uses no vector instructions, SEE, AVX2, or AVX512 and all versions will be compiled into the executable and the best version you can actually use will be selected at runtime. This is how glibc selects the optimal version of functions like memset/memcpy/memcmp, as there are vector instructions that significantly speed these functions up.
There's an LWN article about the feature if you're curious how it works: https://lwn.net/Articles/691932/
Re: Vectorized and performance-portable Quicksort
#96Looks like djb is giving it a spin: https://twitter.com/hashbreaker/status/1533201734369103872
Re: Vectorized and performance-portable Quicksort
#97Will browsers start using this code for typed array sorting? Maybe they already do?
Sorting integers is actually rare in practice, esp. not very useful for a browser.
The method exists. They could make it faster without breaking anything.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
Re: Vectorized and performance-portable Quicksort
#98I wonder how fast it is compared to djbsort https://github.com/jart/cosmopolitan/blob/master/libc/nexgen... and longsort https://github.com/jart/cosmopolitan/blob/e011973593407f576d... djbsort is outrageously fast for 32-bit ints with avx2 (which unlike avx512 it's the avx we can reliably use in open source). But there's never been a clear instruction set to use on Intel / AMD for sorting 64-bit ints that's reliably…
Yes, we can sort 64-bit ints. The speedup on AVX2 is roughly 2/3 of the 10x we see on AVX-512. Longsort appears to be an autovectorized sorting network. That's only going to be competitive or even viable for relatively small arrays (thousands). See comments above on djbsort. Why not use whichever AVX the CPU has? Not a problem when using runtime dispatch :)
What about performance-per-watt?
Re: Vectorized and performance-portable Quicksort
#99Earlier quoted context omitted.
On Ice Lake Xeon the penalty for using the AVX-512 features on a single core is -100MHz. If we pessimistically use the slowest part Intel sells, that is a 5% performance penalty (2% on their fastest parts). The speedup from this work is 40-60% compared to AVX2. So you'd be a fool to take the side of the folk myth. AVX-512 works. By the way the performance penalty for using AVX-512 on multiple cores when the multiple…
It's the transition that kills you. Are you doing this full time?
My full-time thing is more search-y and takes tens of milliseconds so I'm not really sweating power state transitions that take a few micros.
Re: Vectorized and performance-portable Quicksort
#100Looks like djb is giving it a spin: https://twitter.com/hashbreaker/status/1533201734369103872
And he shat all over Google yet again