4 ms·

Please, you are overstating your case in a way that distracts from the issues at hand. I do agree that Linus's opinions are irrelevant to a lot of computing, an

Please, you are overstating your case in a way that distracts from the issues at hand. I do agree that Linus's opinions are irrelevant to a lot of computing, and that sorting must make some use of SIMD for the best performance, and that there's good work in vqsort. But the 10x factor is highly misleading. Sure, it's technically correct that you "can be about 10x as fast" as a scalar sort. In the same sense that a scalar sort can be 10x as fast as an AVX-512 one. The 10x number is from comparing against std::sort on random data, yes? Both common std::sort implementations are branching quicksorts from the era when introsort was still considered exciting new technology, and are much slower than pdqsort and other branchless quicksorts. The measurements at [0] show by my estimate about a gain of 3x against pdqsort and 2x against ipnsort. For vqsort only; intel barely beats ipnsort. I also pointed out to you at [1] benchmarks showing 1450MB/s for 32-bit radix sort at a million elements on M1, which is comparable to your Xeon measurements and nearly 3x faster than the 499MB/s for M1 in the vqsort paper. If you're going to quote a std::sort number, at least give the name instead of implying it's a good representative for scalar sorts! I would strongly recommend, however, that you benchmark against and study more modern scalar algorithms. I know SIMD and have even vectorized parts of pdqsort in the past; I've chosen to work with scalar algorithms for the past year or two because I think these methods still have a lot to offer. [0] https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#addendum https://github.com/Voultapher/sort-research-rs/blob/main/wri... [1] https://news.ycombinator.com/item?id=36309049 https://news.ycombinator.com/item?id=36309049

vegabook 3y ago
Quite the robust defence of scalar, coming as it is from from a vector guy! https://github.com/mlochbaum/BQN https://github.com/mlochbaum/BQN
- mlochbaum 3y ago
  Vector registers are great, but it's important to remember that random-access cache is also very powerful hardware, and can be better-suited to a lot of searching and sorting tasks. One task where, unlike sorting, I think vectors have no shot, is random shuffling. For small sizes (okay, but too large to fit all in registers) it's hard to see how anything could beat Knuth shuffle since it just does one swap per value. At large sizes it's not cache-friendly, and there are known methods based on quicksort and mergesort that work better. But I found that a radix pass beats these easily, and I'd expect this to hold even with AVX-512 versions of merge/partition, because it takes 8 steps of those to add up to one 1-byte radix step. Sorting runs into similar problems at very large sizes. The vqsort authors found that at 1e8 elements a hybrid of ips4o (samplesort, think many-way partition) beats pure vqsort. Writeup: https://mlochbaum.github.io/BQN/implementation/primitive/random.html#shuffling https://mlochbaum.github.io/BQN/implementation/primitive/ran... Timings (i5-6200U): https://matrix.org/_matrix/media/r0/download/matrix.org/AVtvoCgryEmdCeVvgtuRHUDm https://matrix.org/_matrix/media/r0/download/matrix.org/AVtv...
  - moonchild 3y ago
    It seems likely to me that multi-way merge is better. 256-way is a bit much, but, with appropriate queueing, you can get close. Among other reasons because, unlike multi-way partition, multi-way merge does benefit from vectorisation, and hence is more efficient. (Of course, for the 'very parallel' a la gpus, partition/radix is apparently interesting again, as you can afford the out-of-place parallel scan.)
    - mlochbaum 3y ago
      Oh, I didn't know that about multi-way merge (regrettably I haven't really wrapped my head around SIMD merging yet). Got a source for this? https://vldb.org/pvldb/vol8/p1274-inoue.pdf https://vldb.org/pvldb/vol8/p1274-inoue.pdf mentions it but it looks more like interleaving several binary merges than true multi-way. Although I guess from a memory perspective there's no difference. Also, not sure I've mentioned multiway Powersort to you, and it seems like a natural fit: https://www.wild-inter.net/publications/cawley-gelling-nebel-smith-wild-2023 https://www.wild-inter.net/publications/cawley-gelling-nebel... . One thing that I'd imagine makes sense is to increase the number of merged arrays as the total size gets larger and the memory accesses get slow.
      - moonchild 3y ago
        Yeah, that's logically what it is—point is just to reduce memory traffic. (And, for that matter, memory subsystem ops, which is amusing as distribution by contrast directly exploits the memory subsystem.) I haven't read anything about it, but I came up with the following scheme: A basic efficient scheme for merging two arrays is: pop one vector from the left array, pop one from the right array, merge them with some oblivious sorting network, and then write out the low vector. Keep the high in reserve. Then repeatedly pop a vector from whichever array has the lower initial element, merge it with the reserve vector, and write out the low vector from the result. We can imagine doing something similar to merge k inputs: pop one vector from each input, and merge them all together. Write out the low vector, keeping the remaining k-1 in reserve; then, repeatedly pop one vector from the input with the lowest initial element (can be determined with a tourney tree[0]), merge it with the k-1 reserve vectors, and write out the low result. The problem is that this is inefficient; we have to do a 1:k-1 merge. The solution is queueing. Pop k vectors, each time from the lowest remaining input. Merge the k vectors all together (if k is a power of two, then this is completely balanced), then merge the fresh k with the reserve k-1 (only slightly unbalanced), and write out the low k results, leaving the high k-1 as the reserve for the next iteration. For very large inputs, this will be inadequate (I think I can get up to k=8 on avx512), but it can be layered using in-memory buffers; 8^2=64-way merge seems reasonable, especially given that at this point you probably want to use multiple cores. Multiway powersort looks interesting, thanks! I was wondering how to solve that problem. 0. https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tournament_Tree https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tourname...
