JDK-8013334 : Spliterator behavior for LinkedList contradicts the spec of Spliterator.trySplit() method
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.util
  • Affected Version: 8
  • Priority: P2
  • Status: Closed
  • Resolution: Fixed
  • Submitted: 2013-04-26
  • Updated: 2017-05-17
  • Resolved: 2013-05-19
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 8
8 b93Fixed
Related Reports
Relates :  
Description
(issue is reproducible with JDK8b87)

Consider the following code sample:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Spliterator;

public class SplittingLinkedList {

    public static void main(String[] args) {

        final Spliterator spliterator = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5)).spliterator();
        System.out.println("initial spliterator size = " + spliterator.estimateSize());
        final Spliterator nextSpliterator = spliterator.trySplit();
        System.out.println("next splitertor size = " + nextSpliterator.estimateSize());
        System.out.println("initial spliterator size = " + spliterator.estimateSize());

    }
}

From the output it could be seen that the first attempt to split consumes all the initial spliterator:


initial spliterator size = 5
next splitertor size = 5
initial spliterator size = 0


This behavior contradicts the spec for Spliterator.trySplit():
http://download.java.net/jdk8/docs/api/java/util/Spliterator.html#trySplit()

"... the value reported for estimateSize() before splitting, if not already zero or Long.MAX_VALUE, must, after splitting, be greater than estimateSize() for this and the returned Spliterator ... "

Either the specification or behavior of the implementation should be corrected.

The following JCK (not yet integrated) tests fail due to this issue:

api/java_util/concurrent/ArrayBlockingQueue/SpliteratorGeneral.html#SpliteratorGeneral[estimateSize_decreasingWithTrySplitCalls] 
api/java_util/LinkedHashSet/SpliteratorGeneral.html#SpliteratorGeneral[estimateSize_decreasingWithTrySplitCalls]                 
api/java_util/LinkedList/SpliteratorGeneral.html#SpliteratorGeneral[estimateSize_decreasingWithTrySplitCalls]                    
api/java_util/Spliterators/SpliteratorFromCollection.html#SpliteratorFromCollection[estimateSize_decreasingWithTrySplitCalls]    




Comments
Spec changed, SQE has looked at the bug and decided no additional tests are needed
25-08-2013

Verified in jdk8/b101 with test SplittingLinkedList mentioned in description.
06-08-2013

Change set in lambda repo: http://hg.openjdk.java.net/lambda/lambda/jdk/rev/f91091fa0cc3
29-04-2013

LinkedList uses a spliterator from iterator technique where splitting will create a left split by copying elements from linked list into an array of increasing batch sizes. The initial batch size is 1024 and the array size will be the minimum of the parent split size and batch size. Hence for small list sizes, or small parent split sizes (i.e. this can occur for large list sizes too), the left split will contain all elements and the right split none. Any spliterator implementation using the same technique will fail. (Note in a previous implementation i don't think this used to fail since the arithmetic progression of array sizes proceeded in steps of 1 not 1024). We will need to tweak the spec to say "greater than or equal to", and perhaps with some advisory note saying preferable greater than.
26-04-2013