13 ms·

Vectorized and performance-portable Quicksort

460 points by slackerIII 4y ago

VHRanger 4y ago
I love work like this and SIMD-JSON which vectorizes what "should be" sequential form problems to find massive performance gains
- charcircuit 4y ago
  Any nonsequential problem can be divided into sequential subprobolems.
- singhrac 4y ago
  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 https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html [2]: https://arxiv.org/abs/2205.11659 https://arxiv.org/abs/2205.11659
alecco 4y ago
> 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.
- slackerIII 4y ago
  The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf https://arxiv.org/pdf/2205.05982.pdf
  - MontyCarloHall 4y ago
    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.
    - kadoban 4y ago
      That might be an interesting benchmark, but assuming good cooling isn't exactly unreasonable either.
      - MontyCarloHall 4y ago
        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.
    - hinkley 4y ago
      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.
      - bee_rider 4y ago
        One option would be to go into BIOS and see if there's some way of just locking your CPU to one of the lower clock speeds. This will give lower benchmarking numbers of course, but at least they should be fairly stable. (in Linux, it also often possible to tinker with frequencies while the system is running). Even on a desktop this sort of thing is sometimes necessary, for example my CPU has different clock speeds depending on how many processors are running, so I have to lock it to the all-core clock if I want to see proper parallel speedups. This might be annoying for day-to-day usage (although, CPUs really are insanely performant nowadays so maybe it will not be too bad).
- Rizz 4y ago
  Which they did and showed in the previous sentence. You cannot possibly have missed that.
- throw-away_42 4y ago
  Also disingenuous to claim they don't make that comparison when it's literally the sentence before the one you quoted.
  - alecco 4y ago
    My bad. Apologies.
cbetti 4y ago
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?
- VHRanger 4y ago
  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.
  - janwas 4y ago
    The CPU has a certain upper bound on power, TDP. That limit is independent of whether it is reached by executing scalar code on lots of cores, or SIMD on a few. One little-known fact is that out of order CPUs burn lots of energy just on scheduling instructions, ~10x more than the operation itself. SIMD amortizes that per-instruction overhead over multiple data elements, and actually increases the amount of useful work done per joule. We're talking 5-10x increase in energy efficiency.
  - saltcured 4y ago
    Right, though your use of the terms "different registers" and "properly pipelined" is quite nuanced for a non-specialist. It leaves a lot to the imagination or prior experience! If it is a compute-heavy code that was spilling to a stack and now can fit in the SIMD registers, there could be a speed up with less memory traffic. This is analogous to a program's working set either fitting in RAM or spilling to swap while it runs, but at a different level of the memory hierarchy. In the extreme case, your working set could be a fixed set of variables in expensive loops for some sequential algorithm, and so the compiler register placement ability and number of registers available could be the difference between effectively O(1) or O(n) memory accesses with respect to the number of compute steps. Of course, you can find such transitions between registers/L1 cache, L1/L2 cache, L2/L3 cache (if present), local/remote RAM (for modern NUMA machines), etc. This happens as you transition from a pure CPU-bound case to something with bigger data structures, where the program focus has to move to different parts of the data to make progress. Naively holding other things equal, an acceleration of a CPU-bound code will of course mean you churn through these different data faster, which means more cache spills as you pull in new data and have to displace something else. Going back to the earlier poster's question, this cache spilling can have a detrimental effect on other processes sharing the same cache or NUMA node, just like one extremely bloated program can cause a virtual memory swapping frenzy and hurt every other program on the machine. One form of "pipelining" optimization is to recognize when your loop is repeatedly fetching a lot of the same input data in multiple iterations and changing that to use variables/buffers to retain state between iterations and avoid redundant access. This often happens in convolution algorithms on arrays of multi-dimensional data, e.g. image processing and neural nets and many cellular-automata style or grid-based simulations. Your algorithm slides a "sampling window" along an array to compute an output value as a linear combination of all the neighboring values within the window using some filtering kernel (a fixed pattern of multiplicative scalars/weights). Naive code keeps loading this whole window once for each iteration of the loop to address one output position. It is effectively stateless except for the loops to visit every output. Pipelined code would manage a window buffer and fetch and replace only the fringe of the buffer while holding and reusing inputs from the previous iterations. While this makes the loops more stateful, it can dramatically reduce the number of memory reads and shift a memory-bound code back into a CPU-bound regime. Other major optimizations for these N-dimensional convolutions are done by the programmer/designer: some convolution kernels are "decomposable" and the expensive multi-dimensional operation can be strength-reduced to a sequence of 1-dimensional convolutions with appropriately chosen filter kernels to produce the same mathematical result. This optimization has nothing to do with SIMD but simplifies the work to embody the operation. Fewer input values to read (e.g. a 1D line of neighbors instead of 2D box) and the number of arithmetic operations to do all the multiply-and-add steps to produce the output. Imagine a 2D filter that operates on an 8x8 window. The 2D convolution has to sample and combine 64 input neighbors per output, while the decomposed filter does 8 neighbors in each axis and so one quarter as many steps total after one pass for the X axis and one pass for the Y axis. Naively, decompsition is done as separate 1D passes over the data and so performs more memory writes and allocates an additional intermediate array between the original input and final output. This is often a big win in spite of the extra memory demands. It's a lot more coding, but this could also be "pipelined" to some degree in N-dimensions to avoid pushing the entire intermediate results arrays through main memory. Approaches differ, but you can make different tradeoffs for how many intermediate results to store or buffer versus redundant calculation in a less stateful manner. Generally, as you make the above kinds of optimizations your code becomes more "block-based", loading larger chunks of data with fewer changes to new "random" memory locations. This is very much like how databases and filesystems optimized their access to disk storage in prior decades to avoid random seeks for individual bytes or blocks and to instead use clever structures to support faster loading of sets of blocks or pages. When this is successful, your program does most of its memory access sequentially and achieves higher throughput that is bound by total memory bus bandwidth rather than random access latency limitations. The final form of "pipelining" matters once you really hit your stride with these optimized, block-based programs. All this access again can cause cache spilling as you sustain high bandwidth memory access. But if you can provide the right hints to the CPU, or if the CPU is clever enough to detect the pattern, it can shift into a different cache management regime. Knowing that you will only access each block of data once and then move on (because you are holding the reusable state in registers), the CPU can use a different prefetching and spilling policy to both optimize for your next memory access and to avoid churning the whole cache with these values you will only read once and then ignore. This reduces the impact of the code on other concurrent tasks which can still enjoy more reasonable caching behavior in spite of the busy neighbor.
