diff -r ee3bda8e26c6 -r d5a620310f97 jdk/src/share/classes/java/util/stream/Streams.java
--- a/jdk/src/share/classes/java/util/stream/Streams.java	Mon Jun 10 11:06:26 2013 -0700
+++ b/jdk/src/share/classes/java/util/stream/Streams.java	Tue Jun 11 12:13:26 2013 +0200
@@ -25,7 +25,6 @@
 package java.util.stream;
 
 import java.util.Comparator;
-import java.util.Iterator;
 import java.util.Objects;
 import java.util.Spliterator;
 import java.util.Spliterators;
@@ -62,39 +61,62 @@
      * 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
+        // elements have been traversed
+        private int last;
 
-        RangeIntSpliterator(int from, int upTo, int step) {
+        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;
-            if (hasNext) {
-                consumer.accept(from);
-                from += step;
+            final int i = from;
+            if (i < upTo) {
+                from++;
+                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 hStep = step; // hoist accesses and checks from loop
-            for (int i = from; i < hUpTo; i += hStep)
+            int i = from;
+            final int hUpTo = upTo;
+            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;
-            return (d / step) + ((d % step == 0) ? 0 : 1);
+            // Ensure ranges of size > Integer.MAX_VALUE report the correct size
+            return ((long) upTo) - from + last;
         }
 
         @Override
@@ -111,57 +133,108 @@
 
         @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;
-            // If bisection > step then round down to nearest multiple of step
-            // otherwise round up to step
-            return bisection > step ? bisection - bisection % step : step;
+        /**
+         * The spliterator size below which the spliterator will be split
+         * at the mid-point to produce balanced splits. Above this size the
+         * spliterator will be split at a ratio of
+         * 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
+        // elements have been traversed
+        private int last;
 
-        RangeLongSpliterator(long from, long upTo, long step) {
+        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;
-            if (hasNext) {
-                consumer.accept(from);
-                from += step;
+            final long i = from;
+            if (i < upTo) {
+                from++;
+                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 hStep = step; // hoist accesses and checks from loop
-            for (long i = from; i < hUpTo; i += hStep)
+            long i = from;
+            final long hUpTo = upTo;
+            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 (d / step) + ((d % step == 0) ? 0 : 1);
+            return upTo - from + last;
         }
 
         @Override
@@ -178,17 +251,42 @@
 
         @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;
-            // If bisection > step then round down to nearest multiple of step
-            // otherwise round up to step
-            return bisection > step ? bisection - bisection % step : step;
+        /**
+         * The spliterator size below which the spliterator will be split
+         * at the mid-point to produce balanced splits. Above this size the
+         * spliterator will be split at a ratio of
+         * 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;
         }
     }