There is an interesting algorithm for sorting that is highly amenable to parallelization and which I thought this article was going to be about: https://en.wikipedia.org/wiki/Sorting_network
Sorting with SIMD
41–50 of 66 posts
Re: Sorting with SIMD
#42There is an interesting algorithm for sorting that is highly amenable to parallelization and which I thought this article was going to be about: https://en.wikipedia.org/wiki/Sorting_network
Though about that as well. Few years ago I implemented a SIMD sort using those and mergesort.
Re: Sorting with SIMD
#43I wonder why no one mentions bitonic sort? If you want to do anything in SIMD you better avoid branching as much as possible... and ideally altogether. Here is an implementation I co-authored some 10 years ago: https://github.com/zerovm/zerovm-samples/blob/master/disort/...
Sorting-networks which were already mentioned seems similar but a bit too abstract.
My code above doesn't contains values but those are easy to add I think. Of course it is better to permute fixed size pointers / offsets and not the entire blobs which can be of variable size and then it will complicate everything beyond feasible for SIMD
Re: Sorting with SIMD
#44Has 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.
That's pretty cool.
The compare_and_swap ops of the sorting network can be done in SIMD using _mm_min_epi32, _mm_max_epi32, and _mm_blend_epi32. For the 8-value network, they can operate on 4 pairs of the values and 8 pairs for 16-value network, as long as the pairs have no dependency with each other.
Re: Sorting with SIMD
#45Earlier quoted context omitted.
Popular compilers support popular SIMD architectures through “intrinsic” functions. They look and act like regular functions, but they are built in to the compiler and usually compile to a single specific assembly instruction. In the article, _mm_set_epi32 is an intrinsic function that compiles to the instruction of the same name. This is a sharp contrast to inline assembly for which the compiler has practically zero…
Isn’t the reason they had to use inline assembly there because the compiler they’re using doesn’t have that particular instruction bound as an intrinsic? What do you do in that case? I’m genuinely curious as it’s something I’ve run up against: the vector extensions for the LX7 processor in the ESP32-S3 don’t have intrinsics for them.
You continue doing what you are doing.
Intrinsics in many languages are just a file full of inline ASM somewhere.
Re: Sorting with SIMD
#46Earlier quoted context omitted.
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 repos…
[deleted]
Re: Sorting with SIMD
#47If 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. 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.
Re: Sorting with SIMD
#48Is there a particular reason to use direct intrinsics over portable simd?
What is portable simd?
Since the example was using rust, I'm guessing the [std::simd module](https://doc.rust-lang.org/std/simd/index.html), which is currently unstable but would be cool to see put to use here
Re: Sorting with SIMD
#49Nice article, but there are many errors or typo that makes it hard to follow. (Is it a typo or do I not understand that part)
For example, his use of 'unsafe': why functions that don't take pointer are declared as unsafe? Also taking a pointer of an array shouldn't need unsafe. Is 4 > 8 ? Missing close ']'. And that's just the one I see.
I haven't tried compiling the code example, but I don't think they do.
Re: Sorting with SIMD
#50Earlier quoted context omitted.
Popular compilers support popular SIMD architectures through “intrinsic” functions. They look and act like regular functions, but they are built in to the compiler and usually compile to a single specific assembly instruction. In the article, _mm_set_epi32 is an intrinsic function that compiles to the instruction of the same name. This is a sharp contrast to inline assembly for which the compiler has practically zero…
Isn’t the reason they had to use inline assembly there because the compiler they’re using doesn’t have that particular instruction bound as an intrinsic? What do you do in that case? I’m genuinely curious as it’s something I’ve run up against: the vector extensions for the LX7 processor in the ESP32-S3 don’t have intrinsics for them.
There are intrinsics for a wide range of ARM and PowerPC SIMD instructions, a huge range of Intel SIMD instructions and several useful instructions like ByteSwap or FindFirstSetBit on several architectures.
But, there is not an instrinsic for every instruction nor for useful instructions on every architecture. In those cases, you might be lucky to have the compiler recognize very specific patterns in C (compilers are great at recognizing C implementations of byteswap, for example). But, otherwise you’ll have to write inline assembly if you want to utilize those features.