Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sorting with SIMD

tweedegolf.nl

Post reply on HN
Print view View original

31–40 of 66 posts

Re: Sorting with SIMD

#31

Post by geysersam »

Dwedit wrote: post #12

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 objects in an array, the objects will have one member which is a Key that you will sort the objects on. In order to create a sorted permutation of the list, you either need to rearrange the list of object pointers (fast), rearrange the memory of the objects (slow), o…

Would using a structure-of-arrays (instead of array-of-structues) make this less of a problem?

Re: Sorting with SIMD

#32

Post by hoten »

dan-robertson wrote: post #13
Dwedit wrote: post #12

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 objects in an array, the objects will have one member which is a Key that you will sort the objects on. In order to create a sorted permutation of the list, you either need to rearrange the list of object pointers (fast), rearrange the memory of the objects (slow), o…

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]] I think with simd you’d want to sort your array and simultaneously permute either a second array o…

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

Re: Sorting with SIMD

#33

Post by ww520 »

Has anyone been working on using SIMD on sorting networks? For the 16-input network, for each stage on the first half of the pipeline, all comparisons have no dependency and seems to be a good candidate for SIMD.

Re: Sorting with SIMD

#34

Post by 0xf00ff00f »

ww520 wrote: post #33

Has anyone been working on using SIMD on sorting networks? For the 16-input network, for each stage on the first half of the pipeline, all comparisons have no dependency and seems to be a good candidate for SIMD.

I played a bit with sorting 8 floats in 2 SSE registers with a sorting network. I had a bit of trouble shuffling the registers so the values would be in the right places, so I ended up brute-forcing it:

https://github.com/0xf00ff00f/short-simd-sorter

I don't know if you could use the same idea to sort 16 values in 2 AVX registers. There's probably a better way.

Re: Sorting with SIMD

#35

Post by Dwedit »

geysersam wrote: post #31
Dwedit wrote: post #12

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 objects in an array, the objects will have one member which is a Key that you will sort the objects on. In order to create a sorted permutation of the list, you either need to rearrange the list of object pointers (fast), rearrange the memory of the objects (slow), o…

Would using a structure-of-arrays (instead of array-of-structues) make this less of a problem?

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.

Re: Sorting with SIMD

#36

Post by pizza »

rikschennink wrote: post #15

This is why with redact.photo I randomly shuffle the pixels before blurring so it looks like you can reverse engineer it but you’ll just get scrambled pixels.

Hah.. but by shuffling you preserve the number of white and black pixels, which may make it possible to reverse ;)

Re: Sorting with SIMD

#37

Post by Kon-Peki »

fathyb wrote: post #24
the__alchemist wrote: post #23

When would you use SIMD vice a GPU? (Eg Vulkan comp shader) Is it easier to write for CPU, but you bring in the GPU shader if doing massively parallel ops vice just a few? I've skimmed a Rust lib that uses CPU SIMD (GLAM), and it used a diff syntax from normal, so I'm not positive it would be easier if you're familiar with the GPU process.

It depends how much, where, and when you'd like the data to be sent? Most discrete GPUs cannot access the CPU memory directly, so you need to make a copy through the PCI bus, which can be slow. If you have small chunks of data (mining), or your destination is the screen (video game), it might make sense to use the GPU. If you need high-throughput, low latency, or your destination is something like a sound card (DAW),…

> Fast integrated GPUs like Apple's allow for directly accessing the main memory without copy, making the GPU more viable for general purposes.

My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be extremely fast). Metal Buffers use raw bytes so they will work well with C/C++ arrays, but if you are using something like a Swift array, that is not such an easy to use pairing - you can only get a Swift UnsafeMutableRawPointer to the data.

Further complicating things is that for the best GPU compute performance on Apple Silicon, you want to use Metal Buffers that are private to the GPU, forcing you to use a "blit" operation to copy data to/from CPU-visible memory.

I've been exploring general purpose computing with both CUDA and Apple Silicon and am having a lot better luck using SIMD intrinsics instead. While the GPU compute is incredibly fast, there is just so much time spent synchronizing data. There really seems to be some sweet spot where the GPU wins out, but in a lot of general purpose uses you won't ever get there. But I would really like to be shown that I'm wrong!!!

PS - the very basic ARM Neon stuff that the M1 supports is insanely fast and gets even better when you use multiple threads.

Re: Sorting with SIMD

#38

Post by fathyb »

Kon-Peki wrote: post #37
fathyb wrote: post #24

Earlier quoted context omitted.

It depends how much, where, and when you'd like the data to be sent? Most discrete GPUs cannot access the CPU memory directly, so you need to make a copy through the PCI bus, which can be slow. If you have small chunks of data (mining), or your destination is the screen (video game), it might make sense to use the GPU. If you need high-throughput, low latency, or your destination is something like a sound card (DAW),…

> Fast integrated GPUs like Apple's allow for directly accessing the main memory without copy, making the GPU more viable for general purposes. My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be ext…

> My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be extremely fast).

You have to use Metal Buffers, but you don't have to copy, as long as it is properly page aligned [0]. The YUV data from both camera is for example.

> PS - the very basic ARM Neon stuff that the M1 supports is insanely fast and gets even better when you use multiple threads.

It is, these chips have so much to give!

[0]: https://developer.apple.com/documentation/metal/mtldevice/14...

Re: Sorting with SIMD

#39

Post by Kon-Peki »

fathyb wrote: post #38
Kon-Peki wrote: post #37

Earlier quoted context omitted.

> Fast integrated GPUs like Apple's allow for directly accessing the main memory without copy, making the GPU more viable for general purposes. My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be ext…

> My understanding (and I would be very happy for any clarifications/corrections!) is that you must use Metal Buffers (MTLBuffer) with the Apple Silicon GPU. If your data isn't already in a Metal Buffer (why would it be?), you have to do a copy into a buffer (but it will be extremely fast). You have to use Metal Buffers, but you don't have to copy, as long as it is properly page aligned [0]. The YUV data from both ca…

I have just been nerd sniped.

EDIT - any hints on how to get a plain-old Swift array to be allocated in a conforming alignment (4096 bytes on Apple Silicon)?

Re: Sorting with SIMD

#40

Post by Const-me »

I recently tried to do that as well, but failed. Specifically, I have implemented AA sort [1] but for my use case the performance was about the same as std::sort in C++, for the substantial code complexity cost. I reverted to std::sort. The code is on github [2]

Still, in that particular project the vectors being sorted are relatively small, typically under than 100kb, so I have only implemented their “inner” algorithm which works on a single CPU core. The complete AA sort algorithm was apparently designed for large vectors, and uses both SIMD and multithreading. Might be still useful for very long vectors.

[1] https://ieeexplore.ieee.org/document/4336211

[2] https://github.com/Const-me/fTetWild/blob/master/MeshRepair/...

Post reply on HN