5

I watched a youtube video on the Top 10 Craziest Assembly Language Instructions and some of these instructions have no obvious application to me. What's the point of something like PEXT, which takes only the bits from the second argument which match indices of 1s in the first argument? How would the compiler know when to use this instruction? Same/similar questions about carry-less multiplication.

Disclaimer: I know little to nothing about assembly language. Maybe I should read up on it!

I hope this question is stackoverflow-appropriate.

8
  • 4
    There are a number of different applications. A popular one is to compute bishop attacks in chess programming. I used it as a part of a perfect hash function for combinatorial search problems.
    – fuz
    Nov 14, 2021 at 19:30
  • 3
    A couple uses I've run across include How to unset N right-most set bits, and multiple parts of AVX2 what is the most efficient way to pack left based on a mask? where I used pext as a bit version of left-packing, and pdep to expand a bitmask to bytes. Google site:stackoverflow.com pext pdep for more. IDK if there are any cases where a compiler would use it for you; normally you'd use it via intrinsics, i.e. _pdep_u64 Nov 14, 2021 at 20:15
  • 3
    Carryless multiplication is equivalent to multiplication of polynomials with coefficients in the integers mod 2, see en.wikipedia.org/wiki/Carry-less_product. Also known as Galois field multiplication. It shows up in cryptography algorithms like AES and in error-correcting codes. So there are definite uses for this. Nov 14, 2021 at 23:09
  • 4
    Unfortunately(?) it's the other way around: compilers are relatively clueless when it comes to these instructions, but humans can use them in various inventive ways. BTW a neat use of PEXT is in calculating the indexes of set bits
    – harold
    Nov 15, 2021 at 19:14
  • 2
    My impression of pdep/pext is that they are sort of a "because we can" instruction. It has various special cases that could be useful (packing/unpacking values scattered across bitfields, interleaving bits for Z-ordering, etc) and so perhaps they just went ahead and implemented a generic version to allow for programmers to be creative. It's one of those things, like popcount or lzcount, that can be done many times more efficiently in hardware with a dedicated instruction than in software using existing instructions. Nov 15, 2021 at 20:53

4 Answers 4

11

You can find some applications listed in the paper regarding the hardware unit for PDEP/PEXT

There are many emerging applications, such as cryptography, imaging and biometrics, where more advanced bit manipulation operations are needed. While these can be built from the simpler logical and shift operations, the applications using these advanced bit manipulation operations are significantly sped up if the processor can support more powerful bit manipulation instructions. Such operations include arbitrary bit permutations, performing multiple bit-field extract operations in parallel, and performing multiple bit-field deposit operations in parallel. We call these permutation (perm), parallel extract (pex) or bit gather, and parallel deposit (pdep) or bit scatter operations, respectively.

Performing Advanced Bit Manipulations Efficiently in General-Purpose Processors

Bit permutation is extremely common in bitboards, for example reverse bytes/words or mirror bit arrays. There are lots of algorithms in it that require extensive bit manipulation and people had to get creative to do that before the era of PEXT/PDEP. Later many card game engines also use that technique to deal with a single game set in just one or a few registers

PDEP/PEXT is also used to greatly improve bit interleaving performance, which is common in algorithms like Morton code. Some examples on this:

The multiplication technique invented for bitboards is also commonly used in many algorithms in Bit Twiddling Hacks, for example interleave bits with 64-bit multiply. This technique is no longer needed when PDEP/PEXT is available

You can find more detailed information in Bit permutations and Hacker's Delight

Another usage for PDEP/PEXT is to extract/combine fields where the bits are not in contiguous positions, for example disassemble RISC-V instructions where immediates scatter around to make hardware design simpler but also make it a bit messier to work with on software without PDEP/PEXT

Some other applications:

I think the pext / pdep instructions have HUGE implications to 4-coloring problem, 3-SAT, Constraint Solvers, etc. etc. More researchers probably should look into those two instructions.

Just look at Binary Decision Diagrams, and other such combinatorial data structures, and you can definitely see the potential uses of PEXT / PDEP all over the place.

https://news.ycombinator.com/item?id=19137260


How would the compiler know when to use this instruction?

Compilers can recognize common patterns and optimize the instruction sequence, but for advanced things like this then programmers usually need to explicitly call intrinsics from high level code

2
  • You write that "Later many card game engines also use that technique to deal with a single game set in just one or a few registers" Do you have any reference or info where I can read more about this?
    – Petter T
    Nov 28, 2022 at 11:00
  • @PetterT I don't remember where I read that, it was long ago. However some people definitely use it, especially in games that only care about the value and not the suits More efficient way to store Playing Cards in bits?
    – phuclv
    Nov 29, 2022 at 13:42
5

PDEP (Parallel Deposit) and PEXT (Parallel Extract) are meant to be a convenient way to extract and deposit bit fields. I'd bet there are good low level use cases for them.

For actual uses - I wrote a Sudoku solver that used PEXT in couple functions to extract bit values. Thanks to PEXT I was able to extract 4 elements in a single instruction (vs 1 for normal approach). It was really convenient. If you'd really want I could put up a code snippet on Compiler Explorer to show the difference.

2

Here's a real world use case from our recent publication Transcoding Unicode Characters with AVX-512. A total of 4 pext instructions are used to convert from UTF-8 to UTF-16.

