[concurrency-interest] CHM trySplit of a map with odd size

Ben Manes ben_manes at yahoo.com
Mon Feb 22 04:33:20 EST 2016

I checked Doug's CVS repository and I didn't see a fix for this off-by-one issue.
When writing parameterized tests for a custom Spliterator view, the tests failed for maps of size 1. ConcurrentHashMap trySplit will return a new Spliterator with an estimated size of zero and set the source spliterator to zero as well. The contract states that trySplit should return null in that case and leave the source spliterator unchanged. When the map is an odd size larger than 1, the two spliterators have an even estimated count. For size 3 this means that the estimate is 2. This resulted in tests with a population size of 25 to fail. These issues occur for keySet, values, and entrySet views.
To verify my expectations, I then tested with ConcurrentSkipListMap. A split always returns null and the resulting source spliterator has an estimated count of Integer.MAX_VALUE. This happens for any non-empty map. Perhaps this should have been Long.MAX_VALUE as according to the JavaDoc that indicates an infinite, unknown, or too computationally expensive size.
The JavaDoc says the estimate may be arbitrarily inaccurate. It would be nice if either the implementations were more accurate or included a comment hinting to their behavior.
@Testpublic void keySpliterator_trySplit() {  Map<Integer, Integer> map = new ConcurrentHashMap<>();  map.put(1, 1);
  Spliterator<Integer> spliterator = map.keySet().spliterator();  Spliterator<Integer> other = spliterator.trySplit();  // 1. Split should return null, but is present  // assertThat(other, is(nullValue()));
  // 2. Size should be 1, but is 0  // int size = (int) (spliterator.estimateSize() + other.estimateSize());  // assertThat(size, is(map.size()));}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160222/06a1aeb2/attachment.html>

More information about the Concurrency-interest mailing list