On Wed, 6 Apr 2022 21:57:44 GMT, Paul Sandoz <psan...@openjdk.org> wrote:
>> Add support to compress bits and expand bits of `int` and `long` values, see >> Hacker's Delight (2nd edition), section 7.4. >> >> Compressing or expanding bits of an `int` or `long` value can be composed to >> enable general permutations, and the "sheep and goats" operation (SAG) see >> Hacker's Delight (2nd edition), section 7.7. SAG can be used to perform a >> stable binary radix sort. >> >> The compress and expand functionality maps efficiently to hardware >> instructions, such as `PEXT` and `PDEP` on x86 hardware. Thus the >> implementations can be very efficient on supporting hardware. >> Intrinsification will occur in a separate PR. >> >> This [paper](https://arxiv.org/pdf/1706.00990.pdf) investigates the >> beneficial performance impact of the `PDEP` instruction, and by extension >> the `expand` method, when applied to the implementation of a bit-vector >> select operation in succinct data structures (for example `select(r)` >> returns the position of the `r`th 1). >> >> Testing-wise the approach take is three fold: >> 1. Tests compared against simple implementations that are easy to read and >> verify against the JDK implementations (which later will also be made >> intrinsic). To compensate all tests are also run flipping the test methods >> and the methods under test. >> 2. Tests composed of compress and expand and vice versa. >> 3. Tests with known mask patterns, whose expected values are easily derived >> from the inputs. > > Paul Sandoz has updated the pull request incrementally with one additional > commit since the last revision: > > Doc and test updates. I experimented with this and drafted a few microbenchmarks along and a micro-optimization to the expand methods (see #8146). Up to you, but I think it makes sense to consider such optimizations to the plain java implementation given that 1) not all platforms have specialized instructions where an intrinsic will make sense and 2) it appears to be a boost to warmup. ------------- PR: https://git.openjdk.java.net/jdk/pull/8115
