Sorting with SIMD
tweedegolf.nl
Sorting with SIMD
1–10 of 66 posts
Re: Sorting with SIMD
#2This is a well written SIMD example I find these are the hardest topic to clearly explain because of how much is happening. Anyone got other nice links I've been doing a lot of vector processing so I need to learn!
Re: Sorting with SIMD
#3This is a well written SIMD example I find these are the hardest topic to clearly explain because of how much is happening. Anyone got other nice links I've been doing a lot of vector processing so I need to learn!
Someone previously shared this YouTube playlist on HN, and I have found it to be very helpful [1].
[1] https://www.youtube.com/playlist?list=PLYCMvilhmuPEM8DUvY6Wg...
Re: Sorting with SIMD
#4128bit 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.
Re: Sorting with SIMD
#5This is a good explanation. Writing the masks in big-endian somewhat obscures things.
As an aside, while recent developments in quicksort are quite good, it seems like MSB radix sort performs comparably to (or slightly better than!) these algorithms on random inputs.
Re: Sorting with SIMD
#6This is a good explanation. Writing the masks in big-endian somewhat obscures things. As an aside, while recent developments in quicksort are quite good, it seems like MSB radix sort performs comparably to (or slightly better than!) these algorithms on random inputs.
Random inputs for which you don’t know the bounds?
Re: Sorting with SIMD
#7This is a good explanation. Writing the masks in big-endian somewhat obscures things. As an aside, while recent developments in quicksort are quite good, it seems like MSB radix sort performs comparably to (or slightly better than!) these algorithms on random inputs.
Random inputs for which you don’t know the bounds?
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 performs well enough.
Re: Sorting with SIMD
#8128bit 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.
That's not entirely true. AVX from the beginning (introduced with Sandy Bridge), not AVX2 (introduced with Haswell), contains 128-bit instructions as well, and these are what's being used in the article (e.g. vpermilps).
Re: Sorting with SIMD
#9Earlier quoted context omitted.
Random inputs for which you don’t know the bounds?
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.
Re: Sorting with SIMD
#10SIMD is a fantastic tool. My first try with AVX2 (256-bit), building an "overlay with transparency" for two YUVA420P frames, yielded speed better than 1 pixel per CPU cycle! Although i didn't even try optimising it all that much.