4 ms·

If you are exclusively moving numbers around in an array, SIMD sorting sounds great. But when you want to actually sort things, it's different. You have objec

• dan-robertson 4y ago
  Yeah I find the thing you generally want but which many languages don’t support well is to have a struct-of-arrays or data frame layout rather than an array of objects. Then you can do one of: Sort one array and rearrange other arrays the same way Compute the array of indices into another array such that array[index[i]] < array[index[i+1]], I.e. the sorted version of the array is then [array[i] for i in index]. If you have a vectorised index operation (eg APL, R, …) getting the sorted array is one line of code. I think with simd you’d want to sort your array and simultaneously permute either a second array or the array of indices 1, 2, …, n so you can use that to do accesses to corresponding elements in your other associated columns.
  • hoten 4y ago
    Last I checked, Jai was going this direction (a type modifier that allowed one to do either AOS or SOA) but abandoned it (or at least, abandoned the particular syntax JB originally prototyped).
    • cyber_kinetist 4y ago
      I think they didn't really abandoned it, but were planning to make the metaprogramming facilities powerful enough to just implement them in plain code instead of creating a separate language feature. (Zig has already taken this direction: https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-in-userland-40m0 https://zig.news/kristoff/struct-of-arrays-soa-in-zig-easy-i...)
  • watersb 4y ago
    I've been playing with Intel's "Implicitly Parallel SIMD Compiler" (ISPC) [0]. The ISPC User Guide was easy for me to work through, and there's a section on "Structure of Arrays" (SOA) programming [1]. This approach to vector-parallel programming was new to me, but got me to try some C code for the kernel transformation. My simple applications are probably fast enough in Python, but I thought it quite worthwhile to look at tiny kernels and the code the compiler generates. - [0] https://ispc.github.io/index.html https://ispc.github.io/index.html - [1] https://ispc.github.io/ispc.html#structure-of-array-types https://ispc.github.io/ispc.html#structure-of-array-types
  • ddlutz 4y ago
    Maybe Google's new "Rune" language will become prevalent https://github.com/google/rune https://github.com/google/rune, which supports SoA.
    • Trex_Egg 4y ago
      What's SoA?
      • ithkuil 4y ago
        Struct of Arrays
        • Trex_Egg 4y ago
          Thanks
• ww520 4y ago
  It might be easier for SIMD to work by extracting the key value from each object into its own array. Form an array with fixed element size: [ {index0 | key0}, {index1 | key1}, ...], where indices are the element index to the original array of objects and the keys are fixed size. The fat element {index | key} is moved as a whole unit to carry the original index along with the swap during sorting. SIMD can deal with fixed size units very well.
  • nickelpro 4y ago
    That would be called a gather operation, which is itself slow, exactly as the OP comment said.
• geysersam 4y ago
  Would using a structure-of-arrays (instead of array-of-structues) make this less of a problem?
  • Dwedit 4y ago
    Okay, let's suppose we are defining the problem like this: • ObjectArray, an Array of objects, will be treated as immutable • IndexArray, an array of ints, indexes into the first array. Initialize to [0...N). After sort finishes, this contains an ordering into the first array. Now we want to run the sort. Every time we do a comparison, we read from IndexArray, and use that index into ObjectArray. Every time we do a swap, we only mutate IndexArray. There is guaranteed to be at least one level of indirection, because you need to read from IndexArray to determine which object is actually there. So you get a scatter-gather requirement here for SIMD code. Now for the different ways to represent the array: • Plain pointers to objects (like C# reference types) • One object after the other in a contiguous memory block (Array of structures) • All Keys contiguous in memory (Structure of arrays) If you go with Plain Pointers to objects (reference types in C#), you get an extra read to some object in memory that was allocated elsewhere. Can be a cache miss. If you go with Big Memory Block with objects inside (Array of structures), you avoid the read of the plain pointer value. You calculate the address of a key with a Multiply (by size of object) and an Add (base address). The data that's loaded into the processor cache may be unnecessary for sorting. If you go with All Keys Contiguous in memory (Structure of arrays), you calculate the address of a key with a Bitshift (size of key) and an Add (base address). With keys contiguous in memory, it helps with caching, as you are loading only keys into the cache at that time.
• srcreigh 4y ago
  Yeah. Whether this is faster than normal sort is a big "depends" based on how the sorted data is accessed. SIMD sort with indirection would be nice if you only need to access top 25 or 1/255 items in the array or something. Faster sorting helps pay off the cost of cache misses when accessing the other fields. If you need to sort and then process every item with associated data, I wouldn't be surprised if quicksort on the structs themselves is faster. The cache misses would add up.
• thecompilr 4y ago
  The original (AFAICT) work on SIMD quick sort, also mentioned in the google post also implemented pointer sort by loading a pointed key using gather instructions and the method can be used for an array of structs. https://github.com/vkrasnov/avx_qsort/blob/master/qsort_AVX2_HSW_256bit_ptrs.s https://github.com/vkrasnov/avx_qsort/blob/master/qsort_AVX2...