6 ms·
Intel Releases x86-SIMD-sort 2.0 With Faster AVX-512 Sorting, New Algorithms
- hedora 3y agoAre these significantly faster than the 256 bit versions? They compare to non-simd, but that’s less interesting. Also, it’s unfortunate that this stuff won’t run on most developer machines.
- mgaunard 3y agoYou don't need avx512 to implement a bitonic sort. I worked on several implementations with plain avx.
- vardump 3y agoOr SSE2+.
- RaisingSpear 3y agoAVX-512's VPCOMPRESS* instructions are very useful for binary-radix sorting though.
- janwas 3y agoYes, can be about 1.6x speedup: https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#addendum https://github.com/Voultapher/sort-research-rs/blob/main/wri... (cpp_intel_avx512). Disclosure: I am the main author of vqsort, which is also a vectorized Quicksort but portable.
- jackmott42 3y agoIt can often be more than you would expect from the width increase, as lots of masking tools and instructions allow you to vectorize things more efficiently than could be done before.
- deleted 3y ago[deleted]
- adgjlsfhk1 3y agoThe 512 bit registers are the least important part of AVX-512. The much more important parts are the 32 registers, mask registers (these are great for quicksort), compressed displacement (which shrinks the instruction size for unrolled code), and a bunch of other goodies.
- tecleandor 3y agoWhat kind of processes are heavily (or, at least, moderately) impacted by the performance improvement of sorting algorithms? By my lack of knowledge (and the heat of today :0 ) can't guess what algorithms or processes do lots of sorting behind the scenes.
- djxfade 3y agoDatabases would be me suggestion
- YetAnotherNick 3y agoI might be wrong but I don't think any databases operation is limited by sorting. Even naive quicksort with compiler optimization performs very fast and it is much more faster than reading from disk even with extra log n factor. Maybe things like redis sorted sets could benefit from it, but most implementations of things like these are priority queue.
- zeroimpl 3y agoIt’s pretty common for most SQL queries to be reading data that is entirely cached in memory. In these cases, the performance limitations often come from sorts or hash joins.
- cmrdporcupine 3y ago(Hopefully) gone are the days when DBs are spending the bulk of their time blocking in I/O waiting for spinning disks to spin. They spend a lot of intelligence on keeping active tuples paged-in, and memory sizes are exponentially bigger than they used to be, and intelligent query optimization is going to do as much as it can into memory and then apply join algorithms which... are usually sorts. And even writes, there's sorting there. An LSM or a B-epsilon-tree, etc. they're doing sorting and ordered key traversals before paging out.
- deleted 3y ago[deleted]
- 3y ago
- cientifico 3y agoA interesting reading related to this is the thoughts of Linus about AVX-512 back in 2020: https://www.phoronix.com/news/Linus-Torvalds-On-AVX-512 https://www.phoronix.com/news/Linus-Torvalds-On-AVX-512 My conclusion (feel free to enlighten me if I am wrong) is that a system will profit by having more cores instead of AVX-512 for the same power consumption.
- qayxc 3y agoI won't say you're wrong, but the answer might depend heavily on the application.
- gmokki 3y agoAMD enabled AVX-512 without increasing their power consumption. To do that their AVX-512 runs only half of max speed compared Intel when using 512 bit registers (aka max flops is same as with AVX2 256 bit registers). Still, because the new instructions in AVX-512 are beneficial in many scenarios the actual speed up is still often 10-20% in code that benefits from the new instructions. Then 4 years later AMD has the option to bump to full-speed AVX-512 if it is really needed. This is the same they did with AVX2 initially.
- adrian_b 3y agoNo, this (AMD running at half speed) is a myth. For most instructions AMD runs the 512-bit instructions at exactly the same speed as Intel. Both Intel and AMD execute either two 512-bit instructions per cycle (most simpler instructions) or one 512-bit instruction per cycle (a few of the more complex instructions). The reason is that AMD executes four 256-bit instructions per cycle (and Intel only three, with a fourth 256-bit section that can be used only by the AVX-512 instructions). Both Intel and AMD pair 256-bit sections to execute 512-bit operations at half rate, but equal throughput (the effective throughput actually increases due to lower overhead). The main exception is that some of the models of Intel Sapphire Rapids, only the most expensive of them, i.e. Xeon Platinum and most of the Xeon Gold models, have a second FMA unit, so only these models are able to execute two 512-bit FMA instructions per cycle, while Zen 4 can execute only one 512-bit FMA instruction + one 512-bit FADD instruction per cycle. The second advantage of Intel is that it has double bandwidth towards the L1 cache, which is absolutely necessary for Intel, because otherwise it would have been impossible to provide the operands for two FMA instructions per cycle. While the more expensive Intel models have this FMA throughput advantage, there are also many AVX-512 instructions where AMD has lower latencies than Intel. AMD has also higher clock frequencies when all the cores are busy, and also higher memory throughput, so the result is that for many AVX-512 workloads a Zen 4 beats easily a Sapphire Rapids. The main applications where Intel wins are those that depend mainly on FMA, i.e. linear algebra operations on dense arrays, e.g. DGEMM or LINPACK.
- jaxrtech 3y agoIs there an equivalent to caniuse.com for gauging the level of instruction set extension support on x86 and ARM in the wild?
- daveoc64 3y agoThe Steam Hardware Survey "Other Settings" section lists the prevalence of various extensions among users that have taken the survey: https://store.steampowered.com/hwsurvey/Steam-Hardware-Software-Survey-Welcome-to-Steam https://store.steampowered.com/hwsurvey/Steam-Hardware-Softw... The data set is a mixed bag though. Some types of system are going to be over-represented.
- janwas 3y agoYes, I've recently heard some mention of this survey being skewed/buggy, which is a pity because I do not know anything better. IIRC Linux systems were underrepresented.
- vkaku 3y agoThe client CPUs released until present do not have AVX-512 sadly. I'm not planning any hardware updates for the next 3 years at least. Not relevant for me at least.
- sagarm 3y agoFaster, but still 15-25% slower than Highway's vqsort according to my somewhat amateur tests: ------------------------------------------------------------ Benchmark Time Bytes Items ------------------------------------------------------------ Hwy/random 2.16 s 474.1M/s 62.1M/s Hwy/sorted_runs 2.29 s 446.7M/s 58.5M/s IntelX86SIMD/random 2.90 s 353.9M/s 46.3M/s IntelX86SIMD/sorted_runs 2.68 s 382.4M/s 50.1M/s https://github.com/funrollloops/parallel-sort-bench https://github.com/funrollloops/parallel-sort-bench
- eesmith 3y agoSee also "10~17x faster than what? A performance analysis of Intel's x86-simd-sort (AVX-512)" at https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md https://github.com/Voultapher/sort-research-rs/blob/main/wri... posted here at https://news.ycombinator.com/item?id=36273544 https://news.ycombinator.com/item?id=36273544 and minor additional comments at https://news.ycombinator.com/item?id=36268877 https://news.ycombinator.com/item?id=36268877 . When those benchmarks were first done, for random input, vqsort was faster once you get around ~20,000 items, but for 1,000 items the new AVX512 sort is 13x faster than vqsort. As you read it, you'll see that the vqsort issue for small arrays has been fixed, and as of a few weeks ago or so, vqsort is now faster than the AVX512 sort for random.