This is an automated email from the ASF dual-hosted git repository.
pkarwasz pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git
The following commit(s) were added to refs/heads/master by this push:
new 845c0e540 [collections-722] deeply nested chainedIterator performance
problems fixed (#628)
845c0e540 is described below
commit 845c0e5400c5a804c972bdd9d60e6852f0c268f9
Author: Joerg Budischewski <[email protected]>
AuthorDate: Tue Aug 19 15:07:35 2025 +0200
[collections-722] deeply nested chainedIterator performance problems fixed
(#628)
* [collections-722] basically 'renovated' stale PR
commons-collections/pull/308 from collections-770, ensures that rechaining
chainedIterators multiple times now result in a single IteratorChain instance
with all picked up underlying iterators, thus avoiding deeply nested
imperformant IteratorChain instances. Additionally the UnmodifiableIterator
gets a special treatment, so that SetUtils.SetView.iterator() also benefits
from this solution. Raised test coverage.
* [collections-722] added 722 to changes.xml
---
src/changes/changes.xml | 1 +
.../collections4/iterators/IteratorChain.java | 24 ++++++-
.../iterators/UnmodifiableIterator.java | 1 -
.../collections4/iterators/IteratorChainTest.java | 81 ++++++++++++++++++++++
4 files changed, 105 insertions(+), 2 deletions(-)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 70ef6bb2e..42830e30a 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -33,6 +33,7 @@
<action type="fix" dev="ggregory" due-to="Gary Gregory">Fix exception
message in
org.apache.commons.collections4.functors.FunctorUtils.validate(Consumer...)</action>
<action type="fix" dev="ggregory" due-to="Gary Gregory">Fix exception
message in
org.apache.commons.collections4.iterators.UnmodifiableIterator.remove() to
match java.util.Iterator.remove().</action>
<action type="fix" dev="pkarwasz" due-to="Piotr P. Karwasz, Joerg
Budischewski" issue="COLLECTIONS-838">Calling SetUtils.union on multiple
instances of SetView causes JVM to hang</action>
+ <action type="fix" dev="pkarwasz" due-to="Piotr P. Karwasz, Joerg
Budischewski" issue="COLLECTIONS-722">Improve IteratorUtils.chainedIterator()
performance.</action>
<!-- ADD -->
<action type="add" dev="ggregory" due-to="Gary Gregory">Add generics to
UnmodifiableIterator for the wrapped type.</action>
<!-- UPDATE -->
diff --git
a/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
b/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
index 97373b13c..433f60d46 100644
--- a/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
+++ b/src/main/java/org/apache/commons/collections4/iterators/IteratorChain.java
@@ -168,7 +168,29 @@ public class IteratorChain<E> implements Iterator<E> {
*/
public void addIterator(final Iterator<? extends E> iterator) {
checkLocked();
- iteratorQueue.add(Objects.requireNonNull(iterator, "iterator"));
+ Objects.requireNonNull(iterator, "iterator");
+ if (iterator instanceof UnmodifiableIterator) {
+ final Iterator<? extends E> underlyingIterator =
((UnmodifiableIterator) iterator).unwrap();
+ if (underlyingIterator instanceof IteratorChain) {
+ // in case it is an IteratorChain, wrap every underlying
iterators as unmodifiable
+ // multiple rechainings would otherwise lead to exponential
growing number of function calls
+ // when the iteratorChain gets used.
+ for (Iterator<? extends E> nestedIterator : ((IteratorChain<?
extends E>) underlyingIterator).iteratorQueue) {
+
iteratorQueue.add(UnmodifiableIterator.unmodifiableIterator(nestedIterator));
+ }
+ } else {
+ // we don't know anything about the underlying iterator,
simply add it here
+ iteratorQueue.add(iterator);
+ }
+ } else if (iterator instanceof IteratorChain) {
+ // add the wrapped iterators directly instead of reusing the given
instance
+ // multiple rechainings would otherwise lead to exponential
growing number of function calls
+ // when the iteratorChain gets used.
+ iteratorQueue.addAll(((IteratorChain) iterator).iteratorQueue);
+ } else {
+ // arbitrary other iterator
+ iteratorQueue.add(iterator);
+ }
}
/**
diff --git
a/src/main/java/org/apache/commons/collections4/iterators/UnmodifiableIterator.java
b/src/main/java/org/apache/commons/collections4/iterators/UnmodifiableIterator.java
index 42b11b41a..1fb56b5cc 100644
---
a/src/main/java/org/apache/commons/collections4/iterators/UnmodifiableIterator.java
+++
b/src/main/java/org/apache/commons/collections4/iterators/UnmodifiableIterator.java
@@ -91,5 +91,4 @@ public final class UnmodifiableIterator<E, T extends
Iterator<? extends E>> impl
T unwrap() {
return iterator;
}
-
}
diff --git
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
index be17dac08..8d642e774 100644
---
a/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
+++
b/src/test/java/org/apache/commons/collections4/iterators/IteratorChainTest.java
@@ -25,9 +25,13 @@ import static org.junit.jupiter.api.Assertions.assertTrue;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
import java.util.NoSuchElementException;
+import java.util.Set;
import org.apache.commons.collections4.IteratorUtils;
import org.apache.commons.collections4.Predicate;
@@ -42,10 +46,14 @@ public class IteratorChainTest extends
AbstractIteratorTest<String> {
protected String[] testArray = {
"One", "Two", "Three", "Four", "Five", "Six"
};
+ protected String[] testArray1234 = {
+ "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight"
+ };
protected List<String> list1;
protected List<String> list2;
protected List<String> list3;
+ protected List<String> list4;
public List<String> getList1() {
return list1;
@@ -89,6 +97,9 @@ public class IteratorChainTest extends
AbstractIteratorTest<String> {
list3 = new ArrayList<>();
list3.add("Five");
list3.add("Six");
+ list4 = new ArrayList<>();
+ list4.add("Seven");
+ list4.add("Eight");
}
@Test
@@ -149,9 +160,14 @@ public class IteratorChainTest extends
AbstractIteratorTest<String> {
expected.addAll(list2);
expected.addAll(list3);
final IteratorChain<String> iter = new IteratorChain<>(list);
+ assertEquals(iter.size(), list.size());
+ assertFalse(iter.isLocked());
final List<String> actual = new ArrayList<>();
iter.forEachRemaining(actual::add);
assertEquals(actual, expected);
+ assertTrue(iter.isLocked());
+ assertThrows(UnsupportedOperationException.class, () ->
iter.addIterator(list1.iterator()),
+ "adding iterators after iteratorChain has been traversed
must fail");
}
@Test
@@ -263,4 +279,69 @@ public class IteratorChainTest extends
AbstractIteratorTest<String> {
assertEquals(1, list2.size());
}
+ @Test
+ public void testChainOfChains() {
+ final Iterator<String> iteratorChain1 = new
IteratorChain<>(list1.iterator(), list2.iterator());
+ final Iterator<String> iteratorChain2 = new
IteratorChain<>(list3.iterator(), list4.iterator());
+ final Iterator<String> iteratorChainOfChains = new
IteratorChain<>(iteratorChain1, iteratorChain2);
+
+ for (final String testValue : testArray1234) {
+ final String iterValue = (String) iteratorChainOfChains.next();
+ assertEquals(testValue, iterValue, "Iteration value is correct");
+ }
+
+ assertFalse(iteratorChainOfChains.hasNext(), "Iterator should now be
empty");
+ assertThrows(NoSuchElementException.class,
iteratorChainOfChains::next, "NoSuchElementException must be thrown");
+ }
+
+ @Test
+ public void testChainOfUnmodifiableChains() {
+ final Iterator<String> iteratorChain1 = new
IteratorChain<>(list1.iterator(), list2.iterator());
+ final Iterator<String> unmodifiableChain1 =
IteratorUtils.unmodifiableIterator(iteratorChain1);
+ final Iterator<String> iteratorChain2 = new
IteratorChain<>(list3.iterator(), list4.iterator());
+ final Iterator<String> unmodifiableChain2 =
IteratorUtils.unmodifiableIterator(iteratorChain2);
+ final Iterator<String> iteratorChainOfChains = new
IteratorChain<>(unmodifiableChain1, unmodifiableChain2);
+
+ for (final String testValue : testArray1234) {
+ final String iterValue = (String) iteratorChainOfChains.next();
+ assertEquals(testValue, iterValue, "Iteration value is correct");
+ }
+
+ assertFalse(iteratorChainOfChains.hasNext(), "Iterator should now be
empty");
+ assertThrows(NoSuchElementException.class,
iteratorChainOfChains::next, "NoSuchElementException must be thrown");
+ }
+
+ @Test
+ public void
testChainOfUnmodifiableChainsRetainsUnmodifiableBehaviourOfNestedIterator() {
+ final Iterator<String> iteratorChain1 = new
IteratorChain<>(list1.iterator(), list2.iterator());
+ final Iterator<String> unmodifiableChain1 =
IteratorUtils.unmodifiableIterator(iteratorChain1);
+ final Iterator<String> iteratorChain2 = new
IteratorChain<>(list3.iterator(), list4.iterator());
+ final Iterator<String> unmodifiableChain2 =
IteratorUtils.unmodifiableIterator(iteratorChain2);
+ final Iterator<String> iteratorChainOfChains = new
IteratorChain<>(unmodifiableChain1, unmodifiableChain2);
+
+ iteratorChainOfChains.next();
+ assertThrows(UnsupportedOperationException.class,
iteratorChainOfChains::remove,
+ "Calling remove must fail when nested iterator is
unmodifiable");
+ }
+
+ @Test
+ public void testMultipleChainedIteratorPerformWellCollections722() {
+ final Map<Integer, List<Integer>> source = new HashMap<>();
+ for (int i = 0; i < 50; i++) {
+ source.put(i, Arrays.asList(1, 2, 3));
+ }
+
+ Iterator<Integer> iterator = IteratorUtils.emptyIterator();
+ final Set<Entry<Integer, List<Integer>>> entries = source.entrySet();
+ for (final Entry<Integer, List<Integer>> entry : entries) {
+ final Iterator<Integer> next = entry.getValue().iterator();
+ iterator = IteratorUtils.chainedIterator(iterator, next);
+ }
+ final Iterator<Integer> lastIterator = iterator;
+ assertTimeoutPreemptively(Duration.ofSeconds(2), () -> {
+ while (lastIterator.hasNext()) {
+ lastIterator.next().toString();
+ }
+ });
+ }
}
