11–20 of 147 posts
What would it take for something like this to make it into Postgres?
It would be more likely to show up in something like Apache Arrow which is designed columnar to leverage these sort of tricks
> 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
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?
If you're really taking a microscope to performance, the main hazards would be intermittently using AVX for only a few instructions, because that might lead to the CPU stopping for a few microseconds to turn the power on and off on the functional units. If you're using them heavily the overall thermal situation might cause a core or package-wide clock rate degradation, but if you have a use case for sustained AVX-512 usage this is likely to be a good tradeoff.
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.
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?
Well, to me sounds that C++ std::sort is simply lacking an optimization which can very easy be implemented in next iteration of the compiler/linker. I had high hopes this would be a really breakthrough algorithm, not lack of a simple optimization using some instruction set that compiler/linker didn't implement. If they want, CPU vendors would make an even more awesome and faster instruction set, let's say SIMD2, which would leave this one in the dust.
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.
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.
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.