slackerIII 4y ago
What would it take for something like this to make it into Postgres?
- VHRanger 4y ago
  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
  - Denvercoder9 4y ago
    The data in indexes is stored columnar by most RDBMSes, as far as I know.
    - ddorian43 4y ago
      It actually is not.
    - janwas 4y ago
      I don't know about "most", but here is a list: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes
      - ComputerGuru 4y ago
        No, this is a list of columnar database systems - gp was saying the index, which is often (but not always) stored separately from the main db records.
        janwas 4y ago
        Ah, indeed, my mistake. FWIW I've observed increasing numbers of papers over the past couple of years mentioning entirely columnar databases.
    - 4y ago
deleted 4y ago
[deleted]
orlp 4y ago
SIMD based sorting isn't new, e.g. djbsort: https://sorting.cr.yp.to/ 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 https://arxiv.org/abs/1704.08579. A comparison would still be nice though.
- explaingarlic 4y ago
  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.
  - janwas 4y ago
    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) :)
- nostrademons 4y ago
  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.
  - jeffbee 4y ago
    The blog post does seem to be quite explicit about the fact that their contribution is in the field of portability, not novelty.
  - janwas 4y ago
unnouinceput 4y ago
Quote: "Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort...." and proceeds to explain about SIMD instructions. 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.
- janwas 4y ago
  CPU vendors have recently introduced SVE (Arm) and RVV (RISC-V) and we support those in Highway and thus also vqsort. It's definitely interesting to discuss std::sort benefitting from such optimizations, but "very easy" seems rather optimistic.
  - benstrumental 4y ago
    Do you expect these optimizations making their way into std::sort eventually?
    - janwas 4y ago
      It depends on the goals of the library maintainers. Users who really care about speed may already be using another library such as PDQsort or ips4o. Given that, the stdlib maintainers may reason that adding code and 'complexity' (not all developers understand or are able to maintain SIMD) is not worthwhile. Conversely, they may prefer to work towards the standard library being the fastest known way of doing things. This is now much more feasible given the single portable implementation, vs. having to rewrite thousands of lines for six instruction sets. Not sure which consideration carries more weight.
