Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Vectorized and performance-portable Quicksort

opensource.googleblog.com

Post reply on HN
Print view View original

41–50 of 147 posts

Re: Vectorized and performance-portable Quicksort

#41

Post by akelly »

jart wrote: post #31
wtallis wrote: post #27

Earlier 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.

Intel 10th gen mobile and 11th gen mobile and desktop, excluding Pentium and Celeron, have AVX-512. And all 12th gen have it on the P cores but not the E cores. If the E cores are enabled then AVX-512 is unavailable.

Re: Vectorized and performance-portable Quicksort

#42

Post by mchusma »

janwas wrote: post #36

Author here, happy to discuss.

Very cool work! What do you see as the typical process of getting code like this into use in well known codebases? I'm trying to get a sense of when a typical engineer (operating with higher level language or libraries) might get to take advantage of this.

Thanks for open sourcing!

Re: Vectorized and performance-portable Quicksort

#43

Post by janwas »

jart wrote: post #17

I 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 :)

Re: Vectorized and performance-portable Quicksort

#44

Post by mixedCase »

orlp wrote: post #14

SIMD based sorting isn't new, e.g. djbsort: https://sorting.cr.yp.to/ . I find it strange the paper doesn't cite it or compare to it at all. EDIT: to be fair it does seem that Bramas' first published work on SIMD sorting (that I could find) predates djbsort, https://arxiv.org/abs/1704.08579 . A comparison would still be nice though.

The article acknowledges SIMD based sorting and states what makes this novel.

Re: Vectorized and performance-portable Quicksort

#45

Post by janwas »

jart wrote: post #31
wtallis wrote: post #27

Earlier 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.

I agree AVX-512 is not exactly widespread on client CPUs but as akelly mentions, it does exist (e.g. Icelake).

What we do is dispatch to the best available instruction set at runtime - that costs only an indirect branch, plus somewhat larger binary and longer compile time.

Re: Vectorized and performance-portable Quicksort

#46

Post by gww »

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've found it heard to make the "plunge".

Re: Vectorized and performance-portable Quicksort

#48

Post by wtallis »

jart wrote: post #31
wtallis wrote: post #27

Earlier 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.

Even if AVX512 was entirely constrained to server hardware (it's not), how would it be contrary to the public interest for open-source software to take advantage of those instructions?

Re: Vectorized and performance-portable Quicksort

#49

Post by janwas »

VHRanger wrote: post #6
cbetti wrote: post #4

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? In other words, do you have to be more careful when integrating these wide operators to preserve some resources for other operations?

They do emit a lot of heat, which might actually throttle the CPU overall. But to my knowledge they use different registers, and when properly pipelined they don't hog the CPU cache like unoptimized algorithms that constantly round trip to RAM.

The CPU has a certain upper bound on power, TDP. That limit is independent of whether it is reached by executing scalar code on lots of cores, or SIMD on a few. One little-known fact is that out of order CPUs burn lots of energy just on scheduling instructions, ~10x more than the operation itself. SIMD amortizes that per-instruction overhead over multiple data elements, and actually increases the amount of useful work done per joule. We're talking 5-10x increase in energy efficiency.

Re: Vectorized and performance-portable Quicksort

#50

Post by janwas »

Denvercoder9 wrote: post #24
VHRanger wrote: post #11

Earlier quoted context omitted.

unlikely - postgres stores data row-wise and this assumes sequentially stored columns. They even mention that issue in the blog post. It would be more likely to show up in something like Apache Arrow which is designed columnar to leverage these sort of tricks

The data in indexes is stored columnar by most RDBMSes, as far as I know.

I don't know about "most", but here is a list: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes
Post reply on HN