64 bytes of UTF-8 text are loaded into a vector. We classify* the bytes into ASCII bytes (00 to 7f), follow bytes (80 to bf), 2-byte lead bytes (c0 to df), 3-byte lead-bytes (e0 to ef) and 4-byte lead bytes (the others). ASCII bytes, 2-byte lead bytes, 3-byte lead bytes, and 4-byte lead bytes are lead bytes.

  1. The first pext instruction is used in the fast-path for when there are no 3-byte or 4-byte lead bytes. In such a case, we extract the lead byte mask with itself using pext to get a mask of the first n bits set where n is the number of bits in the lead byte mask. We need this mask to then store n bytes of output into memory. Using pext is faster than alternatives like popcnt followed by bzhi.

  2. In the fast path for “no 4-byte lead bytes”, after transcoding has finished, we have a mask that tells us where the last bytes of each UTF-8 sequence were. We take the mask of 3-byte lead bytes, shift it to the left by 2 (to instead indicate the final bytes of 3-byte sequences) and extract it with pext through the last byte mask, giving us a mask that for each UTF-8 sequence (corresponding to one UTF-16 word in the output) tells us if that word corresponds to a 3-byte sequence. We then use this mask to check if there were any invalid 3-byte sequences in the input (i.e. surrogates or overlong sequences).

  3. In the main code path, we use a similar approach to find out which of the generated UTF-16 words are supposed to be surrogates so we can check for correct sequencing and apply some postprocessing.

  4. Lastly, the same approach from (2) is also used in the main code path, once again to validate 3-byte sequences.

All of this would have been significantly harder without pdep and pext and it's really important to have them.


* invalid bytes c0, c1, and f8 to ff are sorted out in a later step.

0

The following isn't directly related to the usag of PDEP / PEXT since it's about the performance - but it affects if its usage makes sense. I've got a Zen2 Ryzen Threadripper 3990X CPU under Windows 11 and I tested the througput of PDEP and PEXT with the intrinsics of MSVC++ and Intel C++ under Windows and clang++ and g++ under Linux. Here's the code:

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cstdint>
#include <atomic>
#if defined(_MSC_VER)
    #include <intrin.h>
#elif defined(__GNUC__) || defined(__llvm__)
    #include <immintrin.h>
#endif

using namespace std;
using namespace chrono;

atomic_uint64_t aSum( 0 );

int main()
{
    constexpr size_t
        N = 0x1000,
        ROUNDS = 10'000;
    vector<uint64_t> data( N, 0 );
    mt19937_64 mt;
    uniform_int_distribution<uint64_t> uid( 0, -1 );
    for( uint64_t &d : data )
        d = uid( mt );
    auto pdep = []( uint64_t data, uint64_t mask ) -> uint64_t { return _pdep_u64( data, mask ); };
    auto pext = []( uint64_t data, uint64_t mask ) -> uint64_t { return _pext_u64( data, mask ); };
    auto bench = [&]<typename Permute>( Permute permute ) -> double
    {
        uint64_t sum = 0;
        auto start = high_resolution_clock::now();
        constexpr uint64_t MASK = 0x5555555555555555u;
        for( size_t r = ROUNDS; r--; )
            for( uint64_t d : data )
                sum += permute( d, MASK );
        double ns = (double)(int64_t)duration_cast<nanoseconds>( high_resolution_clock::now() - start ).count() / ((double)N * ROUNDS);
        ::aSum = sum;
        return ns;
    };
    cout << bench( pdep ) << endl;
    cout << bench( pext ) << endl;
}

According to the data on agner.org PDEP / PEXT should have a latency and througput of slightly below 20 clock cycles on my Zen2 CPU. On Intel since Haswell CPUs the latency is only 3 clock cycles and the throughput is a whopping one clock cycle.
But according to my measurements each instruction takes about 35ns, i.e. about 150 clock cycles on my CPU. There's no measurement error and the disassembly I checked matches what you'd write in assembly. So I'm curious about the data of other CPUs. Maybe you'll report it here. It would be helpful to assess if the usage of PDEP or PEXT makes sense.

10
  • I've seen it said that PEXT/PDEP microcode on AMD before Zen3 has data-dependent performance, so some inputs are faster than others. Maybe Agner only checked with one input value which happened to be simple, like all-zero? May 14, 2022 at 15:05
  • 1
    Anyway, this is clearly not an answer to this SO question, but rather a question you should post separately, with a title like "How do PEXT/PDEP perform on Zen 2 and earlier?" The question body can be mostly this, your experiment and results. Details on exactly how slow it is before Zen3 added HW support would be nice to have, it'd be a good question to have on SO. (We can edit this question and/or one of the answers to mention it being slow on many existing AMD CPUs, since that's good info for future readers to beware of. But it doesn't belong as a full answer here.) May 14, 2022 at 15:06
  • @PeterCordes: I know that my question only partitially fits here, but when I google for "PDEP PEXT Stack Overflow" this is the only article about PDEP and PEXT her. So it is not the worst idea to post it here. And you're right, Peter, the results are varying accoring to the mask. If I have a mask of 0, i..e. extracting or compressing no bits, the results are according to Agner's data. Should I inform him ? Better not, I've aleady mailed him for another reason and got an dismissive reply. May 14, 2022 at 16:18
  • 1
    This isn't an "article", it's a question, about something else. Finding a very different question involving the same function or instruction never makes it ok to post a new question as an answer on Stack Overflow. (Also, my google search for site:stackoverflow.com pext pdep found 137 hits. When I typoed PEXT as PEX, I only got 2, including this and a typoed comment on the AVX2 left-packing Q&A). I guess I can see why you thought it would make sense to post a performance note on a question about using it, so it's not as totally obvious as usual, but you wrote this like a question. May 14, 2022 at 16:39
  • 1
    I've downvoted this answer as it does not attempt to answer the question.
    – fuz
    Nov 6 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.