> 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: Updates to examples ------------- Changes: - all: https://git.openjdk.java.net/jdk/pull/8115/files - new: https://git.openjdk.java.net/jdk/pull/8115/files/96d90e1a..ee062537 Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=8115&range=04 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=8115&range=03-04 Stats: 40 lines in 2 files changed: 10 ins; 2 del; 28 mod Patch: https://git.openjdk.java.net/jdk/pull/8115.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/8115/head:pull/8115 PR: https://git.openjdk.java.net/jdk/pull/8115
