On Wed, 6 Apr 2022 14:58:37 GMT, Alan Bateman <al...@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. > > src/java.base/share/classes/java/lang/Integer.java line 1775: > >> 1773: * the specified bit mask. >> 1774: * <p> >> 1775: * For each one-bit value of the mask, {@code mb} say, from least > > A minor comments is that "For each one-bit value of the mask mb ...." might > be a bit better, otherwise I think these methods and their javadoc looks > good. If it comes up then these methods could include an example in the > javadoc as they aren't hard once you see an example. I can change to "For each one-bit value {@code mb} of the mask ..." ------------- PR: https://git.openjdk.java.net/jdk/pull/8115
