Review use of @inline methods in compiler/library

[retronym]

I noticed that mapConserve is now inlined (in 2.12.x). That is ostensibly a progression, as it is marked with the @inline annotation.

However, the benefit of devirtualizing the apply call within the iteration should be weighed against the cost of duplicated code and increased method size at the call site.

We should review such methods (perhaps looking first at the ones that are most frequently inlined now), and decide whether the annotation makes sense. I might also be possible to restructure the method internals so that some sections of code are factored into sub-methods marked @noinline.

We also now have the flexibility to control inlining with annotations at the call site (as tested in InlinerTest#inlineNoInlineOverride. This would allow us to, for example, remove @inline from mapConserve, but use args.mapConserve(_.typeSymbol) @inline if benchmarking suggests it is beneficial in some particular call sites.

Welcome to Scala 2.12.0-20160226-100424-bc25a72 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_71).
Type in expressions for evaluation. Or try :help.

⚡ scala -optimize -Yinline-warnings
Welcome to Scala 2.11.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_71).
Type in expressions for evaluation. Or try :help.

scala> class Conserve { def foo(as: List[String]) = as.mapConserve(x => x) }
<console>:11: warning: Could not inline required method mapConserve because access level required by callee not matched by caller.
       class Conserve { def foo(as: List[String]) = as.mapConserve(x => x) }
                                                                  ^
<console>:11: warning: At the end of the day, could not inline @inline-marked method mapConserve
       class Conserve { def foo(as: List[String]) = as.mapConserve(x => x) }
                                                                  ^
defined class Conserve

scala> :javap Conserve#foo
  public scala.collection.immutable.List<java.lang.String> foo(scala.collection.immutable.List<java.lang.String>);
    descriptor: (Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
    flags: ACC_PUBLIC
    Code:
      stack=3, locals=11, args_size=2
         0: aload_1
         1: ifnonnull     6
         4: aconst_null
         5: athrow
         6: aconst_null
         7: aload_1
         8: aload_1
         9: astore        4
        11: astore_3
        12: astore_2
        13: aload         4
        15: invokevirtual #27                 // Method scala/collection/immutable/List.isEmpty:()Z
        18: ifeq          41
        21: aload_2
        22: ifnonnull     31
        25: aload_3
        26: astore        10
        28: goto          164
        31: aload_2
        32: aload_3
        33: invokevirtual #32                 // Method scala/collection/mutable/ListBuffer.prependToList:(Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
        36: astore        10
        38: goto          164
        41: aload         4
        43: invokevirtual #36                 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
        46: astore        5
        48: aload         5
        50: checkcast     #38                 // class java/lang/String
        53: invokestatic  #42                 // Method $line4$$read$$iw$$iw$Conserve$$$anonfun$1:(Ljava/lang/String;)Ljava/lang/String;
        56: astore        6
        58: aload         6
        60: aload         5
        62: if_acmpne     82
        65: aload_2
        66: aload_3
        67: aload         4
        69: invokevirtual #45                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
        72: checkcast     #23                 // class scala/collection/immutable/List
        75: astore        4
        77: astore_3
        78: astore_2
        79: goto          13
        82: aload_2
        83: ifnonnull     96
        86: new           #29                 // class scala/collection/mutable/ListBuffer
        89: dup
        90: invokespecial #49                 // Method scala/collection/mutable/ListBuffer."<init>":()V
        93: goto          97
        96: aload_2
        97: astore        7
        99: aload_3
       100: astore        8
       102: aload         8
       104: aload         4
       106: if_acmpeq     133
       109: aload         7
       111: aload         8
       113: invokevirtual #36                 // Method scala/collection/immutable/List.head:()Ljava/lang/Object;
       116: invokevirtual #53                 // Method scala/collection/mutable/ListBuffer.$plus$eq:(Ljava/lang/Object;)Lscala/collection/mutable/ListBuffer;
       119: pop
       120: aload         8
       122: invokevirtual #45                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
       125: checkcast     #23                 // class scala/collection/immutable/List
       128: astore        8
       130: goto          102
       133: aload         7
       135: aload         6
       137: invokevirtual #53                 // Method scala/collection/mutable/ListBuffer.$plus$eq:(Ljava/lang/Object;)Lscala/collection/mutable/ListBuffer;
       140: pop
       141: aload         4
       143: invokevirtual #45                 // Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
       146: checkcast     #23                 // class scala/collection/immutable/List
       149: astore        9
       151: aload         7
       153: aload         9
       155: aload         9
       157: astore        4
       159: astore_3
       160: astore_2
       161: goto          13
       164: aload         10
       166: areturn
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0     167     0  this   L$line4/$read$$iw$$iw$Conserve;
            0     167     1    as   Lscala/collection/immutable/List;
           97      67     7 mapConserve_loop$1_b   Lscala/collection/mutable/ListBuffer;
          100      64     8 mapConserve_loop$1_xc   Lscala/collection/immutable/List;
          149      15     9 mapConserve_loop$1_tail0   Lscala/collection/immutable/List;
           46     118     5 mapConserve_loop$1_head0   Ljava/lang/Object;
           56     108     6 mapConserve_loop$1_head1   Ljava/lang/Object;
           13     151     2 mapConserve_loop$1_mapped   Lscala/collection/mutable/ListBuffer;
           13     151     3 mapConserve_loop$1_unchanged   Lscala/collection/immutable/List;
           13     151     4 mapConserve_loop$1_pending   Lscala/collection/immutable/List;

Was:

Welcome to Scala 2.11.8 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_71).
Type in expressions for evaluation. Or try :help.

