Mill Computing, Inc. › Forums › The Mill › Architecture › pdep and pext
- AuthorPosts
- #3844 |
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.pdfThere are a number of uses for such instructions. Perhaps one of the biggest uses that I am aware of is in implementing the
selectfunction ofrank/selectdata 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 implementselectusingpdep.Some praise of pdep/pext:
https://news.ycombinator.com/item?id=20205743
https://news.ycombinator.com/item?id=19137798 Looks like this got restored at some point after I tried again with:
Anyway, building off the example given here, is there an efficient way to implement the
selectfunction on the Mill, which gets the index of the k’th set bit?Find first one is in the ISA, which suffices for scalars. Bit arrays require code to iterate over the underlying array looking for a non-zero element, then FFO to locate the bit.
- AuthorPosts
You must be logged in to reply to this topic.