3 ms·

From what I understand, these sorts are only for direct lists of primitives. For most of the sorts I see, I'm trying to sort an array of structs with an embedde

From what I understand, these sorts are only for direct lists of primitives. For most of the sorts I see, I'm trying to sort an array of structs with an embedded key. I know this organization destroys the memory access patterns that make SIMD effective. Is the best alternative to move the key out of the struct, and sort two arrays: one of primitive keys and another of original indices? This sort would still be very amenable to SIMD. It just requires a final pass where you rearrange the original array with the indices. Alternately, you could avoid sorting an array of indices and try sorting an struct of arrays directly. I don't see a lot of people handling this very frequent situation in these benchmarks. Any pointers?

mlochbaum 3y ago
It depends on the size of the structs. For struct pointers you're likely better off sorting keys and pointers simultaneously. It doesn't matter much until you get to large sizes (millions), but sorting indices and then selecting with them is random access. If the original ordering is messy, selecting can be slower than the sorting step. For structs a few words long, the unit you're moving is a larger portion of a cache line, and I'd expect the data movement to drown out any SIMD advantage. A radix sort might be all right because it moves less, but I'd probably go with sorting indices as the first thing to try unless I knew the arrays were huge. For very large structs there's an interesting effort called mountain sort[0], "probably the best sorting algorithm if you need to sort actual mountains by height". Given that it minimizes number of moves it's ignoring cache entirely. I haven't benchmarked so I can't say much about how practical it is. [0] https://github.com/Morwenn/mountain-sort https://github.com/Morwenn/mountain-sort
BobbyJo 3y ago
In situations where I need to sort a list of large objects, I normally create an separate "OrderedView" or "Ordering" which holds either two lists [comparable_value] and [index] like you describe, or a single list of [comparable_value, index] (depending on the types and languages the second option will be faster). Then it just provides either an iterator. If you only need the ordering once this saves you from going back and re-ordering the original array. If you need to run through the list multiple times, it probably makes sense to actually go back and re-order the original so that the accesses are linear memory. That is, unless the values are pointers in which the indirection will likely kill the benefit.
blt 3y ago
I agree this is a super common case. I don't have a benchmark, but I bet when actually moving structs the C qsort starts looking a lot more reasonable.
anonymoushn 3y ago
Often you can sort a u128 (or smaller integer) that is actually the key and a pointer or the key and an index into an array. You may find that a single pass to rearrange the original array to the sorted order is slower than multiple passes because of cache issues. I would certainly be interested in reading about this sort of thing if you find anything :)

mlochbaum 3y ago

It depends on the size of the structs. For struct pointers you're likely better off sorting keys and pointers simultaneously. It doesn't matter much until you get to large sizes (millions), but sorting indices and then selecting with them is random access. If the original ordering is messy, selecting can be slower than the sorting step. For structs a few words long, the unit you're moving is a larger portion of a cache line, and I'd expect the data movement to drown out any SIMD advantage. A radix sort might be all right because it moves less, but I'd probably go with sorting indices as the first thing to try unless I knew the arrays were huge. For very large structs there's an interesting effort called mountain sort[0], "probably the best sorting algorithm if you need to sort actual mountains by height". Given that it minimizes number of moves it's ignoring cache entirely. I haven't benchmarked so I can't say much about how practical it is. [0] https://github.com/Morwenn/mountain-sort https://github.com/Morwenn/mountain-sort

BobbyJo 3y ago

In situations where I need to sort a list of large objects, I normally create an separate "OrderedView" or "Ordering" which holds either two lists [comparable_value] and [index] like you describe, or a single list of [comparable_value, index] (depending on the types and languages the second option will be faster). Then it just provides either an iterator. If you only need the ordering once this saves you from going back and re-ordering the original array. If you need to run through the list multiple times, it probably makes sense to actually go back and re-order the original so that the accesses are linear memory. That is, unless the values are pointers in which the indirection will likely kill the benefit.

blt 3y ago

I agree this is a super common case. I don't have a benchmark, but I bet when actually moving structs the C qsort starts looking a lot more reasonable.

anonymoushn 3y ago

Often you can sort a u128 (or smaller integer) that is actually the key and a pointer or the key and an index into an array. You may find that a single pass to rearrange the original array to the sorted order is slower than multiple passes because of cache issues. I would certainly be interested in reading about this sort of thing if you find anything :)