8072784: Better spliterator implementation for BitSet.stream() (original) (raw)
Paul Sandoz paul.sandoz at oracle.com
Tue Nov 15 16:23:19 UTC 2016
- Previous message: 8072784: Better spliterator implementation for BitSet.stream()
- Next message: 8072784: Better spliterator implementation for BitSet.stream()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On 14 Nov 2016, at 17:56, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:
Hi, Please review this patch implementing a spliterator for BitSet: http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8072784-bitset-stream-spliterator/webrev/ The spliterator is SIZED but not SUBSIZED, the bit set’s cardinality is used (same for the iterator) as the size of the root spliterator, and estimates from that are derived thereafter for splits. Splitting attempts to balance the small vs. large, dense vs. sparse cases. Most of the complexity is dealing with the edge case of there being a bit set at Integer.MAXVALUE.
I was right about that aspect, i found a bug in the lowering of the fence when splitting:
diff -r 984df674e145 src/java.base/share/classes/java/util/BitSet.java --- a/src/java.base/share/classes/java/util/BitSet.java Mon Nov 14 17:35:00 2016 -0800 +++ b/src/java.base/share/classes/java/util/BitSet.java Tue Nov 15 07:05:38 2016 -0800 @@ -1300,9 +1300,9 @@ // The index is the first bit set, thus this spliterator // covers one bit and cannot be split, or two or more // bits
hi = fence = hi < Integer.MAX_VALUE
hi = fence = (hi < Integer.MAX_VALUE || !get(Integer.MAX_VALUE)) ? previousSetBit(hi - 1) + 1
: previousSetBit(Integer.MAX_VALUE);
: Integer.MAX_VALUE; // Find the mid point int mid = (lo + hi) >>> 1;
and i modified the test cases:
diff -r d62ebbfd3e0d test/java/util/BitSet/BitSetStreamTest.java --- a/test/java/util/BitSet/BitSetStreamTest.java Tue Nov 15 07:11:07 2016 -0800 +++ b/test/java/util/BitSet/BitSetStreamTest.java Tue Nov 15 08:19:17 2016 -0800 @@ -83,6 +83,7 @@ { "index 255", IntStream.of(255) }, { "index 0 and 255", IntStream.of(0, 255) }, { "index Integer.MAX_VALUE", IntStream.of(Integer.MAX_VALUE) },
{ "index Integer.MAX_VALUE - 1", IntStream.of(Integer.MAX_VALUE - 1) }, { "index 0 and Integer.MAX_VALUE", IntStream.of(0, Integer.MAX_VALUE) }, { "every bit", IntStream.range(0, 255) }, { "step 2", IntStream.range(0, 255).map(f -> f * 2) },
diff -r d62ebbfd3e0d test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java --- a/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Tue Nov 15 07:11:07 2016 -0800 +++ b/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Tue Nov 15 08:19:17 2016 -0800 @@ -892,6 +892,9 @@ { "index 0", IntStream.of(0).toArray() }, { "index 255", IntStream.of(255).toArray() }, { "index 0 and 255", IntStream.of(0, 255).toArray() },
{ "index Integer.MAX_VALUE", IntStream.of(Integer.MAX_VALUE).toArray() },{ "index Integer.MAX_VALUE - 1", IntStream.of(Integer.MAX_VALUE - 1).toArray() },{ "index 0 and Integer.MAX_VALUE", IntStream.of(0, Integer.MAX_VALUE).toArray() }, { "every bit", IntStream.range(0, 255).toArray() }, { "step 2", IntStream.range(0, 255).map(f -> f * 2).toArray() }, { "step 3", IntStream.range(0, 255).map(f -> f * 3).toArray() },
Webrev is updated in place.
Paul.
Testing-wise i have leveraged the existing tests. It would be nice to consider placing the spliterator testing functionality into a separate library for reuse as SpliteratorTraversingAndSplittingTest is getting large. Likewise for more formally for streams, which is possible to reuse but a little clunky. I can log issues for those. Paul.
- Previous message: 8072784: Better spliterator implementation for BitSet.stream()
- Next message: 8072784: Better spliterator implementation for BitSet.stream()
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]