Hey, I was wondering if the Mill has support for the bitwise gather (
pext) or bitwise scatter (
pdep) instructions found on x86_64? These are newer "fundamental" bitwise operations that cannot be implemented very efficiently without hardware support.
Some papers on the topic:
http://palms.ee.princeton.edu/PALMSopen/hilewitz06FastBitCompression.pdf
https://www.lirmm.fr/arith18/papers/hilewitz-PerformingBitManipulations.pdf
There are a
number of uses for such instructions. Perhaps one of the biggest uses that I am aware of is in implementing the
select function of
rank/
select data structures, which are the fundamental operations of
succinct data structures and certain other bitwise structures like the
Counting Quotient Filter (used for Approximate Membership Queries).
Here is an article on how to implement
select using
pdep.
Some praise of pdep/pext:
https://news.ycombinator.com/item?id=20205743
https://news.ycombinator.com/item?id=19137798