Hacker News Reader

Comment by Waterluvian | Hacker News Reader

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?

View on HN

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

To add to this:

A really good, digestible talk about using SIMD for sorting: 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

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.

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

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

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.

>btree

That's literally a collection of arrays that needs to be sorted. And it's still a traditional sorting.

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

It's important enough that there are whole books written about it.

https://www.amazon.com/Art-Computer-Programming-Sorting-Sear...

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.

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

Reply on news.ycombinator.com