-
Bug
-
Resolution: Unresolved
-
P4
-
8, 9
FULL PRODUCT VERSION :
Java version "1.8.0_71"
ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 10.0.10586]
A DESCRIPTION OF THE PROBLEM :
Originally reported here: http://stackoverflow.com/q/35683724
The TreeSet(Collection) constructor caches the size of the collection and then iterates over the collection size times, which assumes the collection is not modified during construction. In particular, it will reliably fail to copy a concurrently-modified ConcurrentSkipListSet.
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Construct a ConcurrentSkipListSet, and start adding and removing elements in a thread. In a separate thread, repeatedly attempt to construct a TreeSet with the elements of the CSLS. After only a few dozen attempts this will fail.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
A TreeSet is constructed in O(n) time with a set of elements that, at one time, were in the ConcurrentSkipListSet.
ACTUAL -
A NoSuchElementException when the CSLS's iterator is over-drained.
ERROR MESSAGES/STACK TRACES THAT OCCUR :
java.util.NoSuchElementException
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299)
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504)
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462)
at java.util.TreeSet.addAll(TreeSet.java:308)
at java.util.TreeSet.<init>(TreeSet.java:172)
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27)
Dummy output: 44910
REPRODUCIBILITY :
This bug can be reproduced always.
---------- BEGIN SOURCE ----------
import java.util.Random;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;
public class ConcurrencyProblem {
private static volatile boolean modifierIsAlive = true;
public static void main(String[] args) {
final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
Thread modifier = new Thread() {
private final Random randomGenerator = new Random();
public void run() {
while (modifierIsAlive) {
concurrentSet.add(randomGenerator.nextInt(1000));
concurrentSet.remove(randomGenerator.nextInt(1000));
}
};
};
modifier.start();
int sum = 0;
while (modifierIsAlive) {
try {
TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet);
// make sure the copy operation is not eliminated by the compiler
sum += sortedCopy.size();
} catch (RuntimeException rte) {
modifierIsAlive = false;
rte.printStackTrace();
}
}
System.out.println("Dummy output: " + sum);
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Copy the CSLS into a fake SortedSet implementation that only implements size(), iterator(), and comparator(). Hacky, but resolves the issue.
Java version "1.8.0_71"
ADDITIONAL OS VERSION INFORMATION :
Microsoft Windows [Version 10.0.10586]
A DESCRIPTION OF THE PROBLEM :
Originally reported here: http://stackoverflow.com/q/35683724
The TreeSet(Collection) constructor caches the size of the collection and then iterates over the collection size times, which assumes the collection is not modified during construction. In particular, it will reliably fail to copy a concurrently-modified ConcurrentSkipListSet.
STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Construct a ConcurrentSkipListSet, and start adding and removing elements in a thread. In a separate thread, repeatedly attempt to construct a TreeSet with the elements of the CSLS. After only a few dozen attempts this will fail.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
A TreeSet is constructed in O(n) time with a set of elements that, at one time, were in the ConcurrentSkipListSet.
ACTUAL -
A NoSuchElementException when the CSLS's iterator is over-drained.
ERROR MESSAGES/STACK TRACES THAT OCCUR :
java.util.NoSuchElementException
at java.util.concurrent.ConcurrentSkipListMap$Iter.advance(ConcurrentSkipListMap.java:2299)
at java.util.concurrent.ConcurrentSkipListMap$KeyIterator.next(ConcurrentSkipListMap.java:2334)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2559)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2547)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2579)
at java.util.TreeMap.buildFromSorted(TreeMap.java:2504)
at java.util.TreeMap.addAllForTreeSet(TreeMap.java:2462)
at java.util.TreeSet.addAll(TreeSet.java:308)
at java.util.TreeSet.<init>(TreeSet.java:172)
at mtbug.ConcurrencyProblem.main(ConcurrencyProblem.java:27)
Dummy output: 44910
REPRODUCIBILITY :
This bug can be reproduced always.
---------- BEGIN SOURCE ----------
import java.util.Random;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;
public class ConcurrencyProblem {
private static volatile boolean modifierIsAlive = true;
public static void main(String[] args) {
final ConcurrentSkipListSet<Integer> concurrentSet = new ConcurrentSkipListSet<>();
Thread modifier = new Thread() {
private final Random randomGenerator = new Random();
public void run() {
while (modifierIsAlive) {
concurrentSet.add(randomGenerator.nextInt(1000));
concurrentSet.remove(randomGenerator.nextInt(1000));
}
};
};
modifier.start();
int sum = 0;
while (modifierIsAlive) {
try {
TreeSet<Integer> sortedCopy = new TreeSet<>(concurrentSet);
// make sure the copy operation is not eliminated by the compiler
sum += sortedCopy.size();
} catch (RuntimeException rte) {
modifierIsAlive = false;
rte.printStackTrace();
}
}
System.out.println("Dummy output: " + sum);
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Copy the CSLS into a fake SortedSet implementation that only implements size(), iterator(), and comparator(). Hacky, but resolves the issue.