On Thu, 7 Apr 2022 18:29:22 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 two additional > commits since the last revision: > > - Fix typo. > - Provide examples. Marked as reviewed by alanb (Reviewer). ------------- PR: https://git.openjdk.java.net/jdk/pull/8115
