Fast bitset decoding using Intel AVX-512(lemire.me)
lemire.me
Fast bitset decoding using Intel AVX-512
https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/
19 comments
It's sad that Intel isn't rolling out AVX-512 more consistently, especially now that their new 10nm process doesn't have such as big clock frequency penalty for using these wide instructions.
If the rumours are true that AMD Zen 4 will have AVX-512, then it'll be yet another sad corporate failure of watching a small underdog competitor show you how you are supposed to be managing your own flagship products...
If the rumours are true that AMD Zen 4 will have AVX-512, then it'll be yet another sad corporate failure of watching a small underdog competitor show you how you are supposed to be managing your own flagship products...
I've read that the value of avx512 as separate instructions isn't high, and this kind of confirms it - a 20% speedup[1] over the next best (ns/value) isn't spectacular and seems to bring a large cost in terms of complexity like dropping the clock (and are there really 512-wide paths on the chip?) and just a bunch of new instructions. Perhaps deep pipelining would have been better based on existing instrructions.
Can anyone with actual hardware experience comment?
[1] Have I got that wrong? Is it 25%
(edited to de-screw formatting)*
Can anyone with actual hardware experience comment?
[1] Have I got that wrong? Is it 25%
(edited to de-screw formatting)*
I don't have the technical details, but I work in a field moving from FPGAs to CPU and all solutions require AVX512. These are software defined radios.
The vendors say there is no other way to make it work on higher bit rates.
I've seen 1.5-1.6x speedups in an image codec, and Quicksort - despite any frequency reduction. As others are saying, it really is a nicer and much more complete instruction set than AVX2.
As far as I understand, even when used with 256 bits paths, the new encoding is quite superior and flexible and it is a good vectorization and compilation target.
I was hoping for a "with hindsight" view from a solid CPU guy, but what you've said is interesting, but can you quantify 'superior' / 'flexible' and why you feel it's a good target compared to an imagined deeply pipelined version of existing instructions? TIA
The most obvious advantage of AVX-512 is that it has mask registers which select the parts of a register that are modified by an operation.
This brings a huge simplification to any loop which must process arrays of variable sizes and alignments.
With SSE or AVX you have to write very complex prologue and epilogue code for loops, to handle the sizes that are not a multiple of the register size and to cope with various alignments. A compiler may be not smart enough to add such code, so it may fail to vectorize a loop, while when the code is written by hand it is hard to avoid bugs.
With AVX-512 handling any size or alignment is trivial and it can also be done automatically by compilers when vectorizing loops.
The second feature is that in AVX-512 there are both gather load and scatter store instructions, which simplify the manual or automatic vectorizing of loops that must access some data structures that do not have the layout required by the SIMD instructions.
Also AVX-512 has a more complete and flexible set of instructions to do various permutations between the parts of the SIMD registers, which also allow the vectorization of some loops that would have been difficult to convert to SIMD instructions when using SSE and AVX.
The net effect of all these features is that many loops that were not worthwhile to convert to SIMD with SSE or AVX, because the resulting programs would have been very complex and would have contained a large number of instructions, can be converted to AVX-512 with little effort and the resulting program has much less instructions than in the SSE/AVX version.
For the loops that are easy to convert to SIMD, e.g. they access only aligned arrays whose size is a multiple of the SIMD register size and there is no need to access other kinds of data structures, e.g. arrays of structures with heterogeneous members, AVX-512 may have no advantage over AVX, except if the target CPU happens to have double throughput with 512-bit registers (true for a part of the server/workstation Intel CPUs).
This brings a huge simplification to any loop which must process arrays of variable sizes and alignments.
With SSE or AVX you have to write very complex prologue and epilogue code for loops, to handle the sizes that are not a multiple of the register size and to cope with various alignments. A compiler may be not smart enough to add such code, so it may fail to vectorize a loop, while when the code is written by hand it is hard to avoid bugs.
With AVX-512 handling any size or alignment is trivial and it can also be done automatically by compilers when vectorizing loops.
The second feature is that in AVX-512 there are both gather load and scatter store instructions, which simplify the manual or automatic vectorizing of loops that must access some data structures that do not have the layout required by the SIMD instructions.
Also AVX-512 has a more complete and flexible set of instructions to do various permutations between the parts of the SIMD registers, which also allow the vectorization of some loops that would have been difficult to convert to SIMD instructions when using SSE and AVX.
The net effect of all these features is that many loops that were not worthwhile to convert to SIMD with SSE or AVX, because the resulting programs would have been very complex and would have contained a large number of instructions, can be converted to AVX-512 with little effort and the resulting program has much less instructions than in the SSE/AVX version.
For the loops that are easy to convert to SIMD, e.g. they access only aligned arrays whose size is a multiple of the SIMD register size and there is no need to access other kinds of data structures, e.g. arrays of structures with heterogeneous members, AVX-512 may have no advantage over AVX, except if the target CPU happens to have double throughput with 512-bit registers (true for a part of the server/workstation Intel CPUs).
AVX-512 has really high potential, but for some reason, LLVM (not sure about GCC) is really bad at effectively using it.
I would prefer assembly code than C intrinsics (I usually go for the intel syntax).
I've recently become convinced intrinsics have a strong reason to at least try them after I rewrote something that was using inline ASM into intrinsics 1:1, and got a not-insignificant speedup, evidently solely because the compiler was better at optimizing it than I was.
Inline ASM might be somewhat opaque to the compiler and interfere with optimization in general. It's not in the IR format that the optimizer uses; register allocation is probably up to the ASM code, not the compiler's choice, perhaps forcing it to either skip optimizing a complete function, just the block in which inline ASM appears, or even to add additional code outside the block to make it run correctly.
AIUI compilers treat inline ASM as an entirely opaque block they cannot mutate or assume much about, so if you're inlining 100 lines of ASM, you will get the ASM you asked for, for better or worse.
(Treating it as completely opaque is, I believe, also why you can get away with things like inlining AVX2 ASM on an -mno-avx2 build, for example.)
(Treating it as completely opaque is, I believe, also why you can get away with things like inlining AVX2 ASM on an -mno-avx2 build, for example.)
If you use intrinsics, you don't have to deal with the different calling conventions of each operating system, so I have used intrinsics for that reason alone, since I otherwise had to write separate versions for Linux and Windows or have a lot of conditional code.
I think this is the fourth time I've seen this on the front page this week [1][2][3] - it was actually kind of spooky the first time, as I'd just found the author's page after looking into their work on doing SIMD-based processing of other things, and here they were turning up on the front page within 24h.
[1] - https://news.ycombinator.com/item?id=31312175
[2] - https://news.ycombinator.com/item?id=31289483
[3] - https://news.ycombinator.com/item?id=31337165
[1] - https://news.ycombinator.com/item?id=31312175
[2] - https://news.ycombinator.com/item?id=31289483
[3] - https://news.ycombinator.com/item?id=31337165
The question is why you were looking at SIMD based processing, maybe you got triggered by another HN post, which triggers this post being reposted more often.
We're each cells in a neutral meta network, triggering each other.
We're each cells in a neutral meta network, triggering each other.
I was looking at SIMD processing for interests not triggered by HN, actually - was trying to figure out how well one could do at efficient binpacking of a structure where you knew something about the contents beyond it being arbitrary noise, as fast as you could get away with it.
Right, unpacking numbers like that is pretty efficient in AVX512.
Still, modern processors have BMI2. For some practical applications, the PEXT instruction is pretty comparable, here’s an example: https://stackoverflow.com/a/72106877/126995
Still, modern processors have BMI2. For some practical applications, the PEXT instruction is pretty comparable, here’s an example: https://stackoverflow.com/a/72106877/126995
Just avoid PDEP/PEXT on AMD before Zen3, it's there, but it's emulated in microcode and slow.
I believe it does 128 bits per instruction, but I'm still struggling with rust w/ asm.
Along my journeys, however, I found this repo https://github.com/WojciechMula/sse-popcount/ which has tons of competing simd implementations for both intel and arm.