Performance of default Spliterators

[Paul Sandoz]

Grrr... attachments are silently stripped.

Paul.


# HG changeset patch
# Parent 0a76b1e789a9725ecb89c7ab3566150f5f12359c
diff -r 0a76b1e789a9 -r 0ef8e2fc2de3 src/share/classes/java/util/AbstractList.java
--- a/src/share/classes/java/util/AbstractList.java	Fri May 10 00:36:02 2013 -0700
+++ b/src/share/classes/java/util/AbstractList.java	Fri May 10 10:55:38 2013 +0200
@@ -25,6 +25,8 @@
 
 package java.util;
 
+import java.util.function.Consumer;
+
 /**
  * This class provides a skeletal implementation of the {@link List}
  * interface to minimize the effort required to implement this interface
@@ -608,6 +610,72 @@
     private String outOfBoundsMsg(int index) {
         return "Index: "+index+", Size: "+size();
     }
+
+    /** Index-based split-by-two, lazily initialized Spliterator */
+    static class RandomAccessListSpliterator<E> implements Spliterator<E> {
+        private final List<E> list;
+        private int index; // current index, modified on advance/split
+        private int fence; // -1 until used; then one past last index
+
+        RandomAccessListSpliterator(List<E> list) {
+            this(list, 0, -1);
+            assert list instanceof RandomAccess;
+        }
+
+        /** Create new spliterator covering the given  range */
+        private RandomAccessListSpliterator(List<E> list, int origin, int fence) {
+            this.list = list;
+            this.index = origin;
+            this.fence = fence;
+        }
+
+        private int getFence() { // initialize fence to size on first use
+            int hi;
+            if ((hi = fence) < 0) {
+                hi = fence = list.size();
+            }
+            return hi;
+        }
+
+        public Spliterator<E> trySplit() {
+            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+            return (lo >= mid) ? null : // divide range in half unless too small
+                   new RandomAccessListSpliterator<>(list, lo, index = mid);
+        }
+
+        public boolean tryAdvance(Consumer<? super E> action) {
+            if (action == null)
+                throw new NullPointerException();
+            int hi = getFence(), i = index;
+            if (i < hi) {
+                index = i + 1;
+                action.accept(list.get(i));
+                return true;
+            }
+            return false;
+        }
+
+        public void forEachRemaining(Consumer<? super E> action) {
+            if (action == null)
+                throw new NullPointerException();
+            int hi = getFence(), i = index;
+            List<E> lst = list;
+            if (i < hi) {
+                index = hi;
+                for (; i < hi; ++i) {
+                    action.accept(lst.get(i));
+                }
+            }
+        }
+
+        public long estimateSize() {
+            return (long) (getFence() - index);
+        }
+
+        public int characteristics() {
+            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+        }
+    }
 }
 
 class SubList<E> extends AbstractList<E> {
diff -r 0a76b1e789a9 -r 0ef8e2fc2de3 src/share/classes/java/util/List.java
--- a/src/share/classes/java/util/List.java	Fri May 10 00:36:02 2013 -0700
+++ b/src/share/classes/java/util/List.java	Fri May 10 10:55:38 2013 +0200
@@ -680,7 +680,11 @@
      */
     @Override
     default Spliterator<E> spliterator() {
-        return Spliterators.spliterator(this, Spliterator.ORDERED);
+        if (this instanceof RandomAccess) {
+            return new AbstractList.RandomAccessListSpliterator<>(this);
+        } else {
+            return Spliterators.spliterator(this, Spliterator.ORDERED);
+        }
     }
 }
 
diff -r 0a76b1e789a9 -r 0ef8e2fc2de3 test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java
--- a/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java	Fri May 10 00:36:02 2013 -0700
+++ b/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java	Fri May 10 10:55:38 2013 +0200
@@ -50,6 +50,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.PriorityQueue;
+import java.util.RandomAccess;
 import java.util.Set;
 import java.util.SortedSet;
 import java.util.Spliterator;
@@ -322,6 +323,25 @@
             db.add("Arrays.asList().spliterator()",
                    () -> Spliterators.spliterator(Arrays.asList(exp.toArray(new Integer[0])), 0));
 
+            class RandomAccessList extends AbstractList<Integer> implements RandomAccess {
+                List<Integer> list;
+
+                RandomAccessList(Collection<Integer> list) {
+                    this.list = new ArrayList<>(list);
+                }
+
+                @Override
+                public Integer get(int index) {
+                    return list.get(index);
+                }
+
+                @Override
+                public int size() {
+                    return list.size();
+                }
+            }
+            db.addList(RandomAccessList::new);
+
             db.addList(ArrayList::new);
 
             db.addList(LinkedList::new);


On May 10, 2013, at 11:02 AM, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:

> Hi Donald,
> 
> I dunno if you work from the lambda source; attached is a patch implementing the random access list spliterator. If you don't work from source, you could copy the spliterator and explicitly hook it up using the constructors in StreamSupport to see if the performance improves.
> 
> Also, what terminal operation are you using for the JDK test code? collect(toList()) ?
> 
> Paul.