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

11–20 of 66 posts

Re: Sorting with SIMD

#11

Post by anonymoushn »

bee_rider wrote: post #9
anonymoushn wrote: post #7

Earlier quoted context omitted.

Yes. If the input is bounded in a narrow range compared to the length if the input, it seems like it should actually be a bit slower than normal, since the first few passes may do nothing and the later passes will need to be run on more of the input than normal. We're using it for arrays of doubles that have fairly small exponents though, and this causes us to have lots of empty buckets in the first pass, and it perf…

Cool! I should probably not have commented, I haven’t really kept up with advances in sorting, haha. I assumed it was basically done to death 20 years ago. This will spur some reading I think! Thanks.

Please do comment in situations like this.

It's tough to find a good overview of this topic that includes recent work or that is aimed at empirical performance. That's part of why TFA is great!

A version of MSB radix sort for sorting ints, doubles, or floats, or sorting structs by a single key of those types is here[0] and a version for sorting strings is here[1]. These are based on the MSB radix sort from this repository[2] which is associated with a technical report about parallel string sorts. I was only interested in sequential sorts, but this repository turned out to be a great resource anyway.

[0]: https://github.com/alichraghi/zort/blob/main/src/radix.zig

[1]: https://github.com/dendibakh/perf-challenge6/blob/Solution_R...

[2]: https://github.com/bingmann/parallel-string-sorting

Re: Sorting with SIMD

#12

Post by Dwedit »

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), or you simply output a list of array indexes that represents what the sort order should be (fast).

Code that doesn't physically move the object memory around creates indirection. Indirection makes any SIMD sorting depend on scatter-gather in order to get data in. Scatter-Gather causes random memory accesses which don't cache as well as sequential access.

Re: Sorting with SIMD

#13

Post by dan-robertson »

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 or the array of indices 1, 2, …, n so you can use that to do accesses to corresponding elements in your other associated columns.

Re: Sorting with SIMD

#14

Post by adrian_b »

wolf550e wrote: post #4

128bit SIMD on x86 is called SSE, not AVX. AVX is 256bit. SSE (first introduced with the Pentium 3) had many extensions that added instructions: SSE2, SSE3, SSSE3, SSE4.1, SSE4.2 and some others.

For most 128-bit SSE instructions, there are equivalent 128-bit AVX instructions, which differ from them by allowing 3 register addresses instead of 2 register addresses, and by not causing execution stalls when they are mixed with 256-bit AVX instructions.

For most AVX instructions, you may choose between 128-bit and 256-bit instructions, which is especially useful on those CPUs where 256-bit instructions cause down-clocking.

There are also 128-bit AVX-512 instructions and 256-bit AVX-512 instructions.

So the same SIMD algorithm may be implemented for Intel CPUs using either 128-bit SSE instructions or 128-bit AVX instructions or 128-bit AVX-512 instructions or 256-bit AVX instructions or 256-bit AVX-512 instructions or 512-bit AVX-512 instructions.

Re: Sorting with SIMD

#16

Post by boberoni »

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.

I thought that blurring a photo would set each pixel to the average color value of all its neighbors. Since information is lost, how could you reverse engineer a blurred photo?

Re: Sorting with SIMD

#17

Post by lucb1e »

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.

The threads are right next to each other, might you have meant to reply here? https://news.ycombinator.com/item?id=34031568 "Unredacter: Never use pixelation [for] redaction"

Re: Sorting with SIMD

#18

Post by [deleted] »

wolf550e wrote: post #4

128bit SIMD on x86 is called SSE, not AVX. AVX is 256bit. SSE (first introduced with the Pentium 3) had many extensions that added instructions: SSE2, SSE3, SSSE3, SSE4.1, SSE4.2 and some others.

[deleted]

Re: Sorting with SIMD

#19

Post by ww520 »

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…

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.

Post reply on HN