janwas 3y ago
What exactly do you see as overstated - only the "10x"? I realize characterizing sort performance with one number is very lossy, but consider "can be" to be a rather modest claim. > The 10x number is from comparing against std::sort on random data, yes? That's just one example. For another, check out how many projects still use the even slower HeapSort: https://sourcegraph.com/search?q=context:global+HeapSort+count:1000000&patternType=standard&sm=1&groupBy=repo https://sourcegraph.com/search?q=context:global+HeapSort+cou... (198K search hits) When comparing against ipnsort, that is also (partially) vectorized, right? FWIW I agree that radix sort can be great in certain cases, especially if one core is allowed to soak up all the system memory bandwidth. Unfortunately this is rare from where I sit. I'm curious which specific parts/aspects of scalar algorithms you'd recommend for study? From my perspective (admittedly skewed towards servers), anything as energy-inefficient as scalar code running on big OoO cores is a hard sell whenever vector alternatives exist.
- mlochbaum 3y ago
  Yes, only your "10x" and "5-10x" numbers are overstated. Which is to say, all the quantitative comparison you've shared here, or in the vqsort README (aside from the link to Lukas's measurements, which is linked with no indication it benchmarks against faster sorts). What you share is defensible in that it's technically correct, but it's not helpful. As an example, consider an application that uses heapsort now, but ships a unified binary for x86. The programmers could easily switch to pdqsort, which is well-tested and available in many languages. If they read only material you publish, they may get the impression that SIMD support (at least SSE4) is required to get a substantial improvement, and stick with heapsort to avoid the need to ship multiple binaries or add architecture detection. All you need to correct this is one mention that you can do better than std::sort! By leaving this out, you instead reinforce the idea that it's a reasonable choice if you have to go scalar. ipnsort has no explicit vectorization; some parts may be auto-vectorized. From a quick glance through perf results, I don't see any vector instructions used in the parts that take up time. I didn't see any anywhere, actually. Same story with other quicksorts, although I know fluxsort/crumsort's initial analyzer is designed to be auto-vectorized. I don't get why you dismiss radix sort so quickly, when your own research shows that an MSD/LSD hybrid addresses the bandwidth problem well? Thanks for sharing that paper by the way, very elegant approach. The bandwidth problem is not one I've seen discussed although I see how it would arise. I just don't deal with big arrays that much—and it seems if you're going to market vqsort as general-purpose you should also care about this use case! However, a nice thing about radix sort is that it can be used as a base case for quicksort/samplesort, and any partitioning done so far allows fewer steps to be used. I have a case in SingeliSort to do 4-byte sorting that fits in 2-byte range nearly in-place[0]. It's only used on 2^16 elements or fewer to avoid possible cache associativity problems, so that should fit in L2 and not use system bandwidth. Comparison-based algorithms I consider most relevant at the moment are fluxsort/crumsort/quadsort (all by the same author; they share many pieces), ipnsort (largely derived from those plus pdqsort but it may be easier to read), and glidesort somewhat (the gliding technique is cool but I think there are flaws to address, see [1]). For distribution sorting, there's radix, the version of counting sort where you reconstruct from counts instead of moving the data (output can be vectorized with a scan for large ranges!), and I've developed Robin Hood sort to take advantage of smooth-ish distributions such as uniform random. I keep notes at [2], which are pretty out of date. I should be writing there instead of here... I of course don't think there's any requirement to know all this to contribute to sorting research. I take issue with making blanket claims like "I'd consider AVX2 to be table stakes for any sorting algorithm" and "anything as energy-inefficient as scalar code running on big OoO cores is a hard sell" without being familiar with the state of the art in scalar sorting. [0] https://github.com/mlochbaum/SingeliSort/blob/master/src/radix.singeli#L120-L128 https://github.com/mlochbaum/SingeliSort/blob/master/src/rad... [1] https://github.com/Voultapher/sort-research-rs/pull/6#issuecomment-1588172671 https://github.com/Voultapher/sort-research-rs/pull/6#issuec... [2] https://mlochbaum.github.io/BQN/implementation/primitive/sort.html https://mlochbaum.github.io/BQN/implementation/primitive/sor...
