34

Reading up a bit on Java 8, I got to this blog post explaining a bit about streams and reduction of them, and when it would be possible to short-circuit the reduction. At the bottom it states:

Note in the case of findFirst or findAny we only need the first value which matches the predicate (although findAny is not guaranteed to return the first). However if the stream has no ordering then we’d expect findFirst to behave like findAny. The operations allMatch, noneMatch and anyMatch may not short-circuit the stream at all since it may take evaluating all the values to determine whether the operator is true or false. Thus an infinite stream using these may not terminate.

I get that findFirst or findAny may short-circuit the reduction, because as soon as you find an element, you do not need to process any further.

But why would this not be possible for allMatch, noneMatch and anyMatch? For allMatch, if you find one which doesn't match the predicate, you can stop processing. Same for none. And anyMatch especially doesn't make sense to me, as it it pretty much equal to findAny (except for what is returned)?

Saying that these three may not short-circuit, because it may take evaluating all the values, could also be said for findFirst/Any.

Is there some fundamental difference I'm missing? Am I not really understanding what is going on?

2240
  • 1,547
  • 2
  • 12
  • 30
Koekje
  • 677
  • 1
  • 6
  • 17

6 Answers6

28

There's a subtle difference, because anyMatch family uses a predicate, while findAny family does not. Technically findAny() looks like anyMatch(x -> true) and anyMatch(pred) looks like filter(pred).findAny(). So here we have another issue. Consider we have a simple infinite stream:

Stream<Integer> s = Stream.generate(() -> 1);

So it's true that applying findAny() to such stream will always short-circuit and finish while applying anyMatch(pred) depends on the predicate. However let's filter our infinite stream:

Stream<Integer> s = Stream.generate(() -> 1).filter(x -> x < 0);

Is the resulting stream infinite as well? That's a tricky question. It actually contains no elements, but to determine this (for example, using .iterator().hasNext()) we have to check the infinite number of underlying stream elements, so this operation will never finish. I would call such stream an infinite as well. However using such stream both anyMatch and findAny will never finish:

Stream.generate(() -> 1).filter(x -> x < 0).anyMatch(x -> true);
Stream.generate(() -> 1).filter(x -> x < 0).findAny();

So findAny() is not guaranteed to finish either, it depends on the previous intermediate stream operations.

To conclude I would rate that blog-post as very misleading. In my opinion infinity stream behavior is better explained in official JavaDoc.

Jean-François Savard
  • 20,626
  • 7
  • 49
  • 76
Tagir Valeev
  • 97,161
  • 19
  • 222
  • 334
14

Answer Updated

I'd say the blog post is wrong when it says "findFirst or findAny we only need the first value which matches the predicate".

In the javadoc for allMatch(Predicate), anyMatch(Predicate), noneMatch(Predicate), findAny(), and findFirst():

This is a short-circuiting terminal operation.

However, note that findFirst and findAny doesn't have a Predicate. So they can both return immediately upon seeing the first/any value. The other 3 are conditional and may loop forever if condition never fires.

Andreas
  • 154,647
  • 11
  • 152
  • 247
  • 1
    From the blog: "The operations allMatch, noneMatch and anyMatch may not short-circuit the stream at all since it may take evaluating all the values to determine whether the operator is true or false." This is obviously incorrect since `allMatch` can be determined to be false as soon as first non-match is found. – Miserable Variable Aug 24 '15 at 23:06
  • @MiserableVariable As I said, blog post is wrong. They *can* all short-circuit. --- The blog is right that 3 of them may *potentially* run forever, but it says it all wrong. – Andreas Aug 24 '15 at 23:09
6

According to Oracle's Stream Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html#StreamOps

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.

All five functions have the line:

This is a short-circuiting terminal operation.

In the description of the function.

WillShackleford
  • 6,918
  • 2
  • 17
  • 33
1

When the javadoc says "may not short-circuit" it is merely pointing out that it is not a short circuit operation and depending on the values, the entire stream may be processed.

findFirst and findAny on the other hand, are guaranteed to short circuit since they never need to process the rest of the stream once they are satisfied.

Trevor Freeman
  • 7,112
  • 2
  • 21
  • 40
0

anyMatch, noneMatch and allMatch return boolean values, so they may have to check all to prove the logic.

findFirst and findAny just care about finding the first they can and returning that.

Edit: For a given dataset the Match methods are guaranteed to always return the same value, however the Find methods are not because the order may vary and affect which value is returned.

The short circuiting described is talking about the Find methods lacking consistency for a given dataset.

  • But anyMatch does as well? – Koekje Aug 24 '15 at 22:47
  • If the last value was the match, then yes. Point is the Match methods will always return the same value on the same data set, but the Find methods aren't guaranteed that consistency because the order may differ. –  Aug 24 '15 at 22:53
  • This lack of consistency is the short circuiting described –  Aug 24 '15 at 22:55
0
LongStream.range(0, Long.MAX_VALUE).allMatch(x -> x >= 0)

LongStream.range(0, Long.MAX_VALUE).allMatch(x -> x > 0)

The first one returns forever, the second one returns immediately

Kai Liu
  • 121
  • 2
  • 7