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

21–30 of 147 posts

Re: Vectorized and performance-portable Quicksort

#21

Post by hinkley »

MontyCarloHall wrote: post #12
slackerIII wrote: post #5

Earlier quoted context omitted.

The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf

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.

My laptop has been throttling itself for a while, I recently discovered. I had been trying to benchmark some code changes and have given up and am letting the CI machine run them, because my numbers are all over the place and go down with each run.

Re: Vectorized and performance-portable Quicksort

#22

Post by jeffbee »

MontyCarloHall wrote: post #12
slackerIII wrote: post #5

Earlier quoted context omitted.

The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf

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 cores were already active is zero. There is no penalty in most server scenarios.

Re: Vectorized and performance-portable Quicksort

#23

Post by nostrademons »

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 comparisons through the use of SIMD instructions, rather than changing the partitioning part of the QuickSort algorithm itself. Not sure how that compares to djbsort, I didn't see technical details of the algorithm on the page.

Re: Vectorized and performance-portable Quicksort

#24

Post by Denvercoder9 »

VHRanger wrote: post #11
slackerIII wrote: post #9

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

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.

Re: Vectorized and performance-portable Quicksort

#25

Post by jeffbee »

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…

The blog post does seem to be quite explicit about the fact that their contribution is in the field of portability, not novelty.

Re: Vectorized and performance-portable Quicksort

#26

Post by MontyCarloHall »

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…

>On Ice Lake Xeon the penalty for using the AVX-512 features on a single core is -100MHz.

That is a penalty due to licensing [0], not thermal throttling. As I wrote elsewhere, I’ve seen my clockspeed get cut in half across all cores on a physical die when running AVX-heavy operations for a sustained period of time, due to thermal throttling.

[0] https://travisdowns.github.io/blog/2020/08/19/icl-avx512-fre...

Re: Vectorized and performance-portable Quicksort

#27

Post by wtallis »

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 bit strange to describe that in terms of reliability.

Re: Vectorized and performance-portable Quicksort

#28

Post by MontyCarloHall »

kadoban wrote: post #19
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.

That might be an interesting benchmark, but assuming good cooling isn't exactly unreasonable either.

In datacenter blade servers (i.e. on a cloud VM), I’ve noticed up to 50% downclocking due to thermal throttling when running sustained frequent AVX operations.

I’m sure an exotic watercooled setup will fare much better, but those aren’t generally what we run in production.

Re: Vectorized and performance-portable Quicksort

#29

Post by vlovich123 »

Arkanosis wrote: post #15
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?

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.

Re: Vectorized and performance-portable Quicksort

#30

Post by samwillis »

VHRanger wrote: post #11
slackerIII wrote: post #9

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

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

There are various Postgres extensions (such as Citus) that are columnar, so with them it should be possible.
Post reply on HN