Re: RFR: 8283892: Compress and expand bits [v4]
On Thu, 7 Apr 2022 18:29:22 GMT, Paul Sandoz 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
Re: RFR: 8283892: Compress and expand bits [v4]
On Thu, 7 Apr 2022 20:02:51 GMT, Alan Bateman wrote: >> Examples added in latest commit. > > I see you've added a comment on each example too, I think this really helpers > readers to see how they can be used. > > The class description of both Integer and Long have an implementation note > (they pre-date @implNote) referencing Hacker's Delight. We could potentially > expand the list of methods mentioned but it's not strictly necessary are they > are just examples. I also saw that on the class doc and considered the new methods fit neatly under the category of "bit twiddling" methods. - PR: https://git.openjdk.java.net/jdk/pull/8115
Re: RFR: 8283892: Compress and expand bits [v4]
On Thu, 7 Apr 2022 18:23:50 GMT, Paul Sandoz wrote: >> src/java.base/share/classes/java/lang/Integer.java line 1781: >> >>> 1779: * All the upper remaining bits of the compressed value are set >>> 1780: * to zero. >>> 1781: * >> >> Following Alan's comment, I suggest the following examples: >> >> >> compress(0x9ABCDEF, 0x0F0F0FF) == 0xACEF >> compress(x, 1<>n & 1) >> compress(x, -1<>> n >> compress(m, m) == (m==-1||m==0)? m : (1<> compress(x, m) == compress(x & m, m) >> compress(expand(x, m), m) == x & compress(m, m) >> (compress(x, m) >>> n) & 1 == /*the bit of x corresponding to the nth set >> bit in m*/ >> >> >> …In two places. Similarly, examples for expand: >> >> >> expand(0x9ABCDEF, 0x0F0F0FF) == 0xC0D0EF >> expand(x, 1<> expand(x, -1<> expand(-1, m) == m >> expand(x, m) == expand(x, m) & m >> expand(compress(x, m), m) == x & m >> expand(1<> highest/lowestOneBit*/ >> >> >> (Please double check these examples!) > > Examples added in latest commit. I see you've added a comment on each example too, I think this really helpers readers to see how they can be used. The class description of both Integer and Long have an implementation note (they pre-date @implNote) referencing Hacker's Delight. We could potentially expand the list of methods mentioned but it's not strictly necessary are they are just examples. - PR: https://git.openjdk.java.net/jdk/pull/8115
Re: RFR: 8283892: Compress and expand bits [v4]
On Wed, 6 Apr 2022 18:22:45 GMT, John R Rose wrote: >> Paul Sandoz has updated the pull request incrementally with two additional >> commits since the last revision: >> >> - Fix typo. >> - Provide examples. > > src/java.base/share/classes/java/lang/Integer.java line 1781: > >> 1779: * All the upper remaining bits of the compressed value are set >> 1780: * to zero. >> 1781: * > > Following Alan's comment, I suggest the following examples: > > > compress(0x9ABCDEF, 0x0F0F0FF) == 0xACEF > compress(x, 1<>n & 1) > compress(x, -1<>> n > compress(m, m) == (m==-1||m==0)? m : (1< compress(x, m) == compress(x & m, m) > compress(expand(x, m), m) == x & compress(m, m) > (compress(x, m) >>> n) & 1 == /*the bit of x corresponding to the nth set > bit in m*/ > > > …In two places. Similarly, examples for expand: > > > expand(0x9ABCDEF, 0x0F0F0FF) == 0xC0D0EF > expand(x, 1< expand(x, -1< expand(-1, m) == m > expand(x, m) == expand(x, m) & m > expand(compress(x, m), m) == x & m > expand(1< highest/lowestOneBit*/ > > > (Please double check these examples!) Examples added in latest commit. - PR: https://git.openjdk.java.net/jdk/pull/8115
Re: RFR: 8283892: Compress and expand bits [v4]
> 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. - Changes: - all: https://git.openjdk.java.net/jdk/pull/8115/files - new: https://git.openjdk.java.net/jdk/pull/8115/files/da49874b..96d90e1a Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=8115&range=03 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=8115&range=02-03 Stats: 186 lines in 2 files changed: 186 ins; 0 del; 0 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