jart 4y ago
I wonder how fast it is compared to djbsort https://github.com/jart/cosmopolitan/blob/master/libc/nexgen32e/djbsort-avx2.S https://github.com/jart/cosmopolitan/blob/master/libc/nexgen... and longsort https://github.com/jart/cosmopolitan/blob/e011973593407f576d6e613222a18e04cf19b483/libc/str/longsort.c#L66 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 fast. So if this thing can actually sort 64-bit integers 10x faster on avx2 I'd be so thrilled.
- wtallis 4y ago
  > 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.
  - jart 4y ago
    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.
    - wtallis 4y ago
      Even if AVX512 was entirely constrained to server hardware (it's not), how would it be contrary to the public interest for open-source software to take advantage of those instructions?
    - akelly 4y ago
      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.
janwas 4y ago
Author here, happy to discuss.
- kwillets 4y ago
  Is there any benefit to a multipivot sort? The partitioning would be more complex but possibly save memory accesses.
  - janwas 4y ago
    Yes, this is discussed in section 4.2 of our paper: https://arxiv.org/pdf/2205.05982.pdf https://arxiv.org/pdf/2205.05982.pdf In short, it turns out not to help for single core with vectors, but a few initial passes of ips4o (with 64..256-way partitioning) is faster for parallel sorts.
- mchusma 4y ago
  Very cool work! What do you see as the typical process of getting code like this into use in well known codebases? I'm trying to get a sense of when a typical engineer (operating with higher level language or libraries) might get to take advantage of this. Thanks for open sourcing!
  - janwas 4y ago
    Thanks! Highway is included in Chrome and Firefox. Not sure what you mean by process? It's pretty easy for example using git submodules - you tell Git the Highway version you want to depend on, notify your CMake or Bazel build system of the hwy library dependency, and that's it. One requirement is C++11 or later - some people have asked about supporting C but I believe that's infeasible.
- johntortugo 4y ago
  I think it would interesting to have a power consumption comparison as well.
  - janwas 4y ago
gww 4y ago
I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".
- janwas 4y ago
  :) How about Chapter 12 of Agner's awesome manual (https://agner.org/optimize/optimizing_cpp.pdf https://agner.org/optimize/optimizing_cpp.pdf), http://const.me/articles/simd/simd.pdf http://const.me/articles/simd/simd.pdf, https://en.algorithmica.org/hpc/simd/ https://en.algorithmica.org/hpc/simd/ ? Does anyone have others to share?
  - gww 4y ago
    These are really helpful too. Another reply to my question suggests a course that looks really good too.
- magicnubs 4y ago
  The lectures and assignments for Oregon State's CS475 (Parallel Programming) are all available online. [0] There are lectures [1] and a project [2] about SIMD. I really enjoyed the entire course as a survey of parallel and high-performance computing. The full course covers multi-processing, multi-threading, caching, SIMD, GPUs (CUDA and OpenCL) and MPI. The projects are in C/C++ (along with OpenMP, CUDA and OpenCL). FYI, I think the last two projects use some large research GPU bank that you have to have special access to use, so you'd be out of luck on implementing the projects for those. [0] https://web.engr.oregonstate.edu/~mjb/cs575/ https://web.engr.oregonstate.edu/~mjb/cs575/ [1] https://media.oregonstate.edu/media/t/1_7wju0jtq https://media.oregonstate.edu/media/t/1_7wju0jtq [2] https://web.engr.oregonstate.edu/~mjb/cs575/Projects/proj04.html https://web.engr.oregonstate.edu/~mjb/cs575/Projects/proj04....
  - gww 4y ago
    Thanks these are really great. That's a course I wish my CS program had.