scala> class Conserve { def foo(as: List[String]) = as.mapConserve(x => x) }
defined class Conserve

scala> :javap Conserve#foo
  public scala.collection.immutable.List<java.lang.String> foo(scala.collection.immutable.List<java.lang.String>);
    descriptor: (Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
    flags: ACC_PUBLIC
    Code:
      stack=4, locals=2, args_size=2
         0: aload_1
         1: new           #9                  // class Conserve$$anonfun$foo$1
         4: dup
         5: aload_0
         6: invokespecial #13                 // Method Conserve$$anonfun$foo$1."<init>":(LConserve;)V
         9: invokevirtual #19                 // Method scala/collection/immutable/List.mapConserve:(Lscala/Function1;)Lscala/collection/immutable/List;
        12: areturn
      LocalVariableTable:
        Start  Length  Slot  Name   Signature
            0      13     0  this   LConserve;
            0      13     1    as   Lscala/collection/immutable/List;
      LineNumberTable:
        line 11: 0
    Signature: #39                          // (Lscala/collection/immutable/List<Ljava/lang/String;>;)Lscala/collection/immutable/List<Ljava/lang/String;>;

[retronym]

/cc @lrytz @gkossakowski

[lrytz]

I did a little bit of coarse-grained benchmarking today. I checked compiling Function1 and all of scalap.

Observations:

• a compiler built with -opt:l:classpath seems to be slightly faster (5% - 10%) than one built without the flag, so that's good news
• I checked if we can remove the existing @inline annotations in the compiler and reflect codebase. I did two versions: first I removed them only from first-order methods (which are never picked by the heuristics, so this means they are not inlined anymore; we leave them to the JVM to profile and inline). Then I removed all @inline annots, which probably doesn't change much: the remaining ones are on higher-order methods, which are picked by the heuristic (if the corresponding argument at callsite is either a function literal or a parameter of the enclosing method).
• I did not see a difference in performance in those two versions, so both of them still seem to have the 5% benefit over the non-optimized version. But the annotations did not hurt either.
• I didn't do enough samples to tell a statistically significant difference between the three versions with the optimizer enabled, there's quite a bit of variation. But the difference to the non-optimized version looks stable.

I also checked what -Yopt-log-inline _ reveals: there are ~600 callsites in the compiler that are chosen by the heuristic but cannot be inlined. The reason for all of them is that the callee contains INVOKESPECIAL calls, which are either super calls or calls to private methods.

• 500 of those are List.map. Here the INVOKESPECIAL is a super-call. This problem should be fixed by Emit trait method bodies in statics scala#5177, when trait bodies are in static methods and super calls are translated to call the static method instead.
• An example for a private method is Typer.silent: its nested methods are lifted to private methods, so they cannot be called from other classes.

There's also a few hand-written higher-order methods where the implementation calls a private method, e.g., IndexedSeqOptimized.forall invokes the private method prefixLengthImpl.