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

31–40 of 147 posts

Re: Vectorized and performance-portable Quicksort

#31

Post by jart »

wtallis wrote: post #27
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…

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

Re: Vectorized and performance-portable Quicksort

#32

Post by mcronce »

vlovich123 wrote: post #29
Arkanosis wrote: post #15

Earlier quoted context omitted.

Pushing them out of the CPU, I don't know, but some SIMD instruction sets on some CPUs have side effects that can negatively affect the performance of other operations. For example, the use of AVX2 / AVX-512 can cause some Intel CPUs to lower their base frequency, thus reducing the performance of simultaneous operations that are not using SIMD.

Is that still true? I was under the impression that post-Haswell CPUs don’t have that particular issue.

Not for recent hardware - Ice Lake eliminated the throttling on 256b ops (they already didn't exist for certain 256b ops and all smaller ops), and reduced the throttling to almost nothing for 512b ops. Rocket Lake eliminated the throttling for 512b ops.

https://en.wikipedia.org/wiki/Advanced_Vector_Extensions#Dow...

They do use a lot of power (and as a result, generate a lot of heat), so they can still cause thermal throttling, or throttling due to power limits - but there's no more "AVX offset"

Re: Vectorized and performance-portable Quicksort

#33

Post by TontonNestor »

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.

djbsort uses a sorting network, not a quicksort. It is also designed to be in constant time, which is not the case with the linked blog post. So the restrictions are different.

This is not my field, so I can't judge the relevance of this, but the author cites the state of the art. It just seems that djbsort is not the state of the art and therefore does not need to be cited.

I still don't understand the hype around Bernstein, he is quite relevant in cryptography/cryptography implementations but not everything he does is gold.

Re: Vectorized and performance-portable Quicksort

#34

Post by ddorian43 »

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.

It actually is not.

Re: Vectorized and performance-portable Quicksort

#35

Post by janwas »

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.

What exactly should be cited? I had a quick look and djbsort seems to be a constant-time algorithm, presumably a sorting network. They report about 2 GB/s for 768 int32 on 3 GHz Skylake; IIRC our sorting network reaches 3-4 GB/s, but for a smaller input size (256 int32 or int64). Hard to compare directly, but djbsort is likely slower, and the sorting network is anyway a small fraction of the total time in a Quicksort.

Re: Vectorized and performance-portable Quicksort

#37

Post by janwas »

TontonNestor wrote: post #33
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.

djbsort uses a sorting network, not a quicksort. It is also designed to be in constant time, which is not the case with the linked blog post. So the restrictions are different. This is not my field, so I can't judge the relevance of this, but the author cites the state of the art. It just seems that djbsort is not the state of the art and therefore does not need to be cited. I still don't understand the hype around B…

:) FWIW we also use a constant-time sorting network as the base case of the Quicksort recursion, that's a widely used optimization.

Re: Vectorized and performance-portable Quicksort

#38

Post by janwas »

nostrademons wrote: post #23
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.

It's not new within Google either. I remember poking through Jeff Dean's original MapReduce code (written c. 2003) and finding a SIMD-based QuickSort that was the in-memory portion of the external sort algorithm. It looks like this algorithm is interesting in the specifics of how it works, eg. the use of a compress-store instruction for partitioning. The algorithm I mentioned above mostly focused on speeding up compa…

Interesting, I did not know that, thanks for the pointer. There is also an effort underway to update LLVM std::sort to BlockQuicksort, which can use some SIMD instructions similarly to what you describe.

Re: Vectorized and performance-portable Quicksort

#39

Post by janwas »

explaingarlic wrote: post #18
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 whole "stick SIMD into it and compare it with the stdlib" thing is a really common learning trope. Feels more like a portfolio filler, albeit probably not a useless one.

We also compare with state of the art platform-specific code. The interesting thing here is that they turn out to be slower than our approach using portable intrinsics (github.com/google/highway) :)

Re: Vectorized and performance-portable Quicksort

#40

Post by mcronce »

jeffbee wrote: post #22
MontyCarloHall wrote: post #12

Earlier quoted context omitted.

I don’t see any mention in the paper of thermal clock throttling concerns, which can really neuter performance of tools that sustain use of AVX operations over a period of time. For the quick benchmarks presented in the paper, of course it will be faster. What if I’m continuously hammering my CPU with AVX operations? I expect it to severely downclock.

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…

The default AVX offset for Ice Lake is indeed only 100MHz (and it doesn't exist starting with Rocket Lake), but 512b SIMD instructions use a lot of power, and as a result generate a lot of heat - so they certainly can cause thermal throttling or throttling due to power limits
Post reply on HN