Odd interaction between ArrayList$Itr and Escape Analysis

Krystal Mok rednaxelafx at gmail.com
Mon Sep 12 19:19:24 UTC 2016

Hi Vitaly,

Haha. I've actually fixed the exact same problem in Zing JVM when I found
this out a while ago. Do you guys want the patch be upstreamed?

Here's the bug description that I wrote for Zing, but it applies to HotSpot
as well (since we inherited that bug from HotSpot):

This bug is to track an enhancement that would allow compilation and
inlining of "bridge constructors" for private inner classes, generated by

In HotSpot's compilation policy, and C2's inlining heuristic, if a
method/constructor is found to have unloaded classes in its signature, then
there are special handling:
 * in compilation policy, if a method is about to be triggered a C2
compilation, and there are unloaded classes in its signature, then these
classes are forced to be loaded before compilation;
 * in C2, when a method is considered to be a candidate for inlining, if
there are unloaded classes in its signature, it will NOT be inlined.

It's questionable whether or not the C2 inlining heuristic is profitable in
general, but there's a case where it's definitely not profitable - when
dealing with "bridge constructors" generated by javac.

When javac sees a private inner class with no explicit constructors, e.g.

> package java.util;
> public class ArrayList<E> implements Iterable<E> {
>   public Iterator<E> iterator() {
>     return new Itr();
>   }
>   private class Itr implements Iterator<E> { }
> }

javac will synthesize two constructors for the inner class (e.g. Itr above):
1. The normal default constructor, with accessibility the same as its
holder class - private
  private java.util.ArrayList$Itr(java.util.ArrayList);
2. A "bridge constructor". Because the enclosing class needs to access
Itr's constructor, but doesn't have accessibility to the private one, so
javac futher synthesizes this "bridge constructor" with package
accessibility, which simply delegates to the private default one:
  java.util.ArrayList$Itr(java.util.ArrayList, java.util.ArrayList$1);

The sole purpose of the "bridge constructor" is to provide accessibility,
but if it were only different from the private one in its accessibility,
the two constructors won't be distinguishable under JVM's overload
resolution rules. So, javac pulls a trick, and appends a marker argument
called "access constructor tag" to the argument list of the bridge
constructor, e.g. java.util.ArrayList$1 in this example, and always passes
a null to this argument.

In effect, the class of this marker argument never needs to be loaded,
because it's never instantiated. But C2 isn't happy about unloaded classes
in signature, so it'd refuse to inline any bridge constructors.

0.320:   17       2 TestC2ArrayListIteratorLoop::sumList
0.321:              @ 3   java.util.ArrayList::iterator (10 bytes)
inlined (hot)
0.321:              - @ 6   java.util.ArrayList$Itr::<init> (6 bytes)
unloaded signature classes
0.321:              @ 8   java.util.ArrayList$Itr::hasNext (20 bytes)
inlined (hot)
0.321:                @ 8   java.util.ArrayList::access$100 (5 bytes)
inlined (hot)
0.322:              @ 25   java.lang.Integer::intValue (5 bytes)   inlined

With this enhancement, C2 will be able to ignore the unloaded class in the
bridge constructor, and inline it:

0.269:   18       2 TestC2ArrayListIteratorLoop::sumList
0.269:              @ 3   java.util.ArrayList::iterator (10 bytes)
inlined (hot)
0.270:                @ 6   java.util.ArrayList$Itr::<init> (6 bytes)
inlined (hot)
0.270:                  @ 2   java.util.ArrayList$Itr::<init> (26 bytes)
inlined (hot)
0.270:                  - @ 6   java.lang.Object::<init> (1 bytes)   don't
intrinsify this
0.270:                    @ 6   java.lang.Object::<init> (1 bytes)
inlined (hot)
0.270:              @ 8   java.util.ArrayList$Itr::hasNext (20 bytes)
inlined (hot)
0.270:                @ 8   java.util.ArrayList::access$100 (5 bytes)
inlined (hot)
0.271:              @ 25   java.lang.Integer::intValue (5 bytes)   inlined

- Kris

On Mon, Sep 12, 2016 at 12:13 PM, Vitaly Davidovich <vitalyd at gmail.com>

> Hi all,
> Vladimir I. and I have been looking at a peculiarity in EA as it relates
> to eliminating the ArrayList$Itr.  What Vladimir found (and I see it as
> well) is that ArrayList$Itr::init isn't always inlined due to "unloaded
> signature classes", e.g.:
> @ 6   java.util.ArrayList::iterator (10 bytes)   inline (hot)
>                               @ 6   java.util.ArrayList$Itr::<init> (6
> bytes)   unloaded signature classes
> I tried to dig a bit further into this, and it appears that what's
> "unloaded" is ArrayList$1.  LogCompilation shows this (which I think is
> relevant):
> <bc code='183' bci='6'/>
> <type id='709' name='void'/>
> <klass id='827' name='java/util/ArrayList$1' unloaded='1'/>
> <klass id='821' name='java/util/ArrayList$Itr' flags='2'/>
> <method id='828' holder='821' name='<init>' return='709'
> arguments='820 827' flags='4096' bytes='6' iicount='1853'/>
> <call method='828' count='-1' prof_factor='0.602806' inline='1'/>
> <inline_fail reason='unloaded signature classes'/>
> <direct_call bci='6'/>
> <parse_done nodes='100' live='98' memory='35824' stamp='1.114'/>
> </parse>
> It looks like ArrayList$1 is a synthetic class generated by javac because
> ArrayList$Itr constructor is private (despite the class itself being
> private).  Here's the bytecode (8u51) of ArrayList::iterator:
> public java.util.Iterator<E> iterator();
>     descriptor: ()Ljava/util/Iterator;
>     flags: ACC_PUBLIC
>     Code:
>       stack=4, locals=1, args_size=1
>          0: new           #61                 // class
> java/util/ArrayList$Itr
>          3: dup
>          4: aload_0
>          5: aconst_null
>          6: invokespecial #62                 // Method
> java/util/ArrayList$Itr."<init>":(Ljava/util/ArrayList;
> Ljava/util/ArrayList$1;)V
>          9: areturn
>       LineNumberTable:
>         line 834: 0
>     Signature: #185                         // ()Ljava/util/Iterator<TE;>;
> The only way I can get the Itr allocation removed in my method is by
> causing some other method that does the same thing to be JIT compiled prior
> to mine.
> Does anyone have a good idea of what's actually going on here? Why is that
> synthetic ArrayList$1 such a pest here? It's a bit sad that such a little
> thing can prevent EA from working in a perfectly good candidate method for
> it.
> Thoughts?
> Thanks
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20160912/5eb7a985/attachment-0001.html>

More information about the hotspot-compiler-dev mailing list