Optimize generated code to reduce method count.

[JakeWharton]

Android's file format, dex, is highly sensitive to the number of methods in the contained class files. There's a method table with a 16-bit index which thus restricts the number of methods to 65536. "65536 methods?" you might say, "that should be enough for anyone!" Unfortunately these add up quick for all kinds of reasons.

As I'm sure you are aware, Retrolambda has a big userbase in the Android community due to the restriction of the toolchain only understanding Java 6/7 classfiles. Minimizing the number of methods generated per lambda and method reference would go a long way to help keep applications under this limit.

There's currently four cases whose generated code can be altered to reduce the number of required methods required for each lambda and method reference. By my estimation this will remove between 2000 and 2500 method references from our app! For our current usage count, that's approximately 5%!

Instance factory method

All $$Lambda$ classes have a lambdaFactory$ method which either returns a new instance for capturing lambdas or a cached instance for non-capturing lambdas. The implementation either delegates to the private constructor or a private static field. Removing the private modifier and making these package scoped would allow the constructor or field to be reference directly from the original call site avoiding the need for this method altogether.

Non-capturing example:

class Test {
  public static void main(String... args) {
    run(() -> System.out.println("Hey!"));
  }
  private static void run(Runnable run) {
    run.run();
  }
}

Generates:

final class Test$$Lambda$1 implements java.lang.Runnable {
  private static final Test$$Lambda$1 instance;

  // <omitted>

  public static java.lang.Runnable lambdaFactory$();
    Code:
       0: getstatic     #22                 // Field instance:LTest$$Lambda$1;
       3: areturn
}

class Test {
  public static void main(java.lang.String...);
    Code:
       0: invokestatic  #22                 // Method Test$$Lambda$1.lambdaFactory$:()Ljava/lang/Runnable;
       3: invokestatic  #26                 // Method run:(Ljava/lang/Runnable;)V
       6: return

  // <omitted>
}

Capturing example:

class Test {
  public static void main(String... args) {
    run(() -> System.out.println("Hey!" + args));
  }
  private static void run(Runnable run) {
    run.run();
  }
}

final class Test$$Lambda$1 implements java.lang.Runnable {
  private Test$$Lambda$1(java.lang.String[]);
    Code:
       0: aload_0
       1: invokespecial #13                 // Method java/lang/Object."<init>":()V
       4: aload_0
       5: aload_1
       6: putfield      #15                 // Field arg$1:[Ljava/lang/String;
       9: return

  // <omitted>

  public static java.lang.Runnable lambdaFactory$(java.lang.String[]);
    Code:
       0: new           #2                  // class Test$$Lambda$1
       3: dup
       4: aload_0
       5: invokespecial #19                 // Method "<init>":([Ljava/lang/String;)V
       8: areturn
}

class Test {
  public static void main(java.lang.String...);
    Code:
       0: aload_0
       1: invokestatic  #22                 // Method Test$$Lambda$1.lambdaFactory$:([Ljava/lang/String;)Ljava/lang/Runnable;
       4: invokestatic  #26                 // Method run:(Ljava/lang/Runnable;)V
       7: return

 // <omitted>
}

Completed Parts 🎉

