Will the JVM be able to hoist a Java stream from within a loop?

Question

I'm wondering if the JVM is able to hoist a stream out of a loop, for example in this intersection check that I wrote:

for (SomeObject someObject:someObjects) {
    if (someList.stream().map(SomeObject::getValue).collect(Collectors.toList())
            .contains(someObject.getValue())) {
        //do some error stuff
    }
}

Is it necessary for me to refactor it like so:

final List<Value> values = someList.stream().map(SomeObject::getValue).collect(Collectors.toList());
for (SomeObject someObject:someObjects) {
    if (values.contains(someObject.getValue()) {
        //do some error stuff
    }
}

It's probably nicer looking code this way, but I'm just wondering if it will have a big performance difference.

I see no reason why the first version would not work. Have you tried it yet? Note that you _could_ also rewrite the first `for` loop using `foreach`, if you are a real glutton for lambda expressions. — Tim Biegeleisen, Sep 20 '18 at 10:54
Do you need to process each overlapping item separately? Or, would a single error message suffice? — Tim Biegeleisen, Sep 20 '18 at 10:59
@Tim both work fine, I'm just wondering about the performance impact of doing this over a large loop, and more generally what the JVM can and can't hoist — Adam Beddoe, Sep 20 '18 at 11:01
I think also using a Set and not a List would improve the performance, in the second code block — Matthieu Gabin, Sep 20 '18 at 11:10

score 1 · Answer 1 · answered Sep 20 '18 at 10:55

1

Yeah the second code is way better, in the first one you were creating from scratch the stream for each 'SomeObject'.

answered Sep 20 '18 at 10:55

vc73

407
3
15

This would be my intuition as well, but some preliminary testing doesn't show any difference in performance. Can you provide some evidence for why it needs to do that? – Adam Beddoe Sep 20 '18 at 11:03
2

@AdamBeddoe The JVM/compiler might be smart enough to realize that your list from a stream is not correlated to the containing loop, and knows enough to pull it out and compute it only once. But, the second version is what I think you should be using here. – Tim Biegeleisen Sep 20 '18 at 11:04
@AdamBeddoe are you sure that your performance test is correct? Maybe your compiler or JIT just moved stream out of loop for first code sample? – Ivan Sep 20 '18 at 12:11
Intuitive stream solution would be something like: `if (someObjects.stream() .anyMatch(someObject -> someList.stream() .anyMatch(someListItem -> someListItem.getValue().equals(someObject.getValue()))) ) { // do stuff; }` – dbl Sep 20 '18 at 12:29

score 0 · Answer 2 · answered Sep 20 '18 at 12:30

0

I'd bet "No". AFAIK the JVM does no interprocedural optimizations. There may be some exceptions, but basically, it only optimizes a single method at a time. For this to be really helpful, it relies on inlining, but your expression is far too complicated for inlining.

Anyway, your second snippet

final List<Value> values = someList.stream().map(SomeObject::getValue).collect(Collectors.toList());
for (SomeObject someObject:someObjects) {
    if (values.contains(someObject.getValue()) {
        //do some error stuff
    }
}

is not optimal either. With the stream inside the loop, you could use

...anyMatch(v -> v.equals(someObject.getValue())

to save yourself collecting. Or, better, you can use a Set for faster lookup.

answered Sep 20 '18 at 12:30

maaartinus

44,714
32
161
320

The JVM definitely *does* “interprocedural optimizations”, known as performing “aggressive inlining” as the very first step before applying any other optimization. It would be disastrous if it didn’t. However, in this specific example, chances are high, that the overall code exceeds specific limits (maximum code size, maximum inlining depth) or hits a construct that prevents the full set of potential optimizations. The Stream implementation has quiet long call chains and Java 8’s limits are not up-to-date… – Holger Sep 20 '18 at 13:19
@Holger I see, I should reformulate my answer... AFAIK all these "interprocedural optimizations" are actually "aggressive inlining" followed by "intraprocedural optimizations". Or are there any exceptions, where the JVM can do something useful for a non-inlined method? – maaartinus Sep 20 '18 at 13:54
@Holger *agresive inlining*? Is this different that *inlining*? First time I hear about this? And also the code inside the JVM has been slightly adjusted to take into account for streams, I remember seing even comments for it – Eugene Sep 20 '18 at 14:08
@Holger I think [this is related](https://stackoverflow.com/questions/44161545/can-hotspot-inline-lambda-function-calls) – Eugene Sep 20 '18 at 14:12
@Eugene “Aggressive inlining” is an umbrella term for “speculative inlining”, “optimistic inlining”, and perhaps some other forms, which have in common that it is not guaranteed that the method invocation always ends up at the method that has been inlined, so fall-backs must be inserted to handle the other cases and even de-optimization may follow at a later time. It may also be used to emphasize that it is not applied merely for eliminating the invocation overhead, but to enable subsequent optimizations, which outweigh any invocation related costs. – Holger Sep 20 '18 at 14:16
@Holger something very new for me with speculative inline, thank you; will need to read about it more. As far as fall backs go, I know about these, at least I think so, that deoptimizations are possible, what zombie methods are, etc. Thank you for the insight – Eugene Sep 20 '18 at 14:39
This article seems to show that the JVM will perform this sort of loop hoisting, but perhaps streams are far too complex for this sort of thing. https://advancedweb.hu/2016/06/28/jvm_jit_optimization_techniques_part_2/ – Adam Beddoe Sep 21 '18 at 09:13
Yes, done some proper benchmarks and the second version is significantly faster. – Adam Beddoe Sep 21 '18 at 10:21

Will the JVM be able to hoist a Java stream from within a loop?

2 Answers2

Linked