4 ms·

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/pvl

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

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