Non-private method references (#84)

Method references on non-private methods (both static and instance) generate a needless package-scoped accessor method. This only needs generated for private methods. All other versions can effectively "inline" the method call directly to the generated $$Lambda$ class.

Example:

class Test {
  public static void main(String... args) {
    run(Test::sayHi);
  }
  private static void run(Runnable run) {
    run.run();
  }
  static void sayHi() {
    System.out.println("Hey!");
  }
}

Generates:

final class Test$$Lambda$1 implements java.lang.Runnable {
  // <omitted>

  public void run();
    Code:
       0: aload_0
       1: getfield      #15                 // Field arg$1:LTest;
       4: invokestatic  #25                 // Method Test.access$lambda$0:(LTest;)V
       7: return
}

class Test {
  // <omitted>

  void sayHi();
    Code:
       0: getstatic     #41                 // Field java/lang/System.out:Ljava/io/PrintStream;
       3: ldc           #43                 // String Hey!
       5: invokevirtual #49                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
       8: return

  static void access$lambda$0(Test);
    Code:
       0: aload_0
       1: invokevirtual #52                 // Method sayHi:()V
       4: return
}

Lambda body methods (#86)

The body of a lambda is copied into a private static method on the defining class with any captured references hoisted into parameters. Being a private method, though, an additional accessor method has to be created so that the $$Lambda$ class can call back into it. Promoting the lambda body method itself to package scoped eliminates the need for this extra indirection.

Example:

class Test {
  public static void main(String... args) {
    run(() -> System.out.println("Hey!" + args));
  }
  private static void run(Runnable run) {
    run.run();
  }
}

Generates:

class Test {
  // <omitted>

  private static void lambda$main$0(java.lang.String[]);
    Code:
       0: getstatic     #37                 // Field java/lang/System.out:Ljava/io/PrintStream;
       3: new           #39                 // class java/lang/StringBuilder
       6: dup
       7: invokespecial #40                 // Method java/lang/StringBuilder."<init>":()V
      10: ldc           #42                 // String Hey!
      12: invokevirtual #46                 // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      15: aload_0
      16: invokevirtual #49                 // Method java/lang/StringBuilder.append:(Ljava/lang/Object;)Ljava/lang/StringBuilder;
      19: invokevirtual #53                 // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      22: invokevirtual #59                 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
      25: return

  static void access$lambda$0(java.lang.String[]);
    Code:
       0: aload_0
       1: invokestatic  #62                 // Method lambda$main$0:([Ljava/lang/String;)V
       4: return
}

Unused factory method (#82)

A factory method named get$Lambda shows up on the $$Lamda$ classes for capturing lambdas. This method duplicates the implementation of the lambdaFactory$ on the same class but is completely unused.

class Test {
  public static void main(String... args) {
    run(() -> System.out.println("Hey!" + args));
  }
  private static void run(Runnable run) {
    run.run();
  }
}

final class Test$$Lambda$1 implements java.lang.Runnable {
  // <omitted>

  private static java.lang.Runnable get$Lambda(java.lang.String[]);
    Code:
       0: new           #2                  // class Test$$Lambda$1
       3: dup
       4: aload_0
       5: invokespecial #19                 // Method "<init>":([Ljava/lang/String;)V
       8: areturn

  // <omitted>
}

[JakeWharton]

There's a TODO for skipping package scoped accessor methods in the code base already: https://github.com/orfjackal/retrolambda/blob/6371ddaa52262d3e42262ad0a409bf0d435eeb10/retrolambda/src/main/java/net/orfjackal/retrolambda/lambdas/BackportLambdaInvocations.java#L65

[luontola]

1. OK.
2. Private instance methods cannot be made package-scoped, but only on private static methods, because of inheritance. See this test. Otherwise this optimizations is OK.
3. OK. The bytecode for calling a constructor is more complex than calling a static method; it requires some stack shuffling.
4. It's not guaranteed that all JREs (current and future) will generate that factory method, so there might need to be a fallback in case it is missing.

There is quite much work in implementing those optimizations, because bytecode manipulation is hard, so I hope that somebody else would have the time to look into it and create a pull request.

[JakeWharton]

RE 2: I don't mean changing the user code at all, but the private static method which is generated (lambda$main$0). Right now the generated lambda class calls the private static generated access$lambda$0 which calls the package static generated lambda$main$0 which then runs the user code. This proposal would just skip one of those two generated methods (having the lambda class call lambda$main$0 directly and changing it from private static to package static).

bytecode manipulation is hard

It is hard, but I'm not opposed here having done my share of ASM. I filed the issue to get initial thoughts, and I'm definitely going to try one or two next week. Would too love to see some additional help.

[JakeWharton]

@orfjackal Can you explain your response to 4 more? I don't quite understand where that get$Lambda method comes from on the lambda class or what it's for.

[JakeWharton]

I have implemented 3, but would like #82 to be merged first since I want to use its added tests to prove the factory method is no longer included. Doing so as a sibling PR would only cause merge conflicts.

[luontola]

RE 2: Some of the generated lambda$xxx$1 methods are instance methods. For example the one created for https://github.com/orfjackal/retrolambda/blob/v2.1.0/end-to-end-tests/src/test/java/net/orfjackal/retrolambda/test/LambdaTest.java#L59 Maybe it has to do with capturing this.

RE 4: the get$Lambda is generated and used by java.lang.invoke.InnerClassLambdaMetafactory. If I remember right, some of the older JDK 8 builds did not produce that factory method, so relying on its existence is risky. Your pull request which removes it is a good idea. Thanks for that.

[luontola]

Your pull requests are now included in Retrolambda 2.3.0. Sorry for taking so long. 😓

[JakeWharton]

Thank you!