https://lemire.me/blog/2023/06/29/dynamic-bit-shuffle-using-avx-512/ Skip to content Daniel Lemire's blog Daniel Lemire is a computer science professor at the Data Science Laboratory of the Universite du Quebec (TELUQ) in Montreal. His research is focused on software performance and data engineering. He is a techno-optimist and a free-speech advocate. Menu and widgets * My home page * My papers * My software Join over 12,500 email subscribers: [ ][Go!] You can follow this blog on telegram. You can find me on twitter as @lemire or on Mastodon. Search for: [ ] [Search] Support my work! I do not accept any advertisement. However, you can you can sponsor my open-source work on GitHub. Recent Posts * Dynamic bit shuffle using AVX-512 * Science and Technology links (June 25 2023) * Citogenesis in science and the importance of real problems * Science and Technology links (June 11 2023) * Parsing IP addresses crazily fast Recent Comments * Daniel Lemire on Dynamic bit shuffle using AVX-512 * Sasha Krassovsky on Dynamic bit shuffle using AVX-512 * camel-cdr on Dynamic bit shuffle using AVX-512 * MajorTom on Dynamic bit shuffle using AVX-512 * camel-cdr on Dynamic bit shuffle using AVX-512 Pages * A short history of technology * About me * Book recommendations * Cognitive biases * Interviews and talks * My bets * My favorite articles * My favorite quotes * My readers * My rules * Newsletter * Predictions * Privacy Policy * Recommended video games * Terms of use * Write good papers Archives Archives [Select Month ] Boring stuff * Log in * Entries feed * Comments feed * WordPress.org Dynamic bit shuffle using AVX-512 Suppose that you want to reorder, arbitrarily, the bits in a 64-bit word. This question was raised on Twitter by @experquisite. Formally, you might want to provide, for each of the 64 bit position, an original bit position you want to copy. Hence, the following code would reverse the bit order in your 64-bit word: uint64_t w = some value; uint8_t indexes[64] = {63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; bit_shuffle(w, indexes); // returns a reversed version A naive way to do it in C might be as follows: uint64_t slow_bit_shuffle(uint64_t w, uint8_t indexes[64]) { uint64_t out{}; for (size_t i = 0; i < 64; i++) { bool bit_set = w & (uint64_t(1) << indexes[i]); out |= (uint64_t(bit_set) << i); } return out; } This might be an acceptable implementation, but what if you want do it using few instructions? You can do it on recent Intel and AMD processors with support for AVX-512 instructions. You go from the general-purpose register to a mask register, to a 512-bit AVX-512 register, you apply a shuffle (vpermb), you go back to a mask register and finally back to a general-purpose register. The code with Intel intrinsic functions looks as follows: uint64_t bit_shuffle(uint64_t w, uint8_t indexes[64]) { __mmask64 as_mask = _cvtu64_mask64(w); __m512i as_vec_register = _mm512_maskz_mov_epi8(as_mask, _mm512_set1_epi8(0xFF)); __m512i as_vec_register_shuf = _mm512_permutexvar_epi8(_mm512_loadu_si512(indexes), as_vec_register); return _cvtmask64_u64(_mm512_movepi8_mask(as_vec_register_shuf)); } It might compile to about six instructions: kmovq k0, rdi vpmovm2b zmm0, k0 vmovdqu8 zmm1, ZMMWORD PTR [rsi] vpermb zmm0, zmm1, zmm0 vpmovb2m k1, zmm0 kmovq rax, k1 As one reader points out, you can do better because AVX-512 has a dedicated instruction for bit shuffling which directly returns a mask and work directly from the 64-bit word as long as it is loaded in a vector register: uint64_t faster_bit_shuffle(uint64_t w, uint8_t indexes[64]) { __m512i as_vec_register = _mm512_set1_epi64(w); __mmask64 as_mask = _mm512_bitshuffle_epi64_mask(as_vec_register, _mm512_loadu_si512(indexes)); return _cvtmask64_u64(as_mask); } The resulting assembly is quite short: vpbroadcastq zmm0, rdi vpshufbitqmb k0, zmm0, ZMMWORD PTR [rsi] kmovq rax, k0 Loading your indexes is likely to have a long latency, so if you can buffer the load (_mm512_loadu_si512(indexes)), you will reduce significantly the latency. I have an implementation in C++. Published by [2ca999] Daniel Lemire A computer science professor at the University of Quebec (TELUQ). View all posts by Daniel Lemire Posted on June 29, 2023June 30, 2023Author Daniel LemireCategories 10 thoughts on "Dynamic bit shuffle using AVX-512" 1. [e03257] -.- says: June 29, 2023 at 8:48 pm Likely faster to just use the purpose built vpshufbitqmb: https:/ /godbolt.org/z/qssovhbcr Reply 1. [2ca999] Daniel Lemire says: June 29, 2023 at 9:51 pm Blog post updated, thanks. Reply 1. [4bc21a] Sasha Krassovsky says: June 30, 2023 at 7:07 pm Have you profiled bitshuffle? I remember trying to implement bit unpacking with it and it was MUCH slower than the AVX2 version of fastunpack. Reply 1. [2ca999] Daniel Lemire says: June 30, 2023 at 7:24 pm I haven't benchmarked it. What is certain is that we have far fewer instructions with it. Reply 2. [2aacaf] Fazal Majid says: June 30, 2023 at 1:17 am And ARM does it in a single rbit instruction... Who is the RISC again? Reply 1. [e03257] -.- says: June 30, 2023 at 2:05 am rbit only reverses bits. It doesn't do an arbitrary bit shuffle. AArch64's NEON would actually do a decent job (better than SSE4), but the instruction sequence would be much longer than what is achievable with AVX-512. Having said that, an AVX2/NEON implementation would be interesting. Should be possible to rshift the indexes by 3, shuffle bytes into the right location, then use a TEST to amplify the relevant bits, then extract them. Reply 3. [6504fa] camel-cdr says: June 30, 2023 at 9:32 am I had a go at a rvv implementation, I'm not able to test it rn, but I think it's roughly correct. Probably not optimal though: vsetivli x0, 1, e64, m1, ma, ta vle8.v v0, (a0) # load uint64_t vsetivli x0, 64, e16, m8, ma, ta vle8.v v8, (a1) # load uint16_t[64] vsetivli x0, 64, e8, m4, ma, ta vmv.v.i v4, 1 vmv.v.i v4, 0, v0 # mask to 0/1 bytes vrgathere16.vv v4, v4, v8 # gather does the shuffle vmseq.vi v0, v4, 0 # 0/1 bytes to mask vsetivli x0, 1, e64, m1, ma, ta vse8.v v0, (a1) # store mask Reply 1. [6504fa] camel-cdr says: June 30, 2023 at 9:35 am I forgot to mention that the above should work for any implementation with a vlen>=128. Reply 1. [6504fa] camel-cdr says: June 30, 2023 at 4:05 pm Edit: It should've been vmerge.vim instead of the second vmv.v.i, because that one isn't maskable. Reply 4. [6f6634] MajorTom says: June 30, 2023 at 2:09 pm I don't know when, or why, but you just saved me hours upon hours of research in the future. Thanks in advance! Reply Leave a Reply Cancel reply Your email address will not be published. To create code blocks or other preformatted text, indent by four spaces: This will be displayed in a monospaced font. The first four spaces will be stripped off, but all other whitespace will be preserved. Markdown is turned off in code blocks: [This is not a link](http://example.com) To create not a block, but an inline code span, use backticks: Here is some inline `code`. For more help see http://daringfireball.net/projects/markdown/syntax [ ] [ ] [ ] [ ] [ ] [ ] [ ] Comment * [ ] Name * [ ] Email * [ ] Website [ ] [ ] Save my name, email, and website in this browser for the next time I comment. Receive Email Notifications? [no, do not subscribe ] [instantly ] Or, you can subscribe without commenting. [Post Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] You may subscribe to this blog by email. Post navigation Previous Previous post: Science and Technology links (June 25 2023) Terms of use Proudly powered by WordPress