olliej 4y ago
Re-implementation of stuff with SIMD is always amazing to me. I have done stuff with SIMD before: 4 element float vector operations; basic arithmetic on arrays of floats. Those are things that are super simple, once you get past the scary mystique of SIMD. It’s stuff like this that should be getting all the witch burning :D
wly_cdgr 4y ago
SpaceChem players have known this for years
jerryjerryjerry 4y ago
This is great, and can definitely improve sort performance in database and big data projects. I can immediately imagine this is a perfect match to my project of columnar processing engine TiFlash (https://github.com/pingcap/tiflash https://github.com/pingcap/tiflash).
skybrian 4y ago
Will browsers start using this code for typed array sorting? Maybe they already do?
- xxs 4y ago
  Sorting integers is actually rare in practice, esp. not very useful for a browser.
  - skybrian 4y ago
    The method exists. They could make it faster without breaking anything. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
DeathArrow 4y ago
This might interest someone: "Vectorized Operations extension for PostgreSQL" https://github.com/postgrespro/vops https://github.com/postgrespro/vops
- polskibus 4y ago
  This looks awesome but could do with a bit of productionalization. For example ready to use binaries. Do you know if there are any plans to merge this work with core postgres?
MrYellowP 4y ago
Man, 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!
- joebob42 4y ago
  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 :)
  - MrYellowP 4y ago
    Thanks for your post! Let me explain my problem, which fits right to it. It works as an example, too. So, in freepascal there's some subpar pattern matching/string search function. It annoyed me so greatly, I've started researching into the "state of the art" and apparently they're all crap. My fixed size pattern matching solution fits into less than 256 bytes, not counting setup code, which is minimal. And here start the problems for me, because I have no way of actually comparing my solution to "the state of the art", because "the state of the art" doesn't offer me downloadable, compiled benchmarks I can just run to compare stuff to my own and learning a new language (like, i don't speak C and certainly never will), installing a compiler, getting through all the walls that inevitably be in my way to getting it to run, etc ... totally breaks my timebudget and thus I drop the problem. Basically, what I'm looking for is: Give me a problem that's worth tackling, with a defined set of parameters and a compiled solution I can compare my own against and I will beat it eventually. I've tried doing this on my own, but that's just a big no-go on many levels, so I'm dependent on someone handing something to me. Like ... the QuickSort. I have no way of comparing my potential own solution against "the state of the art", which is - as far as I know - pretty much all that's holding me back.
BeeOnRope 4y ago
Are there instructions for building & reproducing the performance results?
- janwas 4y ago
  I'd recommend building using Bazel (perhaps via the bazelisk launcher), then it would be: bazel run -c opt :bench_sort (or :bench_parallel). Will verify that on Tue and put it in a README in contrib/sort.
thecompilr 4y ago
I'm the co-author of one of the papers referenced in the blogpost, (Fast Quicksort Implementation Using AVX Instructions), we did write the AVX512 code back in 2015, just had nowhere to run it, at least publicly. The paper also very explicitly says that the lookup tables can be instead replaced by the AVX512 compress instructions. The code for that paper is available in https://github.com/vkrasnov/avx_qsort https://github.com/vkrasnov/avx_qsort
carbocation 4y ago
Looks like djb is giving it a spin: https://twitter.com/hashbreaker/status/1533201734369103872 https://twitter.com/hashbreaker/status/1533201734369103872
- janwas 4y ago
  Response here because I'm not on Twitter: https://github.com/google/highway/issues/736 https://github.com/google/highway/issues/736 In short, what is being compared is O(1) djbsort sorting network, vs our full quicksort with pivot sampling, partitioning, then sorting network. This is because our sorting network size is 16 * elements_per_vector i.e. 128 in this configuration.
- sydthrowaway 4y ago
  And he shat all over Google yet again
  - aaaaaaaaaaab 4y ago
    But he’s right.
  - viraptor 4y ago
    He's just investigating how to reproduce the claimed result. Not sure where you got your take from.
    - jiggawatts 4y ago
      Something to note is that he was testing this on an 11-year old processor: https://ark.intel.com/content/www/us/en/ark/products/52269/intel-xeon-processor-e31220-8m-cache-3-10-ghz.html https://ark.intel.com/content/www/us/en/ark/products/52269/i... The Google sorting algorithm seems to be optimised for the "latest and greatest" AVX-512 capable CPUs.
      - janwas 4y ago
        Oh, thanks for pointing that out. Golly, Sandy Bridge is a bit old, yes - but still the result is surprising. djb reports 8000 cycles for int32 x 256 - this is much slower than we benchmark in bench_sort.cc, even for AVX2 (which he confirms is being reached). Not sure what's going on.
aaaaaaaaaaab 4y ago
This works only with integers, right? Then radix sort is gonna be still faster on sufficiently large inputs…
- janwas 4y ago
  Actually we also support floating-point (32/64 bit, possibly even 16). I've previously also looked into radix sort: https://arxiv.org/abs/1008.2849 https://arxiv.org/abs/1008.2849 Radix sort may actually be faster if you know that only a few bytes are guaranteed to distinguish keys, but that's difficult to guarantee/assume at the library level.
diamondlovesyou 4y ago
If P=NP, it only going to be possible because of vectorizing/vectorization.
sylware 4y ago
This code is worth a clean assembly port.
- janwas 4y ago
  :) I'm curious why? But if so, you can have Compiler Explorer give you a starting point (assembly output) quickly.

460 points by slackerIII 4y ago

