Hi Paul,
Thank you very much for your feedback, and apologize for the delay in
response..
I have incorporated your comments in the attached patch. Please kindly take a
look and let me know if you have further feedback.
- Modified @implSpec to add a description in case the list implements
RandomAccess.
- Added modification checking in RandomAccessSpliterator, only when the list
implements AbstractList.
Sorry for the confusion about SubList. It was all about the concurrent
modification checking, so adding the change above pretty much addressed my
issue earlier.
Thanks,
Hiroshi
-----Original Message-----
From: Paul Sandoz [mailto:paul.san...@oracle.com]
Sent: Thursday, May 12, 2016 8:46 PM
To: Ito, Hiroshi [Tech]
Cc: core-libs-dev@openjdk.java.net; Chan, Sunny [Tech]; Raab, Donald [Tech]
Subject: Re: RFR: Implement RandomAccess spliterator
Hi Hiroshi,
This is a good example of what seems like a small feature and yet there are
some unexpected complexities :-)
We will need to refine the implementation specification of List.spliterator,
which currently states:
* @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.
Since the existing implementation is derived from the iterator:
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
concurrent modification checking will occur. The RandomAccessSpliterator should
also support modification checking, which i think requires it be an inner class
to check co-mod state.
I am struggling to understand the points you make about the spliterator of a
sub-list of a Vector being required to be an iterator-based implementation.
Since AbstractList.SubList can access a Vector's elements through List.get/set
why cannot RandomAccessSpliterator?
If we want to support random access spliterators on sub-lists i think we would
anyway need to override the spliterator method to check for concurrent
modification (as is the case of the iterator method).
Paul.
> On 11 May 2016, at 11:25, Ito, Hiroshi <hiroshi....@gs.com> wrote:
>
> Hi,
>
> Please kindly review the attached patch for RandomAccessSpliterator
> implementation.
>
> Currently default implementation of spliterator is an IteratorSpliterator
> which is not optimal for RandomAccess data structures (besides ArrayList and
> Vector). This patch is to provide a default RandomAccessSpliterator
> implementation for RandomAccess data structure.
>
> The figures below demonstrate the performance difference before and after the
> change. Note the significant performance improvement in test
> SelectTest.parallel_lazy_streams_gsc (parallel streams performance test for
> non-JDK Lists that implement RandomAccess but don't yet implement their own
> spliterators).
>
> Benchmark code:
> https://github.com/goldmansachs/gs-collections/blob/master/jmh-tests/src/main/java/com/gs/collections/impl/jmh/SelectTest.java
>
> With IteratorSpliterator as default:
>
> Benchmark Mode Cnt Score Error Units
> SelectTest.parallel_lazy_jdk thrpt 20 172.671 ± 14.231 ops/s
> SelectTest.parallel_lazy_streams_gsc thrpt 20 20.662 ± 0.493 ops/s
> SelectTest.serial_lazy_jdk thrpt 20 89.384 ± 4.431 ops/s
> SelectTest.serial_lazy_streams_gsc thrpt 20 80.831 ± 7.875 ops/s
>
> With RandomAccessSpliterator as default:
>
> Benchmark Mode Cnt Score Error Units
> SelectTest.parallel_lazy_jdk thrpt 20 174.190 ± 16.870 ops/s
> SelectTest.parallel_lazy_streams_gsc thrpt 20 180.740 ± 9.594 ops/s
> SelectTest.serial_lazy_jdk thrpt 20 85.719 ± 2.414 ops/s
> SelectTest.serial_lazy_streams_gsc thrpt 20 78.760 ± 1.029 ops/s
>
> Majority of the patch is contributed by Paul Sandoz and he should be credited
> in the Contributed-by field.
>
> Along with this patch submission, we have a question for SubList spliterator
> implementation that we retained old behavior for now (i.e. return
> IteratorSpliterator, refer to RandomAccessSubList#spliterator()). We have
> found that Vector's subList is wrapped by RandomAccessSubList, that is
> RandomAccess but not a Vector anymore, and it expects to use
> IteratorSpliterator. We were not sure what's the best approach to distinguish
> Vector from other RandomAccess data structure within RandomAccessSublist, so
> we kept it return IteratorSpliterator for now.
>
> One approach could be to introduce VectorSubList that returns
> IteratorSpliterator (or an implementation similar to VectorSpliterator?).
> Then we could revert the spliterator() override in RandomAccessSublist.
>
> What would be your suggestion to handle this?
>
> Depending on your suggestion, we might fix the subList spliterator in this
> patch, or submit a separate patch if the amount of the change is significant.
>
> Thanks,
> Hiroshi
> <RandomAccessSpliterator.patch.txt>
# HG changeset patch
# User Hiroshi Ito <hiroshi....@gs.com>
# Date 1464016325 -28800
# Mon May 23 23:12:05 2016 +0800
# Node ID d4b180a1e32a2f4579502e57f5f0a181d87f2af4
# Parent 8c293ee99d5ace8938d2117ce380ba9724fedb0a
Add RandomAccessSpliterator to Spliterators.
diff -r 8c293ee99d5a -r d4b180a1e32a
src/java.base/share/classes/java/util/AbstractList.java
--- a/src/java.base/share/classes/java/util/AbstractList.java Thu Apr 07
10:07:02 2016 -0700
+++ b/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,105 @@
return "Index: "+index+", Size: "+size();
}
+ /** Index-based split-by-two, lazily initialized Spliterator */
+ 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
+ private int expectedModCount; // initialized when fence set
+
+ RandomAccessSpliterator(List<E> list) {
+ this(list, 0, -1, list instanceof AbstractList ? ((AbstractList)
list).modCount : 0);
+ assert list instanceof RandomAccess;
+ }
+
+ /** Create new spliterator covering the given range */
+ RandomAccessSpliterator(List<E> list, int origin, int fence,
+ int expectedModCount) {
+ this.list = list; // OK if null unless traversed
+ this.index = origin;
+ this.fence = fence;
+ this.expectedModCount = expectedModCount;
+ }
+
+ private int getFence() { // initialize fence to size on first use
+ int hi; // (a specialized variant appears in method forEach)
+ List<E> lst;
+ if ((hi = fence) < 0) {
+ if ((lst = list) == null)
+ hi = fence = 0;
+ else {
+ if (lst instanceof AbstractList) {
+ expectedModCount = ((AbstractList) lst).modCount;
+ }
+ hi = fence = lst.size();
+ }
+ }
+ return hi;
+ }
+
+ public RandomAccessSpliterator<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.list, lo, index = mid,
+ expectedModCount);
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int hi = getFence(), i = index;
+ if (i < hi) {
+ index = i + 1;
+ @SuppressWarnings("unchecked") E e = this.list.get(i);
+ action.accept(e);
+ checkForComodification(expectedModCount);
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ int i, hi, mc = 0; // hoist accesses and checks from loop
+ List<E> lst;
+ if (action == null)
+ throw new NullPointerException();
+ if ((lst = list) != null) {
+ if ((hi = fence) < 0) {
+ if (lst instanceof AbstractList)
+ mc = ((AbstractList) lst).modCount;
+ hi = lst.size();
+ }
+ else if (lst instanceof AbstractList)
+ mc = expectedModCount;
+ if ((i = index) >= 0 && (index = hi) <= lst.size()) {
+ for (; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = lst.get(i);
+ action.accept(e);
+ checkForComodification(mc);
+ }
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ public long estimateSize() {
+ return (long) (getFence() - index);
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED |
Spliterator.SUBSIZED;
+ }
+
+ private void checkForComodification(int expectedModCount) {
+ if (list instanceof AbstractList &&
+ ((AbstractList) list).modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+ }
+
private static class SubList<E> extends AbstractList<E> {
private final AbstractList<E> root;
private final SubList<E> parent;
diff -r 8c293ee99d5a -r d4b180a1e32a
src/java.base/share/classes/java/util/List.java
--- a/src/java.base/share/classes/java/util/List.java Thu Apr 07 10:07:02
2016 -0700
+++ b/src/java.base/share/classes/java/util/List.java Mon May 23 23:12:05
2016 +0800
@@ -742,6 +742,13 @@
* from the list's {@code Iterator}. The spliterator inherits the
* <em>fail-fast</em> properties of the list's iterator.
*
+ * If the list implements {@code RandomAccess}, it creates a
+ * <em><a href="Spliterator.html#binding">late-binding</a></em>
+ * {@link AbstractList.RandomAccessSpliterator}. If the list extends
+ * {@code AbstractList}, the spliterator may support the
+ * <em>fail-fast</em> properties relying on the modCounts available
+ * in the list.
+ *
* @implNote
* The created {@code Spliterator} additionally reports
* {@link Spliterator#SUBSIZED}.
@@ -751,7 +758,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);
+ }
}
/**
diff -r 8c293ee99d5a -r d4b180a1e32a
test/java/util/Spliterator/SpliteratorLateBindingFailFastTest.java
--- a/test/java/util/Spliterator/SpliteratorLateBindingFailFastTest.java
Thu Apr 07 10:07:02 2016 -0700
+++ b/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);
diff -r 8c293ee99d5a -r d4b180a1e32a
test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java
--- a/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java
Thu Apr 07 10:07:02 2016 -0700
+++ b/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java
Mon May 23 23:12:05 2016 +0800
@@ -51,6 +51,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;
@@ -379,6 +380,24 @@
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);
db.addCollection(HashSet::new);
