Categories
java java-8 java-stream lambda

Why filter() after flatMap() is “not completely” lazy in Java streams?

79

I have the following sample code:

System.out.println(
       "Result: " +
        Stream.of(1, 2, 3)
                .filter(i -> {
                    System.out.println(i);
                    return true;
                })
                .findFirst()
                .get()
);
System.out.println("-----------");
System.out.println(
       "Result: " +
        Stream.of(1, 2, 3)
                .flatMap(i -> Stream.of(i - 1, i, i + 1))
                .flatMap(i -> Stream.of(i - 1, i, i + 1))
                .filter(i -> {
                    System.out.println(i);
                    return true;
                })
                .findFirst()
                .get()
);

The output is as follows:

1
Result: 1
-----------
-1
0
1
0
1
2
1
2
3
Result: -1

From here I see that in first case stream really behaves lazily – we use findFirst() so once we have first element our filtering lambda is not invoked.
However, in second case which uses flatMaps we see that despite first element which fulfils the filter condition is found (it’s just any first element as lambda always returns true) further contents of the stream are still being fed through filtering function.

I am trying to understand why it behaves like this rather than giving up after first element is calculated as in the first case.
Any helpful information would be appreciated.

10

68

+50

TL;DR, this has been addressed in JDK-8075939 and fixed in Java 10 (and backported to Java 8 in JDK-8225328).

When looking into the implementation (ReferencePipeline.java) we see the method [link]

@Override
final void forEachWithCancel(Spliterator<P_OUT> spliterator, Sink<P_OUT> sink) {
    do { } while (!sink.cancellationRequested() && spliterator.tryAdvance(sink));
}

which will be invoke for findFirst operation. The special thing to take care about is the sink.cancellationRequested() which allows to end the loop on the first match. Compare to [link]

@Override
public final <R> Stream<R> flatMap(Function<? super P_OUT, ? extends Stream<? extends R>> mapper) {
    Objects.requireNonNull(mapper);
    // We can do better than this, by polling cancellationRequested when stream is infinite
    return new StatelessOp<P_OUT, R>(this, StreamShape.REFERENCE,
                                 StreamOpFlag.NOT_SORTED | StreamOpFlag.NOT_DISTINCT | StreamOpFlag.NOT_SIZED) {
        @Override
        Sink<P_OUT> opWrapSink(int flags, Sink<R> sink) {
            return new Sink.ChainedReference<P_OUT, R>(sink) {
                @Override
                public void begin(long size) {
                    downstream.begin(-1);
                }

                @Override
                public void accept(P_OUT u) {
                    try (Stream<? extends R> result = mapper.apply(u)) {
                        // We can do better that this too; optimize for depth=0 case and just grab spliterator and forEach it
                        if (result != null)
                            result.sequential().forEach(downstream);
                    }
                }
            };
        }
    };
}

The method for advancing one item ends up calling forEach on the sub-stream without any possibility for earlier termination and the comment at the beginning of the flatMap method even tells about this absent feature.

Since this is more than just an optimization thing as it implies that the code simply breaks when the sub-stream is infinite, I hope that the developers soon prove that they “can do better than this”…


To illustrate the implications, while Stream.iterate(0, i->i+1).findFirst() works as expected, Stream.of("").flatMap(x->Stream.iterate(0, i->i+1)).findFirst() will end up in an infinite loop.

Regarding the specification, most of it can be found in the

chapter “Stream operations and pipelines” of the package specification:

Intermediate operations return a new stream. They are always lazy;

… Laziness also allows avoiding examining all the data when it is not necessary; for operations such as “find the first string longer than 1000 characters”, it is only necessary to examine just enough strings to find one that has the desired characteristics without examining all of the strings available from the source. (This behavior becomes even more important when the input stream is infinite and not merely large.)

Further, some operations are deemed short-circuiting operations. An intermediate operation is short-circuiting if, when presented with infinite input, it may produce a finite stream as a result. A terminal operation is short-circuiting if, when presented with infinite input, it may terminate in finite time. Having a short-circuiting operation in the pipeline is a necessary, but not sufficient, condition for the processing of an infinite stream to terminate normally in finite time.

It’s clear that a short-circuiting operation doesn’t guaranty a finite time termination, e.g. when a filter doesn’t match any item the processing can’t complete, but an implementation which doesn’t support any termination in finite time by simply ignoring the short-circuiting nature of an operation is far off the specification.

12

  • 29

    This a bug. While it might be true that the specification supports this behavior, no one expects that getting the first element of an infinite stream will throw a StackOverflowError or will end up in an infinite loop, no matter if it comes directly from the source of the pipeline or from a nested stream via a mapping function. This should be reported as a bug.

    – fps

    Mar 24, 2015 at 11:30


  • 7

    @Vadym S. Khondar: filing a bug report is a good idea. Regarding why didn’t someone spot this before, I have seen a lot of “can’t believe I’m the first one to notice this” kind of bugs before. Unless infinite streams are involved, this bug has only performance impacts which might stay unnoticed in a lot of use cases.

    – Holger

    Mar 24, 2015 at 16:18


  • 7

    @Marko Topolnik: the property “does not begin until the terminal operation of the pipeline is executed” does not negate other properties of lazy operations. I know that there is no single-sentence declaration of the discussed property, otherwise I cited it. Within the Stream API doc it is said that “Streams are lazy; computation on the source data is only performed when the terminal operation is initiated, and source elements are consumed only as needed.”

    – Holger

    Mar 24, 2015 at 17:24

  • 6

    You may question again wither this implies a lazy execution guaranty regarding short-circuiting, however, I tend to see it the other way round: at no point it is said that implementations are free to implement non-lazy behavior the way we see here. And the specification is very exhaustive regarding what is permissible and what not.

    – Holger

    Mar 24, 2015 at 17:30

  • 5

    JDK-8075939 makes progress now. See mail.openjdk.java.net/pipermail/core-libs-dev/2017-December/… for the core-libs-dev review thread and a link to the first webrev. It apppears we’ll see it in Java 10.

    Dec 22, 2017 at 12:49

18

The elements of the input stream are consumed lazily one by one. The first element, 1, is transformed by the two flatMaps into the stream -1, 0, 1, 0, 1, 2, 1, 2, 3, so that entire stream corresponds to just the first input element. The nested streams are eagerly materialized by the pipeline, then flattened, then fed to the filter stage. This explains your output.

The above does not stem from a fundamental limitation, but it would probably make things much more complicated to get full-blown laziness for nested streams. I suspect it would be an even greater challenge to make it performant.

For comparison, Clojure’s lazy seqs get another layer of wrapping for each such level of nesting. Due to this design, the operations may even fail with StackOverflowError when nesting is exercised to the extreme.

2

  • 2

    @MarkoTopolnik, thanks for your reply. Actually, the concern brought by Holger is actually reason of my surprise. Does the second case mean that I can’t use flatMap for infinite streams?

    Mar 24, 2015 at 10:50

  • Yes, I bet that the nested stream cannot be infinite.

    Mar 24, 2015 at 12:27

8

With regard to breakage with infinite sub-streams, the behavior of flatMap becomes still more surprising when one throws in an intermediate (as opposed to terminal) short-circuiting operation.

While the following works as expected, printing out the infinite sequence of integers

Stream.of("x").flatMap(_x -> Stream.iterate(1, i -> i + 1)).forEach(System.out::println);

the following code prints out only the “1”, but still does not terminate:

Stream.of("x").flatMap(_x -> Stream.iterate(1, i -> i + 1)).limit(1).forEach(System.out::println);

I cannot imagine a reading of the spec in which that were not a bug.