What would it take for something like this to make it into Postgres?
See commment: https://news.ycombinator.com/item?id=31624451
Vectorized and performance-portable Quicksort
81–90 of 147 posts
Re: Vectorized and performance-portable Quicksort
#82Author here, happy to discuss.
I just wanted to say awesome job, I'm going to use it, ignore all the ignorant SIMD haters;0
Re: Vectorized and performance-portable Quicksort
#83I love work like this and SIMD-JSON which vectorizes what "should be" sequential form problems to find massive performance gains
Another one if you enjoy this sort of thing like me is Raph Levien's work on the stack monoid; this [1] blog post and this [2] ArXiV paper are great places to look.
[1]: https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html [2]: https://arxiv.org/abs/2205.11659
Re: Vectorized and performance-portable Quicksort
#84Not 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?
Generally yes to the first question, no to the second.
If you want your code to have low perturbance on other concurrent work done by the system, implementing it in a inefficient way doesn't usually help with that goal, since then your code will just be executing all the time because it takes a long time to finish. And you still won't have good control of the execution resources compared to using normal tools like OS scheduling policies to address the goal.
Re: Vectorized and performance-portable Quicksort
#85Author here, happy to discuss.
Regarding columnar databases, is there an optimal data structure in between storing data as rows and storing data as columns that would make it fast to sort and filter by either dimension? Some mix of B-trees or interval trees?
Re: Vectorized and performance-portable Quicksort
#86> 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.
My bad. Apologies.
Re: Vectorized and performance-portable Quicksort
#87Author here, happy to discuss.
Interesting post and paper, thanks!
Sometimes the state of the art is not found in another paper but somewhere else, e.g,. there is vxsort by Dan Shechter (damageboy):
https://github.com/damageboy/vxsort-cpp/tree/master
He uses a similar approach and while I'm not sure how it compares to the older Blacher et al version, I expect it to be in the ballpark.
He's written an excellent series of blog posts on the design & implementation:
Re: Vectorized and performance-portable Quicksort
#88Author here, happy to discuss.
No post body was provided.
Re: Vectorized and performance-portable Quicksort
#89Man, I was thinking about this problem and came up with some weird solutions. I've actually thought all this stuff has already been solved? Is there a point in still trying to improve efficiency of sorting? I can do that! I'd love such a challenge if there was a point to it!
Sorting is one of a few things that computers spend so much time doing, even a relatively small improvement over that state of the art can have a big impact.
On the one hand this means if you can come up with a better way to do it in some case that's awesome and could be very valuable. On the other hand it means a lot of people have thought pretty hard about it and the next improvement may be hard to come up with unless you pick a tight enough subset of the problem.
Definitely go for it though :)
Re: Vectorized and performance-portable Quicksort
#90Earlier quoted context omitted.
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.
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 CPUs.