I love work like this and SIMD-JSON which vectorizes what "should be" sequential form problems to find massive performance gains

charcircuit 4y ago
Any nonsequential problem can be divided into sequential subprobolems.
singhrac 4y ago
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 https://raphlinus.github.io/gpu/2020/09/05/stack-monoid.html [2]: https://arxiv.org/abs/2205.11659 https://arxiv.org/abs/2205.11659

alecco 4y ago

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

slackerIII 4y ago
The paper goes into a lot more details: https://arxiv.org/pdf/2205.05982.pdf https://arxiv.org/pdf/2205.05982.pdf
- MontyCarloHall 4y ago
  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.
  - kadoban 4y ago
    That might be an interesting benchmark, but assuming good cooling isn't exactly unreasonable either.
    - MontyCarloHall 4y ago
      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.
  - hinkley 4y ago
    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.
    - bee_rider 4y ago
      One option would be to go into BIOS and see if there's some way of just locking your CPU to one of the lower clock speeds. This will give lower benchmarking numbers of course, but at least they should be fairly stable. (in Linux, it also often possible to tinker with frequencies while the system is running). Even on a desktop this sort of thing is sometimes necessary, for example my CPU has different clock speeds depending on how many processors are running, so I have to lock it to the all-core clock if I want to see proper parallel speedups. This might be annoying for day-to-day usage (although, CPUs really are insanely performant nowadays so maybe it will not be too bad).
Rizz 4y ago
Which they did and showed in the previous sentence. You cannot possibly have missed that.
throw-away_42 4y ago
Also disingenuous to claim they don't make that comparison when it's literally the sentence before the one you quoted.
- alecco 4y ago
  My bad. Apologies.

cbetti 4y ago

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?

VHRanger 4y ago
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.
- janwas 4y ago
  The CPU has a certain upper bound on power, TDP. That limit is independent of whether it is reached by executing scalar code on lots of cores, or SIMD on a few. One little-known fact is that out of order CPUs burn lots of energy just on scheduling instructions, ~10x more than the operation itself. SIMD amortizes that per-instruction overhead over multiple data elements, and actually increases the amount of useful work done per joule. We're talking 5-10x increase in energy efficiency.
- saltcured 4y ago
  Right, though your use of the terms "different registers" and "properly pipelined" is quite nuanced for a non-specialist. It leaves a lot to the imagination or prior experience! If it is a compute-heavy code that was spilling to a stack and now can fit in the SIMD registers, there could be a speed up with less memory traffic. This is analogous to a program's working set either fitting in RAM or spilling to swap while it runs, but at a different level of the memory hierarchy. In the extreme case, your working set could be a fixed set of variables in expensive loops for some sequential algorithm, and so the compiler register placement ability and number of registers available could be the difference between effectively O(1) or O(n) memory accesses with respect to the number of compute steps. Of course, you can find such transitions between registers/L1 cache, L1/L2 cache, L2/L3 cache (if present), local/remote RAM (for modern NUMA machines), etc. This happens as you transition from a pure CPU-bound case to something with bigger data structures, where the program focus has to move to different parts of the data to make progress. Naively holding other things equal, an acceleration of a CPU-bound code will of course mean you churn through these different data faster, which means more cache spills as you pull in new data and have to displace something else. Going back to the earlier poster's question, this cache spilling can have a detrimental effect on other processes sharing the same cache or NUMA node, just like one extremely bloated program can cause a virtual memory swapping frenzy and hurt every other program on the machine. One form of "pipelining" optimization is to recognize when your loop is repeatedly fetching a lot of the same input data in multiple iterations and changing that to use variables/buffers to retain state between iterations and avoid redundant access. This often happens in convolution algorithms on arrays of multi-dimensional data, e.g. image processing and neural nets and many cellular-automata style or grid-based simulations. Your algorithm slides a "sampling window" along an array to compute an output value as a linear combination of all the neighboring values within the window using some filtering kernel (a fixed pattern of multiplicative scalars/weights). Naive code keeps loading this whole window once for each iteration of the loop to address one output position. It is effectively stateless except for the loops to visit every output. Pipelined code would manage a window buffer and fetch and replace only the fringe of the buffer while holding and reusing inputs from the previous iterations. While this makes the loops more stateful, it can dramatically reduce the number of memory reads and shift a memory-bound code back into a CPU-bound regime. Other major optimizations for these N-dimensional convolutions are done by the programmer/designer: some convolution kernels are "decomposable" and the expensive multi-dimensional operation can be strength-reduced to a sequence of 1-dimensional convolutions with appropriately chosen filter kernels to produce the same mathematical result. This optimization has nothing to do with SIMD but simplifies the work to embody the operation. Fewer input values to read (e.g. a 1D line of neighbors instead of 2D box) and the number of arithmetic operations to do all the multiply-and-add steps to produce the output. Imagine a 2D filter that operates on an 8x8 window. The 2D convolution has to sample and combine 64 input neighbors per output, while the decomposed filter does 8 neighbors in each axis and so one quarter as many steps total after one pass for the X axis and one pass for the Y axis. Naively, decompsition is done as separate 1D passes over the data and so performs more memory writes and allocates an additional intermediate array between the original input and final output. This is often a big win in spite of the extra memory demands. It's a lot more coding, but this could also be "pipelined" to some degree in N-dimensions to avoid pushing the entire intermediate results arrays through main memory. Approaches differ, but you can make different tradeoffs for how many intermediate results to store or buffer versus redundant calculation in a less stateful manner. Generally, as you make the above kinds of optimizations your code becomes more "block-based", loading larger chunks of data with fewer changes to new "random" memory locations. This is very much like how databases and filesystems optimized their access to disk storage in prior decades to avoid random seeks for individual bytes or blocks and to instead use clever structures to support faster loading of sets of blocks or pages. When this is successful, your program does most of its memory access sequentially and achieves higher throughput that is bound by total memory bus bandwidth rather than random access latency limitations. The final form of "pipelining" matters once you really hit your stride with these optimized, block-based programs. All this access again can cause cache spilling as you sustain high bandwidth memory access. But if you can provide the right hints to the CPU, or if the CPU is clever enough to detect the pattern, it can shift into a different cache management regime. Knowing that you will only access each block of data once and then move on (because you are holding the reusable state in registers), the CPU can use a different prefetching and spilling policy to both optimize for your next memory access and to avoid churning the whole cache with these values you will only read once and then ignore. This reduces the impact of the code on other concurrent tasks which can still enjoy more reasonable caching behavior in spite of the busy neighbor.

