Parallelism with Streams created from Iterators

Question

Experimenting with streams I ran into the following behavior which I don't quite understand. I created a parallel stream from an iterator and I noticed that it did not seem to be exhibiting parallelism. In the below example I've printed a counter to the console for two parallel streams, one created from an iterator and the other from a list. The stream created from the list exhibited the behavior I expected which was to print the counter in non-sequential order but the stream created from the iterator printed the counter in sequential order. Am I creating the parallel stream from an iterator incorrectly?

    private static int counter = 0;

public static void main(String[] args) {
    List<Integer> lstr = IntStream.rangeClosed(1, 100).boxed().collect(Collectors.toList());
    Iterator<Integer> iter = lstr.iterator();

    System.out.println("Iterator Stream: ");
    StreamSupport.stream(Spliterators.spliteratorUnknownSize(iter, Spliterator.IMMUTABLE | Spliterator.CONCURRENT), true).forEach(i -> {
        System.out.print(counter + " ");
        counter++;
    });

    counter = 0;
    System.out.println("\nList Stream: ");
    lstr.parallelStream().forEach(i -> {
        System.out.print(counter + " ");
        counter++;
    });

}

Answer 1

There is no guaranty that parallel processing prints the counter in non-sequential order. Further, since you’re updating a variable without synchronization, it’s possible to miss updates made by other threads, so the results may be entirely inconsistent.

Besides that, an Iterator has to be polled sequentially, so to get at least some gain from parallel processing, elements have to be buffered, but without a known size, there is no good estimate on how many elements to buffer. The default strategy uses more than thousand elements and does not split the work well.

So if you use more than thousand elements you might notice more parallel activity. Alternatively, you may specify a size using StreamSupport.stream(Spliterators.spliterator(iter, lstr.size(), 0), true) to construct the stream. Then, the internally used buffering will be adapted.

Still, the List’s stream will have a more efficient parallel processing, as it not only knows its size but supports splitting the workload utilizing the random access nature of the underlying data structure.

Answer 2

The current implementation will try to parallelize a stream produced form an iterator by buffering up the values and dispatching them to several threads but it only kicks in if the stream is long enough. Increase your list to 10000 elements and you should see parallelism.

With a large list, it might be easier to see how elements distributed by thread if you collect into a map grouped by thread. Replace your .forEach with .collect(Collectors.groupingBy(x -> Thread.currentThread().getName(), Collectors.counting()))

Answer 3

There was a flaw in Spliterators.spliteratorUnknownSize() implementation. I fixed it in Java 19, see JDK-8280915. Since 19-ea+19-1283 early access build the problem is not reproduced anymore, Spliterators.spliteratorUnknownSize is parallelized correctly. Here's the output on my machine:

Iterator Stream: 
0 0 0 1 0 0 6 7 8 0 0 0 0 12 0 15 0 17 18 10 20 21 22 23 11 0 5 27 28 29 30 0 31 32 3 35 36 37 38 39 40 41 42 4 0 2 45 45 43 34 33 26 25 24 54 19 56 16 0 59 59 0 62 14 13 13 65 64 63 61 60 57 71 73 73 75 76 55 54 79 52 51 50 49 48 47 46 85 84 80 74 70 70 68 67 66 94 92 88 98