how fragile is escape analysis in Hotspot in simple cases such as iterator in for-each loop

Question

Suppose I have a java.util.Collection that I want to loop over. Normally I'd do this:

for(Thing thing : things) do_something_with(thing);

But suppose that this is in some core utility method that is used all over the place, and in most places, the collection is empty. Then ideally we would prefer not impose an iterator allocation on every single caller just to perform a no-op loop, and we could rewrite things like this:

if(things.isEmpty()) return;
for(Thing thing : things) do_something_with(thing);

An even more extreme option, if things is a List, would be to use a C-style for loop.

But wait, Java-escape analysis should eliminate this allocation, at least after the C2 compiler gets around to this method. So there should be no need for this "nano-optimization". (I won't even dignify it with the term micro-optimization; it's a bit too small for that.) Except...

I keep hearing that escape analysis is "fragile" but no one seems to ever talk about what in particular can mess it up. Intuitively, I would think that more complicated control flow would be the main thing to fear, which means iterators in a for-each loop should be RELIABLY eliminated, since there the control flow is simple.

The standard response here is to try running an experiment, but unless I know the variables in play, it's pretty hard to trust any conclusions I might be tempted to draw from such an experiment.

Indeed, here's a blog post where someone tried such an experiment, and 2 out of 3 profilers gave the wrong results:

http://psy-lob-saw.blogspot.com/2014/12/the-escape-of-arraylistiterator.html

I know a lot less about obscure JVM wizardry than the author of that blog post, and am likely to be far more easily misled.

Answer 1

Scalar Replacement is indeed a kind of optimization that you can never be absolutely certain about, because it depends on too many factors.

First, an allocation may be eliminated only when all uses of the instance are inlined in one compilation unit. In case of an iterator, it means that the iterator constructor, hasNext and next calls (including the nested calls) must be inlined.

public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

However, inlining itself is a fragile optimization in HotSpot, since it relies on many heuristics and limits. For example, it may happen that iterator.next() call is not fully inlined into the loop due to reaching the maximum inlining depth, or because the outer compilation is already too big.

Second, scalar replacement does not happen if a reference conditionally receives different values.

for(Thing thing : things) do_something_with(thing);

In your example, if things is sometimes ArrayList and sometimes Collections.emptyList(), the iterator will be allocated on the heap. For elimination to happen, the type of the iterator must always be the same.

There are more examples in a great talk on Scalar Replacement by Ruslan Cheremin (it's in Russian, but YouTube's subtitles translation feature to the rescue).

Another recommended read is Aleksey Shipilёv's blog post, which also demonstrates how to use JMH to verify whether Scalar Replacement happens in a particular scenario or not.

In short, in simple cases like yours, there is a high chance that allocation elimination will work as expected. There may be some marginal cases though, as I mentioned above.

There is a recent discussion on hotspot-compiler-dev mailing list regarding Partial Escape Analysis proposal. If implemented, it could significantly extend the applicability of Scalar Replacement optimization.