slackerIII 4y ago

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

VHRanger 4y ago
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
- Denvercoder9 4y ago
  The data in indexes is stored columnar by most RDBMSes, as far as I know.
  - ddorian43 4y ago
    It actually is not.
  - janwas 4y ago
    I don't know about "most", but here is a list: https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes https://en.wikipedia.org/wiki/List_of_column-oriented_DBMSes
    - ComputerGuru 4y ago
      No, this is a list of columnar database systems - gp was saying the index, which is often (but not always) stored separately from the main db records.
      - janwas 4y ago
        Ah, indeed, my mistake. FWIW I've observed increasing numbers of papers over the past couple of years mentioning entirely columnar databases.
  - 4y ago

deleted 4y ago

[deleted]

orlp 4y ago

SIMD based sorting isn't new, e.g. djbsort: https://sorting.cr.yp.to/ 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 https://arxiv.org/abs/1704.08579. A comparison would still be nice though.

explaingarlic 4y ago
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.
- janwas 4y ago
  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) :)
nostrademons 4y ago
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.
- jeffbee 4y ago
  The blog post does seem to be quite explicit about the fact that their contribution is in the field of portability, not novelty.
- janwas 4y ago

unnouinceput 4y ago

Quote: "Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort...." and proceeds to explain about SIMD instructions. 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.

janwas 4y ago
CPU vendors have recently introduced SVE (Arm) and RVV (RISC-V) and we support those in Highway and thus also vqsort. It's definitely interesting to discuss std::sort benefitting from such optimizations, but "very easy" seems rather optimistic.
- benstrumental 4y ago
  Do you expect these optimizations making their way into std::sort eventually?
  - janwas 4y ago
    It depends on the goals of the library maintainers. Users who really care about speed may already be using another library such as PDQsort or ips4o. Given that, the stdlib maintainers may reason that adding code and 'complexity' (not all developers understand or are able to maintain SIMD) is not worthwhile. Conversely, they may prefer to work towards the standard library being the fastest known way of doing things. This is now much more feasible given the single portable implementation, vs. having to rewrite thousands of lines for six instruction sets. Not sure which consideration carries more weight.

jart 4y ago

I wonder how fast it is compared to djbsort https://github.com/jart/cosmopolitan/blob/master/libc/nexgen32e/djbsort-avx2.S https://github.com/jart/cosmopolitan/blob/master/libc/nexgen... and longsort https://github.com/jart/cosmopolitan/blob/e011973593407f576d6e613222a18e04cf19b483/libc/str/longsort.c#L66 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 fast. So if this thing can actually sort 64-bit integers 10x faster on avx2 I'd be so thrilled.