pjmlp 3y ago
Last time I checked, there are more than two C++ compilers.

vegabook 3y ago

Quite the robust defence of scalar, coming as it is from from a vector guy! https://github.com/mlochbaum/BQN https://github.com/mlochbaum/BQN

mlochbaum 3y ago
Vector registers are great, but it's important to remember that random-access cache is also very powerful hardware, and can be better-suited to a lot of searching and sorting tasks. One task where, unlike sorting, I think vectors have no shot, is random shuffling. For small sizes (okay, but too large to fit all in registers) it's hard to see how anything could beat Knuth shuffle since it just does one swap per value. At large sizes it's not cache-friendly, and there are known methods based on quicksort and mergesort that work better. But I found that a radix pass beats these easily, and I'd expect this to hold even with AVX-512 versions of merge/partition, because it takes 8 steps of those to add up to one 1-byte radix step. Sorting runs into similar problems at very large sizes. The vqsort authors found that at 1e8 elements a hybrid of ips4o (samplesort, think many-way partition) beats pure vqsort. Writeup: https://mlochbaum.github.io/BQN/implementation/primitive/random.html#shuffling https://mlochbaum.github.io/BQN/implementation/primitive/ran... Timings (i5-6200U): https://matrix.org/_matrix/media/r0/download/matrix.org/AVtvoCgryEmdCeVvgtuRHUDm https://matrix.org/_matrix/media/r0/download/matrix.org/AVtv...
- moonchild 3y ago
  It seems likely to me that multi-way merge is better. 256-way is a bit much, but, with appropriate queueing, you can get close. Among other reasons because, unlike multi-way partition, multi-way merge does benefit from vectorisation, and hence is more efficient. (Of course, for the 'very parallel' a la gpus, partition/radix is apparently interesting again, as you can afford the out-of-place parallel scan.)
  - mlochbaum 3y ago
    Oh, I didn't know that about multi-way merge (regrettably I haven't really wrapped my head around SIMD merging yet). Got a source for this? https://vldb.org/pvldb/vol8/p1274-inoue.pdf https://vldb.org/pvldb/vol8/p1274-inoue.pdf mentions it but it looks more like interleaving several binary merges than true multi-way. Although I guess from a memory perspective there's no difference. Also, not sure I've mentioned multiway Powersort to you, and it seems like a natural fit: https://www.wild-inter.net/publications/cawley-gelling-nebel-smith-wild-2023 https://www.wild-inter.net/publications/cawley-gelling-nebel... . One thing that I'd imagine makes sense is to increase the number of merged arrays as the total size gets larger and the memory accesses get slow.
    - moonchild 3y ago
      Yeah, that's logically what it is—point is just to reduce memory traffic. (And, for that matter, memory subsystem ops, which is amusing as distribution by contrast directly exploits the memory subsystem.) I haven't read anything about it, but I came up with the following scheme: A basic efficient scheme for merging two arrays is: pop one vector from the left array, pop one from the right array, merge them with some oblivious sorting network, and then write out the low vector. Keep the high in reserve. Then repeatedly pop a vector from whichever array has the lower initial element, merge it with the reserve vector, and write out the low vector from the result. We can imagine doing something similar to merge k inputs: pop one vector from each input, and merge them all together. Write out the low vector, keeping the remaining k-1 in reserve; then, repeatedly pop one vector from the input with the lowest initial element (can be determined with a tourney tree[0]), merge it with the k-1 reserve vectors, and write out the low result. The problem is that this is inefficient; we have to do a 1:k-1 merge. The solution is queueing. Pop k vectors, each time from the lowest remaining input. Merge the k vectors all together (if k is a power of two, then this is completely balanced), then merge the fresh k with the reserve k-1 (only slightly unbalanced), and write out the low k results, leaving the high k-1 as the reserve for the next iteration. For very large inputs, this will be inadequate (I think I can get up to k=8 on avx512), but it can be layered using in-memory buffers; 8^2=64-way merge seems reasonable, especially given that at this point you probably want to use multiple cores. Multiway powersort looks interesting, thanks! I was wondering how to solve that problem. 0. https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tournament_Tree https://en.wikipedia.org/wiki/K-way_merge_algorithm#Tourname...

