Vectorized and performance-portable Quicksort
opensource.googleblog.com
Vectorized and performance-portable Quicksort
1–10 of 147 posts
Re: Vectorized and performance-portable Quicksort
#2I love work like this and SIMD-JSON which vectorizes what "should be" sequential form problems to find massive performance gains
Re: Vectorized and performance-portable Quicksort
#3> By comparison, the standard library reaches 58/128/117 MB/s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers.
That's pretty disingenuous. The standard implementation is known to be terribly slow because of constraints. They should compare against current state of the art.
Re: Vectorized and performance-portable Quicksort
#4Not 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?
Re: Vectorized and performance-portable Quicksort
#5> By comparison, the standard library reaches 58/128/117 MB/s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers. That's pretty disingenuous. The standard implementation is known to be terribly slow because of constraints. They should compare against current state of the art.
The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf
Re: Vectorized and performance-portable Quicksort
#6Not 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.
Re: Vectorized and performance-portable Quicksort
#7> By comparison, the standard library reaches 58/128/117 MB/s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers. That's pretty disingenuous. The standard implementation is known to be terribly slow because of constraints. They should compare against current state of the art.
Which they did and showed in the previous sentence. You cannot possibly have missed that.
Re: Vectorized and performance-portable Quicksort
#8> By comparison, the standard library reaches 58/128/117 MB/s on the same CPU, so we have managed a 9-19x speedup depending on the type of numbers. That's pretty disingenuous. The standard implementation is known to be terribly slow because of constraints. They should compare against current state of the art.
Also disingenuous to claim they don't make that comparison when it's literally the sentence before the one you quoted.
Re: Vectorized and performance-portable Quicksort
#9What would it take for something like this to make it into Postgres?
Re: Vectorized and performance-portable Quicksort
#10[deleted]