wtallis 4y ago
> 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.
- jart 4y ago
  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.
  - wtallis 4y ago
    Even if AVX512 was entirely constrained to server hardware (it's not), how would it be contrary to the public interest for open-source software to take advantage of those instructions?
  - akelly 4y ago
    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.

janwas 4y ago

Author here, happy to discuss.

kwillets 4y ago
Is there any benefit to a multipivot sort? The partitioning would be more complex but possibly save memory accesses.
- janwas 4y ago
  Yes, this is discussed in section 4.2 of our paper: https://arxiv.org/pdf/2205.05982.pdf https://arxiv.org/pdf/2205.05982.pdf In short, it turns out not to help for single core with vectors, but a few initial passes of ips4o (with 64..256-way partitioning) is faster for parallel sorts.
mchusma 4y ago
Very cool work! What do you see as the typical process of getting code like this into use in well known codebases? I'm trying to get a sense of when a typical engineer (operating with higher level language or libraries) might get to take advantage of this. Thanks for open sourcing!
- janwas 4y ago
  Thanks! Highway is included in Chrome and Firefox. Not sure what you mean by process? It's pretty easy for example using git submodules - you tell Git the Highway version you want to depend on, notify your CMake or Bazel build system of the hwy library dependency, and that's it. One requirement is C++11 or later - some people have asked about supporting C but I believe that's infeasible.
johntortugo 4y ago
I think it would interesting to have a power consumption comparison as well.
- janwas 4y ago

gww 4y ago

I am always amazed at the algorithms re-implemented using SIMD. One of my favorites is the Striped Smith-Waterman approach used for sequence alignment. Does anyone have any good resources on learning to use SIMD? I've found it heard to make the "plunge".

janwas 4y ago
:) How about Chapter 12 of Agner's awesome manual (https://agner.org/optimize/optimizing_cpp.pdf https://agner.org/optimize/optimizing_cpp.pdf), http://const.me/articles/simd/simd.pdf http://const.me/articles/simd/simd.pdf, https://en.algorithmica.org/hpc/simd/ https://en.algorithmica.org/hpc/simd/ ? Does anyone have others to share?
- gww 4y ago
  These are really helpful too. Another reply to my question suggests a course that looks really good too.
magicnubs 4y ago
The lectures and assignments for Oregon State's CS475 (Parallel Programming) are all available online. [0] There are lectures [1] and a project [2] about SIMD. I really enjoyed the entire course as a survey of parallel and high-performance computing. The full course covers multi-processing, multi-threading, caching, SIMD, GPUs (CUDA and OpenCL) and MPI. The projects are in C/C++ (along with OpenMP, CUDA and OpenCL). FYI, I think the last two projects use some large research GPU bank that you have to have special access to use, so you'd be out of luck on implementing the projects for those. [0] https://web.engr.oregonstate.edu/~mjb/cs575/ https://web.engr.oregonstate.edu/~mjb/cs575/ [1] https://media.oregonstate.edu/media/t/1_7wju0jtq https://media.oregonstate.edu/media/t/1_7wju0jtq [2] https://web.engr.oregonstate.edu/~mjb/cs575/Projects/proj04.html https://web.engr.oregonstate.edu/~mjb/cs575/Projects/proj04....
- gww 4y ago
  Thanks these are really great. That's a course I wish my CS program had.

olliej 4y ago

Re-implementation of stuff with SIMD is always amazing to me. I have done stuff with SIMD before: 4 element float vector operations; basic arithmetic on arrays of floats. Those are things that are super simple, once you get past the scary mystique of SIMD. It’s stuff like this that should be getting all the witch burning :D

wly_cdgr 4y ago

SpaceChem players have known this for years

jerryjerryjerry 4y ago