janwas 3y ago

What exactly do you see as overstated - only the "10x"? I realize characterizing sort performance with one number is very lossy, but consider "can be" to be a rather modest claim. > The 10x number is from comparing against std::sort on random data, yes? That's just one example. For another, check out how many projects still use the even slower HeapSort: https://sourcegraph.com/search?q=context:global+HeapSort+count:1000000&patternType=standard&sm=1&groupBy=repo https://sourcegraph.com/search?q=context:global+HeapSort+cou... (198K search hits) When comparing against ipnsort, that is also (partially) vectorized, right? FWIW I agree that radix sort can be great in certain cases, especially if one core is allowed to soak up all the system memory bandwidth. Unfortunately this is rare from where I sit. I'm curious which specific parts/aspects of scalar algorithms you'd recommend for study? From my perspective (admittedly skewed towards servers), anything as energy-inefficient as scalar code running on big OoO cores is a hard sell whenever vector alternatives exist.

mlochbaum 3y ago
Yes, only your "10x" and "5-10x" numbers are overstated. Which is to say, all the quantitative comparison you've shared here, or in the vqsort README (aside from the link to Lukas's measurements, which is linked with no indication it benchmarks against faster sorts). What you share is defensible in that it's technically correct, but it's not helpful. As an example, consider an application that uses heapsort now, but ships a unified binary for x86. The programmers could easily switch to pdqsort, which is well-tested and available in many languages. If they read only material you publish, they may get the impression that SIMD support (at least SSE4) is required to get a substantial improvement, and stick with heapsort to avoid the need to ship multiple binaries or add architecture detection. All you need to correct this is one mention that you can do better than std::sort! By leaving this out, you instead reinforce the idea that it's a reasonable choice if you have to go scalar. ipnsort has no explicit vectorization; some parts may be auto-vectorized. From a quick glance through perf results, I don't see any vector instructions used in the parts that take up time. I didn't see any anywhere, actually. Same story with other quicksorts, although I know fluxsort/crumsort's initial analyzer is designed to be auto-vectorized. I don't get why you dismiss radix sort so quickly, when your own research shows that an MSD/LSD hybrid addresses the bandwidth problem well? Thanks for sharing that paper by the way, very elegant approach. The bandwidth problem is not one I've seen discussed although I see how it would arise. I just don't deal with big arrays that much—and it seems if you're going to market vqsort as general-purpose you should also care about this use case! However, a nice thing about radix sort is that it can be used as a base case for quicksort/samplesort, and any partitioning done so far allows fewer steps to be used. I have a case in SingeliSort to do 4-byte sorting that fits in 2-byte range nearly in-place[0]. It's only used on 2^16 elements or fewer to avoid possible cache associativity problems, so that should fit in L2 and not use system bandwidth. Comparison-based algorithms I consider most relevant at the moment are fluxsort/crumsort/quadsort (all by the same author; they share many pieces), ipnsort (largely derived from those plus pdqsort but it may be easier to read), and glidesort somewhat (the gliding technique is cool but I think there are flaws to address, see [1]). For distribution sorting, there's radix, the version of counting sort where you reconstruct from counts instead of moving the data (output can be vectorized with a scan for large ranges!), and I've developed Robin Hood sort to take advantage of smooth-ish distributions such as uniform random. I keep notes at [2], which are pretty out of date. I should be writing there instead of here... I of course don't think there's any requirement to know all this to contribute to sorting research. I take issue with making blanket claims like "I'd consider AVX2 to be table stakes for any sorting algorithm" and "anything as energy-inefficient as scalar code running on big OoO cores is a hard sell" without being familiar with the state of the art in scalar sorting. [0] https://github.com/mlochbaum/SingeliSort/blob/master/src/radix.singeli#L120-L128 https://github.com/mlochbaum/SingeliSort/blob/master/src/rad... [1] https://github.com/Voultapher/sort-research-rs/pull/6#issuecomment-1588172671 https://github.com/Voultapher/sort-research-rs/pull/6#issuec... [2] https://mlochbaum.github.io/BQN/implementation/primitive/sort.html https://mlochbaum.github.io/BQN/implementation/primitive/sor...

pjmlp 3y ago

Last time I checked, there are more than two C++ compilers.