6 ms·

(Frequent AVX-512 user, opinions are my own.) It is time to stop quoting this rant, which is rather far removed from actual practice and reality. Specifically

by janwas 3y ago

(Frequent AVX-512 user, opinions are my own.) It is time to stop quoting this rant, which is rather far removed from actual practice and reality. Specifically for sorting, Intel's sort and ours can be about 10x as fast as scalar. AVX-512 has high power? Great! Power is work per time. Let's have more of that. It is _useful_ work per _energy spent_ that we want to maximize, and there scalar code falls flat. Consider that OoO scheduling/control overhead is the real culprit; executing one instruction costs far more energy than the actual operation. SIMD divides that fixed cost over 16 elements, leading to 5-10x higher power efficiency. Top frequency reduction? Not since the first implementation on Skylake, and even there a non-issue, see https://github.com/google/highway/blob/master/hwy/contrib/sort/README.md#study-of-avx-512-downclocking https://github.com/google/highway/blob/master/hwy/contrib/so.... More cores? The shared-memory fabric is already bursting at the seams (see on-chip bottlenecks of Genoa), we are already cramming in too many for the current memory interface. What would actually be necessary: more bandwidth! A64FX CPUs actually beat GPUs in 2019 for supercomputing applications thanks to their HBM. Intel's Sappire Rapids Max also has this. Let's build more of those, at a decent price. And start using the wide vector units, they are there precisely because lots of highly-clocked cores in one big NUMA domain is not always the best way forward.

HuhWhatMeansYou 3y ago
[dead]
mlochbaum 3y ago
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.
cmrdporcupine 3y ago
More bandwidth, and more or wider cache lines, maybe. From my crude benchmarking, pretty sure a lot of the oomph in Apple's M1 is that 128-byte cache line. 512-byte SIMD operations are great, but if I'm constantly having to copy things over to SIMD registers to do it... am I really winning? More cores just means more cache evictions / contention in many workloads.

by janwas 3y ago

HuhWhatMeansYou 3y ago

[dead]

mlochbaum 3y ago

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.

cmrdporcupine 3y ago

More bandwidth, and more or wider cache lines, maybe. From my crude benchmarking, pretty sure a lot of the oomph in Apple's M1 is that 128-byte cache line. 512-byte SIMD operations are great, but if I'm constantly having to copy things over to SIMD registers to do it... am I really winning? More cores just means more cache evictions / contention in many workloads.