3 ms·

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 searchi

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
> vqsort authors found that at 1e8 elements a hybrid of ips4o (samplesort, think many-way partition) beats pure vqsort. Whoa, important caveat there: we did the hybrid with ips4o as an easy way of getting multicore support. We also mention pure scalar ips4o is slower than vqsort until it can use _19 threads_ (vs one for vqsort). It is the combination of multiple threads (to compensate for the much slower scalar code) and bandwidth friendliness that makes this hybrid useful.
- mlochbaum 3y ago
  Apologies, I misread that section and thought the only difference between tables 1 and 2 was the array size! Thanks for correcting my impression here, that's good to know. And very sorry for the misrepresentation.

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

> vqsort authors found that at 1e8 elements a hybrid of ips4o (samplesort, think many-way partition) beats pure vqsort. Whoa, important caveat there: we did the hybrid with ips4o as an easy way of getting multicore support. We also mention pure scalar ips4o is slower than vqsort until it can use _19 threads_ (vs one for vqsort). It is the combination of multiple threads (to compensate for the much slower scalar code) and bandwidth friendliness that makes this hybrid useful.

mlochbaum 3y ago
Apologies, I misread that section and thought the only difference between tables 1 and 2 was the array size! Thanks for correcting my impression here, that's good to know. And very sorry for the misrepresentation.