jdk-sandbox: comparison jdk/src/share/classes/java/util/stream/Streams.java

equal deleted inserted replaced

-:ee3bda8e26c6
+:d5a620310f97
 * questions.
 */
 package java.util.stream;
 import java.util.Comparator;
-import java.util.Iterator;
 import java.util.Objects;
 import java.util.Spliterator;
 import java.util.Spliterators;
 import java.util.function.BiFunction;
 import java.util.function.Consumer;
 /**
 * An {@code int} range spliterator.
 */
 static final class RangeIntSpliterator implements Spliterator.OfInt {
+// Can never be greater that upTo, this avoids overflow if upper bound
+// is Integer.MAX_VALUE
+// All elements are traversed if from == upTo & last == 0
 private int from;
 private final int upTo;
-private final int step;
+// 1 if the range is closed and the last element has not been traversed
+// Otherwise, 0 if the range is open, or is a closed range and all
-RangeIntSpliterator(int from, int upTo, int step) {
+// elements have been traversed
+private int last;
+RangeIntSpliterator(int from, int upTo, boolean closed) {
+this(from, upTo, closed ? 1 : 0);
+}
+private RangeIntSpliterator(int from, int upTo, int last) {
 this.from = from;
 this.upTo = upTo;
-this.step = step;
+this.last = last;
 }
 @Override
 public boolean tryAdvance(IntConsumer consumer) {
-boolean hasNext = from < upTo;
+final int i = from;
-if (hasNext) {
+if (i < upTo) {
-consumer.accept(from);
+from++;
-from += step;
+consumer.accept(i);
-}
+return true;
-return hasNext;
+}
+else if (last > 0) {
+last = 0;
+consumer.accept(i);
+return true;
+}
+return false;
 }
 @Override
 public void forEachRemaining(IntConsumer consumer) {
-int hUpTo = upTo;
+int i = from;
-int hStep = step; // hoist accesses and checks from loop
+final int hUpTo = upTo;
-for (int i = from; i < hUpTo; i += hStep)
+int hLast = last;
+from = upTo;
+last = 0;
+while (i < hUpTo) {
+consumer.accept(i++);
+}
+if (hLast > 0) {
+// Last element of closed range
 consumer.accept(i);
-from = upTo;
+}
 }
 @Override
 public long estimateSize() {
-int d = upTo - from;
+// Ensure ranges of size > Integer.MAX_VALUE report the correct size
-return (d / step) + ((d % step == 0) ? 0 : 1);
+return ((long) upTo) - from + last;
 }
 @Override
 public int characteristics() {
 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |
 return null;
 }
 @Override
 public Spliterator.OfInt trySplit() {
-return estimateSize() <= 1
+long size = estimateSize();
+return size <= 1
 ? null
-: new RangeIntSpliterator(from, from = from + midPoint(), step);
+// Left split always has a half-open range
-}
+: new RangeIntSpliterator(from, from = from + splitPoint(size), 0);
+}
-private int midPoint() {
-// Size is known to be >= 2
+/**
-int bisection = (upTo - from) / 2;
+* The spliterator size below which the spliterator will be split
-// If bisection > step then round down to nearest multiple of step
+* at the mid-point to produce balanced splits. Above this size the
-// otherwise round up to step
+* spliterator will be split at a ratio of
-return bisection > step ? bisection - bisection % step : step;
+* 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)
+* to produce right-balanced splits.
+*
+* <p>Such splitting ensures that for very large ranges that the left
+* side of the range will more likely be processed at a lower-depth
+* than a balanced tree at the expense of a higher-depth for the right
+* side of the range.
+*
+* <p>This is optimized for cases such as IntStream.ints() that is
+* implemented as range of 0 to Integer.MAX_VALUE but is likely to be
+* augmented with a limit operation that limits the number of elements
+* to a count lower than this threshold.
+*/
+private static final int BALANCED_SPLIT_THRESHOLD = 1 << 24;
+/**
+* The split ratio of the left and right split when the spliterator
+* size is above BALANCED_SPLIT_THRESHOLD.
+*/
+private static final int RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;
+private int splitPoint(long size) {
+int d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;
+// 2 <= size <= 2^32
+return (int) (size / d);
 }
 }
 /**
 * A {@code long} range spliterator.
+*
+* This implementation cannot be used for ranges whose size is greater
+* than Long.MAX_VALUE
 */
 static final class RangeLongSpliterator implements Spliterator.OfLong {
+// Can never be greater that upTo, this avoids overflow if upper bound
+// is Long.MAX_VALUE
+// All elements are traversed if from == upTo & last == 0
 private long from;
 private final long upTo;
-private final long step;
+// 1 if the range is closed and the last element has not been traversed
+// Otherwise, 0 if the range is open, or is a closed range and all
-RangeLongSpliterator(long from, long upTo, long step) {
+// elements have been traversed
+private int last;
+RangeLongSpliterator(long from, long upTo, boolean closed) {
+this(from, upTo, closed ? 1 : 0);
+}
+private RangeLongSpliterator(long from, long upTo, int last) {
+assert upTo - from + last > 0;
 this.from = from;
 this.upTo = upTo;
-this.step = step;
+this.last = last;
 }
 @Override
 public boolean tryAdvance(LongConsumer consumer) {
-boolean hasNext = from < upTo;
+final long i = from;
-if (hasNext) {
+if (i < upTo) {
-consumer.accept(from);
+from++;
-from += step;
+consumer.accept(i);
-}
+return true;
-return hasNext;
+}
+else if (last > 0) {
+last = 0;
+consumer.accept(i);
+return true;
+}
+return false;
 }
 @Override
 public void forEachRemaining(LongConsumer consumer) {
-long hUpTo = upTo;
+long i = from;
-long hStep = step; // hoist accesses and checks from loop
+final long hUpTo = upTo;
-for (long i = from; i < hUpTo; i += hStep)
+int hLast = last;
+from = upTo;
+last = 0;
+while (i < hUpTo) {
+consumer.accept(i++);
+}
+if (hLast > 0) {
+// Last element of closed range
 consumer.accept(i);
-from = upTo;
+}
 }
 @Override
 public long estimateSize() {
-long d = upTo - from;
+return upTo - from + last;
-return (d / step) + ((d % step == 0) ? 0 : 1);
 }
 @Override
 public int characteristics() {
 return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED |
 return null;
 }
 @Override
 public Spliterator.OfLong trySplit() {
-return estimateSize() <= 1
+long size = estimateSize();
+return size <= 1
 ? null
-: new RangeLongSpliterator(from, from = from + midPoint(), step);
+// Left split always has a half-open range
-}
+: new RangeLongSpliterator(from, from = from + splitPoint(size), 0);
+}
-private long midPoint() {
-// Size is known to be >= 2
+/**
-long bisection = (upTo - from) / 2;
+* The spliterator size below which the spliterator will be split
-// If bisection > step then round down to nearest multiple of step
+* at the mid-point to produce balanced splits. Above this size the
-// otherwise round up to step
+* spliterator will be split at a ratio of
-return bisection > step ? bisection - bisection % step : step;
+* 1:(RIGHT_BALANCED_SPLIT_RATIO - 1)
+* to produce right-balanced splits.
+*
+* <p>Such splitting ensures that for very large ranges that the left
+* side of the range will more likely be processed at a lower-depth
+* than a balanced tree at the expense of a higher-depth for the right
+* side of the range.
+*
+* <p>This is optimized for cases such as LongStream.longs() that is
+* implemented as range of 0 to Long.MAX_VALUE but is likely to be
+* augmented with a limit operation that limits the number of elements
+* to a count lower than this threshold.
+*/
+private static final long BALANCED_SPLIT_THRESHOLD = 1 << 24;
+/**
+* The split ratio of the left and right split when the spliterator
+* size is above BALANCED_SPLIT_THRESHOLD.
+*/
+private static final long RIGHT_BALANCED_SPLIT_RATIO = 1 << 3;
+private long splitPoint(long size) {
+long d = (size < BALANCED_SPLIT_THRESHOLD) ? 2 : RIGHT_BALANCED_SPLIT_RATIO;
+// 2 <= size <= Long.MAX_VALUE
+return size / d;
 }
 }
 private static abstract class AbstractStreamBuilderImpl<T, S extends Spliterator<T>> implements Spliterator<T> {
 // >= 0 when building, < 0 when built

changeset 18158	d5a620310f97
parent 18153	644df1dfb3be
child 18820	a87cdd6a8834