Accelerated bitfield instructions: PDEP, PEXT and BEXTR?

[juj]

Wasm currently supports some bitfield instructions. It would be very interesting to have support for a more complete set: https://en.wikipedia.org/wiki/Bit_manipulation_instruction_set

In particular, PDEP, PEXT and BEXTR instructions come up every once in a while. Have these been discussed before?

[binji]

Yes, recently 😄 (see the last paragraph of the top post) : #1388

But before that, I don't think so; this is the main list of such instructions that were discussed: https://github.com/WebAssembly/design/blob/master/FutureFeatures.md#additional-integer-operators

I think before we add them, we'd want to do some analysis to determine how they'd be implemented in various native architectures, similar to work done on SIMD instructions.

[daniel-j-h]

Hi folks! I wanted to add some use-cases to the discussion, especially on the pdep/pext instructions.

These instructions are key to innovative data structures and use cases; in my case succinct data structures but there is a great motivational issue describing varied use cases in more in detail and linking to various additional resources:

ziglang/zig#14995

In my specific case I'm working on https://tinygraph.org in my evenings using succinct data structures and I'm evaluating WebAssembly as a target. At the core of most such succinct data structures are two operations: rank ("how many bits are set") and select ("give me the position of the ith set bit"). The rank operation can be implemented with popcnt. The select operation with pdep as: select(x, r) = TZCNT(PDEP(2^r,x)). Without pdep we need to rely on slow bit hacks to implement select manually.

Below are more resources on the use case but as I said above ziglang/zig#14995 is a pretty good ticket

• https://en.wikipedia.org/wiki/Succinct_data_structure
• https://www.cambridge.org/core/books/compact-data-structures/68A5983E6F1176181291E235D0B7EB44
• https://vigna.di.unimi.it/ftp/papers/Broadword.pdf
• https://arxiv.org/abs/1706.00990
• https://arxiv.org/abs/2206.01149

[dtig]

Thanks for adding a use case! Could you elaborate on the hardware support across architectures? On Intel/AMD the baseline for these sets of instructions to be performant seems to be BMI/BMI2, for Aarch64 would there be a performant lowering without SVE2?

[daniel-j-h]

I can't say much about architectures other than x86_64 where it works well on Intel 10+ years. For AMD pre-Zen 3 (~2020 and older) CPUs implement them in microcode that seems to come with a performance penalty.

There seems to be data points out there from other folks though e.g.

• https://dougallj.github.io/asil/doc/bdep_z_zz_64.html
• https://dougallj.github.io/asil/doc/bext_z_zz_64.html
• https://gist.github.com/Validark/9455d410ccc8e4bfd1c1c5c4fa38f934
• https://stackoverflow.com/questions/77834169/what-is-a-fast-fallback-algorithm-which-emulates-pdep-and-pext-in-software

There's also a C++ proposal with a x86-64 and arm implementation

• https://eisenwave.github.io/cpp-proposals/bit-permutations.html
• https://github.com/Eisenwave/cxx26-bit-permutations

[jjl]

Hi,

I also build datastructures. In particular I have worked with the Height Optimized Trie a lot recently and it uses pext in the hot path. It also uses pdep during insertion but this is less critical. I'm attempting to make something comparable to a B+ Tree, building on the HOT and i'd love to be able to support wasm.

I can't say much about architectures other than x86_64 where it works well on Intel 10+ years.

Vector variants of PEXT/PDEP exist in ARM SVE2 as BEXT/BDEP, though they're usable for just one.

For AMD pre-Zen 3 (~2020 and older) CPUs implement them in microcode that seems to come with a performance penalty.

Yeah, they take variable time up to 290 cycles based on the mask data. They can be emulated much faster on average with zp7 on those chips. I know this because I have one.

Oh and it seems the chess algorithms community also make use of pext/pdep. In fact a whole pile of uses came up while searching for information about them, though I would say they generally lean towards data structures and binary format handling.

[daniel-j-h]

There's another PDEP/PEXT use case we just came across:

Morton codes / space filling curves: the z-order curve; example

• https://github.com/jart/morton/blob/fe5fdb10b507404233ff303b8ccbcffd3ed30d27/morton.c#L25-L43
• https://github.com/jart/morton/blob/fe5fdb10b507404233ff303b8ccbcffd3ed30d27/morton.c#L76-L78

Without PDEP/PEXT interleaving bits / uninterleaving bits needs to happen manually with multiple instructions.

Space filling curves are used in geographic applications but also everywhere you want to map from a higher dimensional space (e.g. 2d) to lower dimensional space (e.g. 1d).

@dtig what does the process look like to move this forward? Is there anything we can help with?

[jjl]

i've come up with a NEON implementation that's a straight port of the zp7 polyfill's process. it's probably a little bit slower because it'll now bottleneck on a vector->gpu register transfer that previously wasn't right in the dependency chain by chance. there may be improvements that could be made, but i'm probably not the best person to make them, since i know very little about NEON, actually. it's still constant time though and most likely beats the branchy solution if there are more than a handful of bits set. if i can find some better resources to work against, i might have a go at speeding this up maybe. i haven't actually run it on real hardware yet to test the perf...

i am looking into a RISC-V Vector implementation too. I am even less familiar with RVV, but it seems to have some useful primitives, if only i could figure out how to get what i want...

[jjl]

i worked out another trick: you can use a pdep and a pext to left pack bytes according to a mask in a GPR. it looks readily adaptable to non-byte widths too, but bytes is what i needed this time:

let byte_mask = _pdep_u64(mask, 0x0101010101010101) * 0xff;
_pext_u64(bytes, byte_mask)

mask is assumed to contain a bitmask in the low 8 bits indicating which bytes should be selected.