Fast bitset decoding using Intel AVX-512

https://lemire.me/blog/2022/05/06/fast-bitset-decoding-using-intel-avx-512/

by ngaut • 4 years ago

62 19 4 years ago

sylware• 4 years ago

I would prefer assembly code than C intrinsics (I usually go for the intel syntax).

rincebrain4• 4 years ago

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.

ygra• 4 years ago

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.

alephnil• 4 years ago

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.

anko• 4 years ago

cool stuff! I was trying to do something similar on Arm Neon (m1 pro) with the CNT instruction https://developer.arm.com/documentation/ddi0596/2020-12/SIMD...

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.

rincebrain4• 4 years ago

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

carlmr• 4 years ago

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.

rincebrain4• 4 years ago

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.

jiggawatts• 4 years ago

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

zasdffaa2• 4 years ago

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)*

gpderetta• 4 years ago

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.

tyldum• 4 years ago

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.

janwas• 4 years ago

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.

Const-me• 4 years ago

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

planede• 4 years ago

Just avoid PDEP/PEXT on AMD before Zen3, it's there, but it's emulated in microcode and slow.

Fast bitset decoding using Intel AVX-512

Related Stories