JENA-813 : Add javadoc to note when IteratorConcat is better. Prefer IteratroCons in Iter.append and note not good style for large numbers of iterators. Consolidate other changes.
Project: http://git-wip-us.apache.org/repos/asf/jena/repo Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/5896fa62 Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/5896fa62 Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/5896fa62 Branch: refs/heads/master Commit: 5896fa623ff6b0beeffe4c5da7a33f223c38e69c Parents: 5c280fa Author: Andy Seaborne <a...@apache.org> Authored: Tue Nov 11 12:10:59 2014 +0000 Committer: Andy Seaborne <a...@apache.org> Committed: Tue Nov 11 12:10:59 2014 +0000 ---------------------------------------------------------------------- jena-arq/ReleaseNotes.txt | 3 +- .../jena/sparql/core/DatasetGraphBaseFind.java | 2 +- .../jena/sparql/core/DatasetGraphCaching.java | 2 +- .../org/apache/jena/atlas/iterator/Iter.java | 44 ++---- .../jena/atlas/iterator/IteratorConcat.java | 13 +- .../jena/atlas/iterator/IteratorCons.java | 141 ++++++++++--------- .../java/org/apache/jena/atlas/lib/Map2.java | 2 +- .../apache/jena/atlas/iterator/TestIter.java | 24 ++-- .../jena/atlas/iterator/TestIteratorPeek.java | 2 +- 9 files changed, 108 insertions(+), 125 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/ReleaseNotes.txt ---------------------------------------------------------------------- diff --git a/jena-arq/ReleaseNotes.txt b/jena-arq/ReleaseNotes.txt index ac092c6..12b0e08 100644 --- a/jena-arq/ReleaseNotes.txt +++ b/jena-arq/ReleaseNotes.txt @@ -4,8 +4,7 @@ ChangeLog for ARQ ==== Jena 2.12.2 -+ JENA-813 : Improve performance of DatasetGraphCollection, deprecate and remove usage of Iter.append() and - IteratorCons in favour of Iter.concat() and IteratorConcat ++ JENA-813 : Improve performance of DatasetGraphCollection for large numbes of named graphs. ==== Jena 2.12.1 http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphBaseFind.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphBaseFind.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphBaseFind.java index b08fa3a..e83f0c1 100644 --- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphBaseFind.java +++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphBaseFind.java @@ -73,7 +73,7 @@ abstract public class DatasetGraphBaseFind extends DatasetGraphBase if ( iter1 == null && iter2 == null ) return Iter.nullIterator() ; // Copes with null in either position. - return Iter.concat(iter1, iter2) ; + return Iter.append(iter1, iter2) ; } protected abstract Iterator<Quad> findInDftGraph(Node s, Node p , Node o) ; http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphCaching.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphCaching.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphCaching.java index d69383e..a73591a 100644 --- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphCaching.java +++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/core/DatasetGraphCaching.java @@ -177,7 +177,7 @@ abstract public class DatasetGraphCaching extends DatasetGraphTriplesQuads for ( ; iter.hasNext() ; ) { Node gn = iter.next() ; - quads = Iter.concat(quads, findInSpecificNamedGraph(dsg, gn, s, p, o)) ; + quads = Iter.append(quads, findInSpecificNamedGraph(dsg, gn, s, p, o)) ; } return quads ; } http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/org/apache/jena/atlas/iterator/Iter.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/Iter.java b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/Iter.java index 9ae35eb..f46a631 100644 --- a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/Iter.java +++ b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/Iter.java @@ -443,18 +443,18 @@ public class Iter<T> implements Iterable<T>, Iterator<T> { return Iter.operate(stream, action) ; } - /** - * @deprecated Use {@link #concat(Iterable, Iterable)} instead which is much more performant + /** Join two iteratables + * If there, potentially, going to be many iterators, it is better to + * create an {@linkplain IteratorConcat} explicitly and add each iterator. */ - @Deprecated - public static <T> Iterator<T> append(Iterable<T> iter1, Iterable<T> iter2) { + public static <T> Iterator<T> append(Iterable<? extends T> iter1, Iterable<? extends T> iter2) { return IteratorCons.create(iterator(iter1), iterator(iter2)) ; } - /** - * @deprecated Use {@link #concat(Iterator, Iterator)} instead which is much more performant + /** Join two iterator + * If there, potentially, going to be many iterators, it is better to + * create an {@linkplain IteratorConcat} explicitly and add each iterator. */ - @Deprecated public static <T> Iterator<T> append(Iterator<? extends T> iter1, Iterator<? extends T> iter2) { return IteratorCons.create(iter1, iter2) ; } @@ -754,7 +754,7 @@ public class Iter<T> implements Iterable<T>, Iterator<T> { return iter2 ; if ( iter2 == null ) return iter1 ; - return iter1.concat(iter2) ; + return iter1.append(iter2) ; } public static <T> Iterator<T> concat(Iterator<T> iter1, Iterator<T> iter2) { @@ -762,15 +762,7 @@ public class Iter<T> implements Iterable<T>, Iterator<T> { return iter2 ; if ( iter2 == null ) return iter1 ; - return Iter.iter(iter1).concat(Iter.iter(iter2)) ; - } - - public static <T> Iterator<T> concat(Iterable<T> iter1, Iterable<T> iter2) { - if (iter1 == null) - return iter2.iterator(); - if (iter2 == null) - return iter1.iterator(); - return Iter.concat(iter1.iterator(), iter2.iterator()); + return Iter.iter(iter1).append(Iter.iter(iter2)) ; } public static <T> T first(Iterator<T> iter, Filter<T> filter) { @@ -901,17 +893,13 @@ public class Iter<T> implements Iterable<T>, Iterator<T> { apply(iterator, action) ; } - /** - * @deprecated Use {@link #concat(Iterator)} instead which is much more performant + /** Join on an iterator. + * If there are going to be many iterators, uit is better to create an {@linkplain IteratorConcat} + * and <tt>.add</tt> each iterator. The overheads are much lower. */ - @Deprecated public Iter<T> append(Iterator<T> iter) { return new Iter<>(IteratorCons.create(iterator, iter)) ; } - - public Iter<T> concat(Iterator<T> iter) { - return new Iter<>(IteratorConcat.concat(iterator, iter)); - } /** Return an Iter that yields at most the first N items */ public Iter<T> take(int N) { @@ -949,14 +937,6 @@ public class Iter<T> implements Iterable<T>, Iterator<T> { // ---- Iterator - // ---- - // Could merge in concatenated iterators - if used a lot there is reducable - // cost. - // Just putting in a slot is free (?) because objects of one or two slots - // have - // the same memory allocation. - // And .. be an iterator framework for extension - @Override public boolean hasNext() { return iterator.hasNext() ; http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorConcat.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorConcat.java b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorConcat.java index 3d5958c..65e6430 100644 --- a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorConcat.java +++ b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorConcat.java @@ -24,13 +24,13 @@ import java.util.NoSuchElementException ; import org.apache.jena.atlas.lib.DS ; -/** Iterator of Iterators */ +/** Iterator of Iterators + * IteratorConcat is better when there are lots of iterators to be joined. + * IteratorCons is slightly better for two iterators. + */ public class IteratorConcat<T> implements Iterator<T> { - // No - we don't really need IteratorCons and IteratorConcat - // Historical. - private List<Iterator<T>> iterators = DS.list(); int idx = -1 ; private Iterator<T> current = null ; @@ -38,7 +38,7 @@ public class IteratorConcat<T> implements Iterator<T> boolean finished = false ; /** - * Usually better to create an IteratorConcat explicitly and add iterator if there are going to be many. + * Usually, it is better to create an IteratorConcat explicitly and add iterator if there are going to be many. * @param iter1 * @param iter2 * @return Iterator @@ -54,6 +54,9 @@ public class IteratorConcat<T> implements Iterator<T> return c ; } + public IteratorConcat() {} + + public void add(Iterator<T> iter) { iterators.add(iter) ; } @Override http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorCons.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorCons.java b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorCons.java index e86cdee..b3a5943 100644 --- a/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorCons.java +++ b/jena-arq/src/main/java/org/apache/jena/atlas/iterator/IteratorCons.java @@ -18,104 +18,105 @@ package org.apache.jena.atlas.iterator; -import java.util.Iterator; -import java.util.NoSuchElementException; +import java.util.Iterator ; +import java.util.NoSuchElementException ; -/** - * IteratorCons : the concatenation of two iterators. - * <p> - * This has known performance issues when used with lots of iterators and so - * should be avoided in favour of {@link IteratorConcat} which is much better - * performing (see <a - * href="https://issues.apache.org/jira/browse/JENA-813">JENA-813</a> for some - * discussion) - * </p> - * - * @deprecated Use the more performant {@link IteratorConcat} instead +/** IteratorCons : the concatenation of two iterators. + * See also {@linkplain IteratorConcat}. + * If there potentially many iterators to be joined, it is better to + * create an IteratorConcat explicitly and add each iterator. + * IteratorCons is slightly better in the two iterator case. */ -@Deprecated -public class IteratorCons<T> implements Iterator<T>, Iterable<T> { +public class IteratorCons<T> implements Iterator<T>, Iterable<T> +{ // No - we don't really need IteratorCons and IteratorConcat - // Historical. + // Historical - IteratorCons came first. + // IteratorConcat is nearly as good as IteratorCons in the small when it + // it is hard to see when it woudl matter much. + + private Iterator<? extends T> iter1 ; + private Iterator<? extends T> iter2 ; + private Iterator<? extends T> removeFrom ; - private Iterator<? extends T> iter1; - private Iterator<? extends T> iter2; - private Iterator<? extends T> removeFrom; - - /** - * @deprecated Use {@link IteratorConcat#concat(Iterator, Iterator)} instead which is much more performant - */ - @Deprecated - public static <X> Iterator<X> create(Iterator<? extends X> iter1, Iterator<? extends X> iter2) { - if (iter1 == null && iter2 == null) - return Iter.nullIter(); - - // The casts are safe because an iterator can only return X, and does - // not take an X an an assignment. - if (iter1 == null) { + public static <X> Iterator<X> create(Iterator<? extends X> iter1, Iterator<? extends X> iter2) + { + if ( iter1 == null && iter2 == null ) + return Iter.nullIter() ; + + // The casts are safe because an iterator can only return X, and does not take an X an an assignment. + if ( iter1 == null ) + { @SuppressWarnings("unchecked") - Iterator<X> x = (Iterator<X>) iter2; - return x; + Iterator<X> x = (Iterator<X>)iter2 ; + return x ; } - - if (iter2 == null) { + + if ( iter2 == null ) + { @SuppressWarnings("unchecked") - Iterator<X> x = (Iterator<X>) iter1; - return x; + Iterator<X> x = (Iterator<X>)iter1 ; + return x ; } - - return new IteratorCons<>(iter1, iter2); + + return new IteratorCons<>(iter1, iter2) ; } - - private IteratorCons(Iterator<? extends T> iter1, Iterator<? extends T> iter2) { - this.iter1 = iter1; - this.iter2 = iter2; + + private IteratorCons(Iterator<? extends T> iter1, Iterator<? extends T> iter2) + { + this.iter1 = iter1 ; + this.iter2 = iter2 ; } @Override - public boolean hasNext() { - if (iter1 != null) { - if (iter1.hasNext()) - return true; + public boolean hasNext() + { + if ( iter1 != null ) + { + if ( iter1.hasNext() ) return true ; // Iter1 ends - iter1 = null; + iter1 = null ; } - - if (iter2 != null) { - if (iter2.hasNext()) - return true; + + if ( iter2 != null ) + { + if ( iter2.hasNext() ) return true ; // Iter2 ends - iter2 = null; + iter2 = null ; } - return false; + return false ; } @Override - public T next() { - if (!hasNext()) - throw new NoSuchElementException("Iterator2.next"); - if (iter1 != null) { - removeFrom = iter1; + public T next() + { + if ( ! hasNext() ) + throw new NoSuchElementException("Iterator2.next") ; + if ( iter1 != null ) + { + removeFrom = iter1 ; return iter1.next(); } - if (iter2 != null) { - removeFrom = iter2; + if ( iter2 != null ) + { + removeFrom = iter2 ; return iter2.next(); } - throw new Error("Iterator2.next"); + throw new Error("Iterator2.next") ; } @Override - public void remove() { - if (null == removeFrom) - throw new IllegalStateException("no calls to next() since last call to remove()"); - - removeFrom.remove(); - removeFrom = null; + public void remove() + { + if ( null == removeFrom ) + throw new IllegalStateException("no calls to next() since last call to remove()") ; + + removeFrom.remove() ; + removeFrom = null ; } @Override - public Iterator<T> iterator() { - return this; + public Iterator<T> iterator() + { + return this ; } } http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/main/java/org/apache/jena/atlas/lib/Map2.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/main/java/org/apache/jena/atlas/lib/Map2.java b/jena-arq/src/main/java/org/apache/jena/atlas/lib/Map2.java index 3e3a254..75697e0 100644 --- a/jena-arq/src/main/java/org/apache/jena/atlas/lib/Map2.java +++ b/jena-arq/src/main/java/org/apache/jena/atlas/lib/Map2.java @@ -81,7 +81,7 @@ public class Map2<K, V> implements Iterable<K> Iter<K> iter1 = Iter.iter(map1.keySet().iterator()) ; if ( map2 == null ) return iter1 ; - return iter1.concat(Iter.iter(map2.iterator())) ; + return iter1.append(map2.iterator()) ; } public boolean isEmpty() http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIter.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIter.java b/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIter.java index a8b9937..f611c03 100644 --- a/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIter.java +++ b/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIter.java @@ -37,29 +37,29 @@ public class TestIter List<String> data3 = Arrays.asList(null, "x", null, null, null, "y", "z", null); @Test - public void concat_1() + public void append_1() { - Iterator<String> iter = Iter.concat(data1, data0) ; + Iterator<String> iter = Iter.append(data1, data0) ; test(iter, "a") ; } @Test - public void concat_2() + public void append_2() { - Iterator<String> iter = Iter.concat(data0, data1) ; + Iterator<String> iter = Iter.append(data0, data1) ; test(iter, "a") ; } @Test - public void concat_3() + public void append_3() { - Iterator<String> iter = Iter.concat(data1, data2) ; + Iterator<String> iter = Iter.append(data1, data2) ; test(iter, "a", "x", "y", "z") ; } @Test - public void concat_4() + public void append_4() { List<String> L = new ArrayList<>(3); L.add("a"); @@ -71,7 +71,7 @@ public class TestIter R.add("f"); - Iterator<String> LR = Iter.concat(L, R) ; + Iterator<String> LR = Iter.append(L, R) ; while (LR.hasNext()) { @@ -89,7 +89,7 @@ public class TestIter } @Test - public void concat_5() + public void append_5() { List<String> L = new ArrayList<>(3); L.add("a"); @@ -101,7 +101,7 @@ public class TestIter R.add("f"); - Iterator<String> LR = Iter.concat(L, R) ; + Iterator<String> LR = Iter.append(L, R) ; while (LR.hasNext()) { @@ -119,7 +119,7 @@ public class TestIter } @Test - public void concat_6() + public void append_6() { List<String> L = new ArrayList<>(3); L.add("a"); @@ -131,7 +131,7 @@ public class TestIter R.add("f"); - Iterator<String> LR = Iter.concat(L, R) ; + Iterator<String> LR = Iter.append(L, R) ; while (LR.hasNext()) { http://git-wip-us.apache.org/repos/asf/jena/blob/5896fa62/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIteratorPeek.java ---------------------------------------------------------------------- diff --git a/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIteratorPeek.java b/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIteratorPeek.java index 59b3dee..33f0b70 100644 --- a/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIteratorPeek.java +++ b/jena-arq/src/test/java/org/apache/jena/atlas/iterator/TestIteratorPeek.java @@ -45,7 +45,7 @@ public class TestIteratorPeek extends BaseTest @Test public void iter_01() { Iter<String> iter = Iter.iter(data2) ; - iter = iter.concat(data2.iterator()) ; + iter = iter.append(data2.iterator()) ; test(iter, "x", "y", "z", "x", "y", "z") ; }