This is great, and can definitely improve sort performance in database and big data projects. I can immediately imagine this is a perfect match to my project of columnar processing engine TiFlash (https://github.com/pingcap/tiflash https://github.com/pingcap/tiflash).

skybrian 4y ago

Will browsers start using this code for typed array sorting? Maybe they already do?

xxs 4y ago
Sorting integers is actually rare in practice, esp. not very useful for a browser.
- skybrian 4y ago
  The method exists. They could make it faster without breaking anything. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

DeathArrow 4y ago

This might interest someone: "Vectorized Operations extension for PostgreSQL" https://github.com/postgrespro/vops https://github.com/postgrespro/vops

polskibus 4y ago
This looks awesome but could do with a bit of productionalization. For example ready to use binaries. Do you know if there are any plans to merge this work with core postgres?

MrYellowP 4y ago

Man, 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!

joebob42 4y ago
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 :)
- MrYellowP 4y ago
  Thanks for your post! Let me explain my problem, which fits right to it. It works as an example, too. So, in freepascal there's some subpar pattern matching/string search function. It annoyed me so greatly, I've started researching into the "state of the art" and apparently they're all crap. My fixed size pattern matching solution fits into less than 256 bytes, not counting setup code, which is minimal. And here start the problems for me, because I have no way of actually comparing my solution to "the state of the art", because "the state of the art" doesn't offer me downloadable, compiled benchmarks I can just run to compare stuff to my own and learning a new language (like, i don't speak C and certainly never will), installing a compiler, getting through all the walls that inevitably be in my way to getting it to run, etc ... totally breaks my timebudget and thus I drop the problem. Basically, what I'm looking for is: Give me a problem that's worth tackling, with a defined set of parameters and a compiled solution I can compare my own against and I will beat it eventually. I've tried doing this on my own, but that's just a big no-go on many levels, so I'm dependent on someone handing something to me. Like ... the QuickSort. I have no way of comparing my potential own solution against "the state of the art", which is - as far as I know - pretty much all that's holding me back.

BeeOnRope 4y ago

Are there instructions for building & reproducing the performance results?

janwas 4y ago
I'd recommend building using Bazel (perhaps via the bazelisk launcher), then it would be: bazel run -c opt :bench_sort (or :bench_parallel). Will verify that on Tue and put it in a README in contrib/sort.

thecompilr 4y ago

I'm the co-author of one of the papers referenced in the blogpost, (Fast Quicksort Implementation Using AVX Instructions), we did write the AVX512 code back in 2015, just had nowhere to run it, at least publicly. The paper also very explicitly says that the lookup tables can be instead replaced by the AVX512 compress instructions. The code for that paper is available in https://github.com/vkrasnov/avx_qsort https://github.com/vkrasnov/avx_qsort

carbocation 4y ago

Looks like djb is giving it a spin: https://twitter.com/hashbreaker/status/1533201734369103872 https://twitter.com/hashbreaker/status/1533201734369103872

janwas 4y ago
Response here because I'm not on Twitter: https://github.com/google/highway/issues/736 https://github.com/google/highway/issues/736 In short, what is being compared is O(1) djbsort sorting network, vs our full quicksort with pivot sampling, partitioning, then sorting network. This is because our sorting network size is 16 * elements_per_vector i.e. 128 in this configuration.
sydthrowaway 4y ago
And he shat all over Google yet again
- aaaaaaaaaaab 4y ago
  But he’s right.
- viraptor 4y ago
  He's just investigating how to reproduce the claimed result. Not sure where you got your take from.
  - jiggawatts 4y ago
    Something to note is that he was testing this on an 11-year old processor: https://ark.intel.com/content/www/us/en/ark/products/52269/intel-xeon-processor-e31220-8m-cache-3-10-ghz.html https://ark.intel.com/content/www/us/en/ark/products/52269/i... The Google sorting algorithm seems to be optimised for the "latest and greatest" AVX-512 capable CPUs.
    - janwas 4y ago
      Oh, thanks for pointing that out. Golly, Sandy Bridge is a bit old, yes - but still the result is surprising. djb reports 8000 cycles for int32 x 256 - this is much slower than we benchmark in bench_sort.cc, even for AVX2 (which he confirms is being reached). Not sure what's going on.

aaaaaaaaaaab 4y ago

This works only with integers, right? Then radix sort is gonna be still faster on sufficiently large inputs…

janwas 4y ago
Actually we also support floating-point (32/64 bit, possibly even 16). I've previously also looked into radix sort: https://arxiv.org/abs/1008.2849 https://arxiv.org/abs/1008.2849 Radix sort may actually be faster if you know that only a few bytes are guaranteed to distinguish keys, but that's difficult to guarantee/assume at the library level.

diamondlovesyou 4y ago

If P=NP, it only going to be possible because of vectorizing/vectorization.

sylware 4y ago

This code is worth a clean assembly port.

janwas 4y ago
:) I'm curious why? But if so, you can have Compiler Explorer give you a starting point (assembly output) quickly.