8158365: List.spliterator should optimize for RandomAccess lists
Reviewed-by: psandoz
Contributed-by: Hiroshi Ito <hiroshi.ito@gs.com>
--- a/jdk/src/java.base/share/classes/java/util/AbstractList.java Mon Jul 11 14:32:51 2016 +0100
+++ b/jdk/src/java.base/share/classes/java/util/AbstractList.java Mon May 23 23:12:05 2016 +0800
@@ -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
@@ -634,6 +636,115 @@
return "Index: "+index+", Size: "+size();
}
+ /**
+ * An index-based split-by-two, lazily initialized Spliterator covering
+ * a List that access elements via {@link List#get}.
+ *
+ * If access results in an IndexOutOfBoundsException then a
+ * ConcurrentModificationException is thrown instead (since the list has
+ * been structurally modified while traversing).
+ *
+ * If the List is an instance of AbstractList then concurrent modification
+ * checking is performed using the AbstractList's modCount field.
+ */
+ static final class RandomAccessSpliterator<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
+
+ // The following fields are valid if covering an AbstractList
+ private final AbstractList<E> alist;
+ private int expectedModCount; // initialized when fence set
+
+ RandomAccessSpliterator(List<E> list) {
+ assert list instanceof RandomAccess;
+
+ this.list = list;
+ this.index = 0;
+ this.fence = -1;
+
+ this.alist = list instanceof AbstractList ? (AbstractList<E>) list : null;
+ this.expectedModCount = alist != null ? alist.modCount : 0;
+ }
+
+ /** Create new spliterator covering the given range */
+ private RandomAccessSpliterator(RandomAccessSpliterator<E> parent,
+ int origin, int fence) {
+ this.list = parent.list;
+ this.index = origin;
+ this.fence = fence;
+
+ this.alist = parent.alist;
+ this.expectedModCount = parent.expectedModCount;
+ }
+
+ private int getFence() { // initialize fence to size on first use
+ int hi;
+ List<E> lst = list;
+ if ((hi = fence) < 0) {
+ if (alist != null) {
+ expectedModCount = alist.modCount;
+ }
+ hi = fence = lst.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 RandomAccessSpliterator<>(this, 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(get(list, i));
+ checkAbstractListModCount(alist, expectedModCount);
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ List<E> lst = list;
+ int hi = getFence();
+ int i = index;
+ index = hi;
+ for (; i < hi; i++) {
+ action.accept(get(lst, i));
+ }
+ checkAbstractListModCount(alist, expectedModCount);
+ }
+
+ public long estimateSize() {
+ return (long) (getFence() - index);
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+
+ private static <E> E get(List<E> list, int i) {
+ try {
+ return list.get(i);
+ } catch (IndexOutOfBoundsException ex) {
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ static void checkAbstractListModCount(AbstractList<?> alist, int expectedModCount) {
+ if (alist != null && alist.modCount != expectedModCount) {
+ throw new ConcurrentModificationException();
+ }
+ }
+ }
+
private static class SubList<E> extends AbstractList<E> {
private final AbstractList<E> root;
private final SubList<E> parent;
--- a/jdk/src/java.base/share/classes/java/util/List.java Mon Jul 11 14:32:51 2016 +0100
+++ b/jdk/src/java.base/share/classes/java/util/List.java Mon May 23 23:12:05 2016 +0800
@@ -741,9 +741,22 @@
*
* @implSpec
* The default implementation creates a
- * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
- * from the list's {@code Iterator}. The spliterator inherits the
- * <em>fail-fast</em> properties of the list's iterator.
+ * <em><a href="Spliterator.html#binding">late-binding</a></em>
+ * spliterator as follows:
+ * <ul>
+ * <li>If the list is an instance of {@link RandomAccess} then the default
+ * implementation creates a spliterator that traverses elements by
+ * invoking the method {@link List#get}. If such invocation results or
+ * would result in an {@code IndexOutOfBoundsException} then the
+ * spliterator will <em>fail-fast</em> and throw a
+ * {@code ConcurrentModificationException}.
+ * If the list is also an instance of {@link AbstractList} then the
+ * spliterator will use the list's {@link AbstractList#modCount modCount}
+ * field to provide additional <em>fail-fast</em> behavior.
+ * <li>Otherwise, the default implementation creates a spliterator from the
+ * list's {@code Iterator}. The spliterator inherits the
+ * <em>fail-fast</em> of the list's iterator.
+ * </ul>
*
* @implNote
* The created {@code Spliterator} additionally reports
@@ -754,7 +767,11 @@
*/
@Override
default Spliterator<E> spliterator() {
- return Spliterators.spliterator(this, Spliterator.ORDERED);
+ if (this instanceof RandomAccess) {
+ return new AbstractList.RandomAccessSpliterator<>(this);
+ } else {
+ return Spliterators.spliterator(this, Spliterator.ORDERED);
+ }
}
/**
--- a/jdk/test/java/util/Spliterator/SpliteratorLateBindingFailFastTest.java Mon Jul 11 14:32:51 2016 +0100
+++ b/jdk/test/java/util/Spliterator/SpliteratorLateBindingFailFastTest.java Mon May 23 23:12:05 2016 +0800
@@ -24,11 +24,13 @@
import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;
+import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
+import java.util.Iterator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
@@ -37,6 +39,7 @@
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
+import java.util.RandomAccess;
import java.util.Set;
import java.util.Spliterator;
import java.util.Stack;
@@ -191,6 +194,46 @@
db.addList(Vector::new);
+ class AbstractRandomAccessListImpl extends AbstractList<Integer> implements RandomAccess {
+ List<Integer> l;
+
+ AbstractRandomAccessListImpl(Collection<Integer> c) {
+ this.l = new ArrayList<>(c);
+ }
+
+ @Override
+ public boolean add(Integer integer) {
+ modCount++;
+ return l.add(integer);
+ }
+
+ @Override
+ public Iterator<Integer> iterator() {
+ return l.iterator();
+ }
+
+ @Override
+ public Integer get(int index) {
+ return l.get(index);
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ modCount++;
+ return l.remove(o);
+ }
+
+ @Override
+ public int size() {
+ return l.size();
+ }
+
+ @Override
+ public List<Integer> subList(int fromIndex, int toIndex) {
+ return l.subList(fromIndex, toIndex);
+ }
+ }
+ db.addList(AbstractRandomAccessListImpl::new);
db.addCollection(HashSet::new);
--- a/jdk/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Mon Jul 11 14:32:51 2016 +0100
+++ b/jdk/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Mon May 23 23:12:05 2016 +0800
@@ -49,8 +49,10 @@
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
+import java.util.ListIterator;
import java.util.Map;
import java.util.PriorityQueue;
+import java.util.RandomAccess;
import java.util.Set;
import java.util.SortedSet;
import java.util.Spliterator;
@@ -379,6 +381,150 @@
db.addList(Vector::new);
+ class AbstractRandomAccessListImpl extends AbstractList<Integer> implements RandomAccess {
+ Integer[] ia;
+
+ AbstractRandomAccessListImpl(Collection<Integer> c) {
+ this.ia = c.toArray(new Integer[c.size()]);
+ }
+
+ @Override
+ public Integer get(int index) {
+ return ia[index];
+ }
+
+ @Override
+ public int size() {
+ return ia.length;
+ }
+ }
+ db.addList(AbstractRandomAccessListImpl::new);
+
+ class RandomAccessListImpl implements List<Integer>, RandomAccess {
+ Integer[] ia;
+ List<Integer> l;
+
+ RandomAccessListImpl(Collection<Integer> c) {
+ this.ia = c.toArray(new Integer[c.size()]);
+ this.l = Arrays.asList(ia);
+ }
+
+ @Override
+ public Integer get(int index) {
+ return ia[index];
+ }
+
+ @Override
+ public Integer set(int index, Integer element) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void add(int index, Integer element) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public Integer remove(int index) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public int indexOf(Object o) {
+ return l.indexOf(o);
+ }
+
+ @Override
+ public int lastIndexOf(Object o) {
+ return Arrays.asList(ia).lastIndexOf(o);
+ }
+
+ @Override
+ public ListIterator<Integer> listIterator() {
+ return l.listIterator();
+ }
+
+ @Override
+ public ListIterator<Integer> listIterator(int index) {
+ return l.listIterator(index);
+ }
+
+ @Override
+ public List<Integer> subList(int fromIndex, int toIndex) {
+ return l.subList(fromIndex, toIndex);
+ }
+
+ @Override
+ public int size() {
+ return ia.length;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return size() != 0;
+ }
+
+ @Override
+ public boolean contains(Object o) {
+ return l.contains(o);
+ }
+
+ @Override
+ public Iterator<Integer> iterator() {
+ return l.iterator();
+ }
+
+ @Override
+ public Object[] toArray() {
+ return l.toArray();
+ }
+
+ @Override
+ public <T> T[] toArray(T[] a) {
+ return l.toArray(a);
+ }
+
+ @Override
+ public boolean add(Integer integer) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean remove(Object o) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean containsAll(Collection<?> c) {
+ return l.containsAll(c);
+ }
+
+ @Override
+ public boolean addAll(Collection<? extends Integer> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean addAll(int index, Collection<? extends Integer> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean removeAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public boolean retainAll(Collection<?> c) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public void clear() {
+ throw new UnsupportedOperationException();
+ }
+ }
+ db.addList(RandomAccessListImpl::new);
db.addCollection(HashSet::new);