4 ms·

Is sorting one of those things that’s so common that it deserves its own CPU hardware/instructions to aid in performance? Or does AVX-512 provide a lot of what

Is sorting one of those things that’s so common that it deserves its own CPU hardware/instructions to aid in performance? Or does AVX-512 provide a lot of what that would theoretically be?

cbsmith 4y ago
Heck yeah. Sorting is a pretty common operation in tons of algorithms, which is why you find some form of a sort function in pretty much every language's standard runtime. Sure, this won't help much for sorting strings, but numerical sorts are still address a significant chunk of problems.
ygra 4y ago
AVX-512 is not a dedicated sorting instruction set, but rather instructions dedicated to doing the same computations in parallel over 512 bit wide registers. So you can do the same operation in the same time for 8 doubles, 16 integers, or 64 bytes at once. Coming up with good usage of those instructions can be tricky. It's not just the typical arithmetic things, but also instructions that shuffle around values in those registers based on values elsewhere and combining all that cleverly then can yield speed-ups for algorithms that deal with lots of data serially. A while ago while trying to understand all that (for the older instruction sets) I've read this CodeProject article: https://www.codeproject.com/Articles/874396/Crunching-Numbers-with-AVX-and-AVX https://www.codeproject.com/Articles/874396/Crunching-Number... – AVX-512 is basically similar, just wider. Although I've heard it has a few more useful instructions as well that have no counterpart in the older instruction sets.
- yonifei 4y ago
  To add to this: A really good, digestible talk about using SIMD for sorting: https://www.youtube.com/watch?v=M6HaSvifxwQ https://www.youtube.com/watch?v=M6HaSvifxwQ You can also read the author's blog post series, beginning at https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1 https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1
jacquesm 4y ago
It's important enough that there are whole books written about it. https://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 https://www.amazon.com/Art-Computer-Programming-Sorting-Sear...
softwaredoug 4y ago
Lots of things are sorted: search results, recommendations, your news feed
bee_rider 4y ago
That’s a kind of interesting idea. Better implementations of sorting algorithms will go down to a small-ish base case and then do a linear sort. Maybe with AVX512 sized registers there’s room for a “sort the register” instruction to act as the base case, haha.
frankreyes 4y ago
Just to pick a random example: creating an SQL database with an index for faster search requires sorting
- Someone 4y ago
  Except for the special case of loading data into an empty table that already has an index, that requires repeatedly inserting items in a sorted ‘list’ (more likely a btree), keeping it sorted. That’s quite a different thing.
  - frankreyes 4y ago
    >btree That's literally a collection of arrays that needs to be sorted. And it's still a traditional sorting.
speed_spread 4y ago
"Ordinateur", which is French for "computer", literally means "sorting machine". So wherever the sorting instructions would go, the computer would follow.
Waterluvian 4y ago
I really should have clarified that I understand that sorting is important. Hence why wondering if it deserves its own instructions. ;)

Is sorting one of those things that’s so common that it deserves its own CPU hardware/instructions to aid in performance? Or does AVX-512 provide a lot of what that would theoretically be?

cbsmith 4y ago

Heck yeah. Sorting is a pretty common operation in tons of algorithms, which is why you find some form of a sort function in pretty much every language's standard runtime. Sure, this won't help much for sorting strings, but numerical sorts are still address a significant chunk of problems.

ygra 4y ago

AVX-512 is not a dedicated sorting instruction set, but rather instructions dedicated to doing the same computations in parallel over 512 bit wide registers. So you can do the same operation in the same time for 8 doubles, 16 integers, or 64 bytes at once. Coming up with good usage of those instructions can be tricky. It's not just the typical arithmetic things, but also instructions that shuffle around values in those registers based on values elsewhere and combining all that cleverly then can yield speed-ups for algorithms that deal with lots of data serially. A while ago while trying to understand all that (for the older instruction sets) I've read this CodeProject article: https://www.codeproject.com/Articles/874396/Crunching-Numbers-with-AVX-and-AVX https://www.codeproject.com/Articles/874396/Crunching-Number... – AVX-512 is basically similar, just wider. Although I've heard it has a few more useful instructions as well that have no counterpart in the older instruction sets.

yonifei 4y ago
To add to this: A really good, digestible talk about using SIMD for sorting: https://www.youtube.com/watch?v=M6HaSvifxwQ https://www.youtube.com/watch?v=M6HaSvifxwQ You can also read the author's blog post series, beginning at https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1 https://bits.houmus.org/2020-01-28/this-goes-to-eleven-pt1

jacquesm 4y ago

It's important enough that there are whole books written about it. https://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 https://www.amazon.com/Art-Computer-Programming-Sorting-Sear...

softwaredoug 4y ago

Lots of things are sorted: search results, recommendations, your news feed

bee_rider 4y ago

That’s a kind of interesting idea. Better implementations of sorting algorithms will go down to a small-ish base case and then do a linear sort. Maybe with AVX512 sized registers there’s room for a “sort the register” instruction to act as the base case, haha.

frankreyes 4y ago

Just to pick a random example: creating an SQL database with an index for faster search requires sorting

Someone 4y ago
Except for the special case of loading data into an empty table that already has an index, that requires repeatedly inserting items in a sorted ‘list’ (more likely a btree), keeping it sorted. That’s quite a different thing.
- frankreyes 4y ago
  >btree That's literally a collection of arrays that needs to be sorted. And it's still a traditional sorting.

speed_spread 4y ago

"Ordinateur", which is French for "computer", literally means "sorting machine". So wherever the sorting instructions would go, the computer would follow.

Waterluvian 4y ago

I really should have clarified that I understand that sorting is important. Hence why wondering if it deserves its own instructions. ;)