Consider indy-fy boilerplate around case class

[harpocrates]

Taking a page from Java's implementation of record, Scala could change the codgen for some auto-generated methods in case class to just invokedynamic with a bootstrap method similar to ObjectMethods (that's what Java uses to implement toString/equals/hashCode on records). Since the specifics of Scala's equality, hash code, and string representation differ from Java records, we'd need to add some scala.runtime.ScalaCaseMethods (instead of directly re-using ObjectMethods).

I think this trick would work for:

• toString
• hashCode
• equals
• productElementName
• productElement
• copy (maybe - the current bytecode is already pretty trivial)
• unapply
• apply

The motivation for this is that:

• bytecode would be much shorter
• future improvements to these methods would only need to change scala.runtime.ScalaCaseMethods

Of course, we would need to make sure this does not regress performance. I threw together the very simplest of benchmarks and results were very encouraging (although likely muddled due to the fact that Scala-generated equals has different semantics).

[smarter]

One problem with using invokedynamic is that it doesn't work for the JS and native backend, so we'd need to maintain two codepaths.

[harpocrates]

I recently learned that Scala supports macros that generate invokedynamic code, so I decided to use that feature to benchmark this further. Using this macro and this bootstrap method I was able to simulate alternate invokedynamic codegen for equals by manually overriding:

final case class SmallScalaModified(
  i: Int,
  s: String,
  l: Long
) {
  override def equals(other: Any): Boolean = Macros.equals(this, other)  // generates an `invokedynamic`
}

Bytecode before

  public boolean equals(java.lang.Object);
    descriptor: (Ljava/lang/Object;)Z
    flags: ACC_PUBLIC
    Code:
      stack=4, locals=6, args_size=2
         0: aload_0
         1: aload_1
         2: if_acmpeq     102
         5: aload_1
         6: astore_3
         7: aload_3
         8: instanceof    #2                  // class records/SmallScala
        11: ifeq          19
        14: iconst_1
        15: istore_2
        16: goto          27
        19: goto          22
        22: iconst_0
        23: istore_2
        24: goto          27
        27: iload_2
        28: ifeq          106
        31: aload_1
        32: checkcast     #2                  // class records/SmallScala
        35: astore        4
        37: aload_0
        38: invokevirtual #62                 // Method i:()I
        41: aload         4
        43: invokevirtual #62                 // Method i:()I
        46: if_icmpne     98
        49: aload_0
        50: invokevirtual #65                 // Method s:()Ljava/lang/String;
        53: aload         4
        55: invokevirtual #65                 // Method s:()Ljava/lang/String;
        58: astore        5
        60: dup
        61: ifnonnull     73
        64: pop
        65: aload         5
        67: ifnull        81
        70: goto          98
        73: aload         5
        75: invokevirtual #137                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
        78: ifeq          98
        81: aload_0
        82: invokevirtual #68                 // Method l:()J
        85: aload         4
        87: invokevirtual #68                 // Method l:()J
        90: lcmp
        91: ifne          98
        94: iconst_1
        95: goto          99
        98: iconst_0
        99: ifeq          106
       102: iconst_1
       103: goto          107
       106: iconst_0
       107: ireturn

Bytecode after

  public boolean equals(java.lang.Object);
    descriptor: (Ljava/lang/Object;)Z
    flags: ACC_PUBLIC
    Code:
      stack=2, locals=2, args_size=2
         0: aload_0
         1: aload_1
         2: invokedynamic #75,  0             // InvokeDynamic #0:equals:(Lrecords/SmallScalaModified;Ljava/lang/Object;)Z
         7: ireturn
...
BootstrapMethods:
  0: #72 invokestatic records/ScalaObjectMethods.bootstrap:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/Class;[Ljava/lang/invoke/MethodHandle;)Ljava/lang/invoke/ConstantCallSite;
    Method arguments:
      #2 records/SmallScalaModified
      #63 getfield records/SmallScalaModified.i:I
      #64 getfield records/SmallScalaModified.s:Ljava/lang/String;
      #65 getfield records/SmallScalaModified.l:J

I made a handful of equality benchmark cases and here are the results (running on JDK 16):

I was concerned that maybe these results would only work for recent JDKs (perhaps due to progress in optimizing invokedynamic), but running on JDK 8 still showed a substantial speedup when using invokedynamic

Given how significant the speedup is and how much boilerplate bytecode it would remove, I think this would be worth maintaining multiple codepaths.

[harpocrates]

One further update: creating an invokedynamic version of hashCode also provided a substantial speedup while reducing boilerplate. Java records have more efficient hashCode likely because the algorithm is simply faster than Scala's.

OTOH, my initial attempts to indy-fy productElement have not proved successful; in that case the invokedynamic version was 50% slower than the generated bytecode (hypothesis: the lack of anything like tableswitch in MethodHandles is the issue).

At this point, I don't think there is much more left to try. From my initial list:

• toString - not tried: could be optimized, but then might break some code (eg. for people overriding productElement)
• hashCode - tried: invokedynamic was faster
• equals - tried: invokedynamic was faster
• productElementName - not tried: there isn't any boilerplate to abstract
• productElement - tried: invokedynamic was slower
• copy - not tried: not enough boilerplate
• unapply - not tried: this should work, but my macro trick for prototyping relies on Scala 2 (Improve support for macros targeting invokedynamic scala#9528 + some patches) and won't work for static methods
• apply - not tried: not enough boilerplate and static method

[smarter]

Very interesting benchmark results! /cc @retronym who should be interested in this.

I was concerned that maybe these results would only work for recent JDKs (perhaps due to progress in optimizing invokedynamic), but running on JDK 8 still showed a substantial speedup when using invokedynamic

That's good to know, it would also be interesting to try this on graalvm I think.

[smarter]

A benchmark variant that might be interesting: generate a bunch of class instances with random values, store them in an array, and compare their equality with java.util.Arrays.deepEquals.

[harpocrates]

That's good to know, it would also be interesting to try this on graalvm I think.

I'll try this after work and post plots.

A benchmark variant that might be interesting: generate a bunch of class instances with random values, store them in an array, and compare their equality with java.util.Arrays.deepEquals.

Interesting too... I'll try this (probably with something like Gen from scalacheck). You mean just java.util.Arrays.equals though, right? I think there isn't any need for nested array equality.

[smarter]

Ah yeah, I forgot about Arrays.equals

[harpocrates]

Here are the new tests. I'm getting more and more confident that this is a change worth implementing.

Different JVMs

As a reference, here is HotSpot 16 again:

I checked GraalVM 16 (from here). Unsurprisingly, looks quite similar to HotSpot (interestingly a little slower - the max y is different).

OpenJ9 performs abysmally on things related to invokedynamic. Since I had a benchmark showing how much worse Java records were compared to HotSpot, I opened eclipse-openj9/openj9#12359, and it turns out this is a difference that they are actively working on fixing for the next major release. Note the massive different in the max y compared to other plots!

Some more checks

Thinking about the comment from @smarter, I realized comparing randomly generated records would not be very interesting: that'd be overwhelmingly testing the path that short-circuits to false on the first unequal field. Instead, I took my large record data type and benchmarked equality with different prefixes of fields being equal.

I was initially expecting this to be a plot with bars growing linearly from left to right (and they sort of do for the non-invokedynamic blue bars), but the generally flat nature of this made me realize that the JIT was probably too good at figuring out the likelihood of each conditional jump. The flatter nature of the red bars likely indicates this optimization works better on invokedynamic.

Still, to get a more even picture, I did one more benchmark where I would repeatedly loop through all the equality checks from the previous plot (so as to prevent the JIT from overfitting equals to any particular test). The results are less pronounced, but still significantly in favor of invokedynamic. (They also confirm that the JIT was overfitting to the test cases from before since the sums of the red/blue bars from the previous plot are nowhere near this plot's red/blue bars)

[retronym]

Thanks for investigating this. I ran your benchmarks to reproduce the results and understand the performance gap.

Looking that the JIT inlining logs (either with -XX+PrintInlining or by dumping a hotspot logfile and visualiing with JITWatch reveals:

[info]                               @ 127   records.LargeScala::t (5 bytes)   accessor
[info]                               @ 132   records.LargeScala::t (5 bytes)   accessor
[info]                               @ 135   scala.runtime.BoxesRunTime::equals (13 bytes)   inline (hot)
[info]                                 @ 9   scala.runtime.BoxesRunTime::equals2 (52 bytes)   inline (hot)
[info]                                   @ 48   records.SmallScala::equals (108 bytes)   inline (hot)
[info]                                    \-> TypeProfile (11560/11560 counts) = records/SmallScala
[info]                                     @ 38   records.SmallScala::i (5 bytes)   accessor
[info]                                     @ 43   records.SmallScala::i (5 bytes)   accessor
[info]                                     @ 50   records.SmallScala::s (5 bytes)   unloaded signature classes
[info]                                     @ 55   records.SmallScala::s (5 bytes)   unloaded signature classes
[info]                                     @ 75   java.lang.String::equals (50 bytes)   inline (hot)
[info]                                       @ 44   java.lang.StringLatin1::equals (36 bytes)   (intrinsic)
[info]                                     @ 82   records.SmallScala::l (5 bytes)   accessor
[info]                                     @ 87   records.SmallScala::l (5 bytes)   accessor

The accessor methods for the String-typed fields aren't being inlined!

After reading:

• https://wiki.openjdk.java.net/display/HotSpot/Server+Compiler+Inlining+Messages
• Trivial call site not inlining with invokedynamic jruby/jruby#6280 (comment)

... I tried some of the workarounds. Both -XX:-TieredCompilation and adding MethodHandles.lookup().ensureInitialized(classOf[String]) or just "".length to the benchmark setup triggers resolution of java/lang/String in the classloader of the JITted method and brings the performance to parity. (The string literals in the file aren't enough, it seems you can reference them from the constant pool of a class without java/lang/String being resolved in that class's classloader.

One thing I don't understand is why some method call to java/lang/String.* from the JMH framework itself didn't trigger initialization of that class. Perhaps there is some classloader layering going on so that JMH is in a parent loader?

In practice you'd be pretty unlucky in real code not to have java/lang/String initialized before you JIT a case class equals.

Could the same problem happen for user-classes? I think it is relatively unlikely, but not impossible. Here's one scenario:

class X
case class A(x: X)

val a1, a2 = new A(null)
for (i <- 0 to 100000) a1 == a2


val a3, a4 = new A1(new X) // X will be initialized now.
for (i <- 0 to 100000) a3 == a4

Similar scenarios could appear if the equals method always had a fast path result of true prior to compilation.

It is likely, though, that in JIT would have assumed that part of the method was dead and the new data shapes would deoptimize and recompile, after which the x accessor would be inlined!

The equals implementations used by JavaObjectMethods (ie java records) and ScalaObjectMethods don't run into this JIT corner case because they use GETFIELD. For java records this is fine because they are final; but case classes aren't final and can be overriden; using a GETFIELD has the wrong semantics for the admittedly baroque:

scala> case class A(s: String); class B extends A("") { override val s = "B.s" }; A("B.s") == new B
class A
class B
val res1: Boolean = true

All that said, I do think it is worthwhile using this approach to reduce classfile size!

[harpocrates]

Thanks for trigging into the difference and sharing the process - this is very informative!

... I tried some of the workarounds. Both -XX:-TieredCompilation and adding MethodHandles.lookup().ensureInitialized(classOf[String]) or just "".length to the benchmark setup triggers resolution of java/lang/String in the classloader of the JITted method and brings the performance to parity

This is very reassuring and good to know. I'm going to rerun some of my other benchmarks while tracing the JITing that happens (ex: is the difference in hashCode performance coming from this too?).

The equals implementations used by JavaObjectMethods (ie java records) and ScalaObjectMethods don't run into this JIT corner case because they use GETFIELD. For java records this is fine because they are final; but case classes aren't final and can be overriden; using a GETFIELD has the wrong semantics for the admittedly baroque

Good point, although this is actually a feature of ScalaObjectMethods rather than a bug: if the case class is final, passing GETFIELD handles to the bootstrap method should be a fine. In the non-final case, you have to fallback to a regular INVOKEVIRTUAL handle to the getter method, but you can re-use the same bootstrap method. This is similar to how final case classes also omit the canEqual check from the code generated for equals.

All that said, I do think it is worthwhile using this approach to reduce classfile size!

Is there anywhere it would be safe to start working on something like this, or should I come back to this after Scala 3.0 is released and settled? Adding ScalaObjectMethods means changing the standard library, so that can't happen before 3.1. Still, I see no branch on either the Dotty or Scala repos tracking something like 3.1.

[smarter]

You can open a draft PR in the dotty repo and mark it as for 3.1.

[harpocrates]

I'd like to do this now.

I think I should be able to figure out the bootstrap method and the bytecode generation, but I'm a bit stuck around what to do around the AST and dotty architecture. The methods whose implementation I would like to turn into a single invokedynamic call (equals, hashCode, productElement, and maybe productElementName) get generated in SyntheticMembers, but they work by emitting Scala ASTs (not bytecode). This makes sense given that the JS backend will also need to know how to compile this, but it is definitely a problem since there's nothing like invokedynamic in the Tree type hierarchy. So far, the idea I've had is to introduce new subclasses of Tree like SyntheticEqualsImpl or SyntheticHashCodeImpl and then the different backends can generate code (with the default implementation being just to run codegen on the current output of SyntheticMembers). However, I'm also unsure if adding new subclasses to Tree is frowned upon or not...

@smarter do you have any advice/suggestions on the above?

[smarter]

Trees are tricky since they need to be copied/transformed. @sjrd can confirm but I think the usual way to have backend-specific behavior is to detect a particular code pattern in the backend itself, so perhaps you can just check for synthetic equals/hashCode methods in case classes

[sjrd]

Adding new kinds of trees is problematic, because they have to be handled by every other phase that sits in-between.

Detecting code patterns is possible, but unless it's based on very specific criteria (like recognizing that it is a case-class-generated equals method, through symbol information), it's very brittle.

Another possibility is to introduce primitive "magic" methods. Instead of generating special trees, you generate calls to those magic methods. Care must still be taken if their semantics cannot be expressed in regular Scala semantics, as intermediate phases may still break some assumptions. That seems to still be the most reliable technique, though. One example of such a magic method is withContextualJSClassValue (grep for it in the dotty repo).

[smarter]

Something else to keep in mind is that pattern matching has some subtlety and doesn't always correspond to exactly one instanceof check, for example in:

class Outer {
  case class Inner(x: Int)
}

The equals(x: Any) method in Inner checks both that x instanceof Inner and that the $outer fields in this and x are referentially equal.

[harpocrates]

@smarter I plan on diving deeper into making sure semantics are preserved, but only once I have a clearer picture on the how the compiler changes should work.

@sjrd I followed your suggestion and have a prototype that replaces the hashCode implementation with a single invokedynamic call - here's the commit.

...

  public int hashCode();
    Code:
       0: aload_0
       1: invokedynamic #66,  0             // InvokeDynamic #0:hashCode:(LFoo;)I
       6: ireturn
...
BootstrapMethods:
  0: #63 REF_invokeStatic scala/runtime/CaseClassMethods.bootstrap:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/Class;[Ljava/lang/invoke/MethodHandle;)Ljava/lang/invoke/ConstantCallSite;
    Method arguments:
      #2 Foo
      #55 REF_getField Foo.i:I
      #56 REF_getField Foo.s:Ljava/lang/String;

I'm still not sure what should be done for the JS backend. Is it a bad idea for SyntheticMembers itself to detect whether the JS backend is enabled and emit different trees depending on what it finds?

As for getting more feedback and help, at what point should I open a draft PR? I also seem to remember Gitter being used, but https://gitter.im/lampepfl/dotty pointed me to https://gitter.im/scala/contributors which is a 404. Is there any chat channel where I can ask small dotty questions?

[smarter]

at what point should I open a draft PR?

That can be done as early as you want.

Is there any chat channel where I can ask small dotty questions?

We've been experimenting with https://github.com/lampepfl/dotty/discussions for that purpose.

[SethTisue]

Is there any chat channel where I can ask small dotty questions?

There is a #scala-contributors channel on Discord (https://discord.com/invite/scala), but so far it hasn't been very common to see active Scala 3 maintainers answering questions there, so Guillaume's link is probably a better bet for specific technical questions. (You'll probably increase your hit rate if you mention that it's in the context of a PR you're working on, and not just a random free-floating question.)

[smarter]

We'd also need to handle the scala native backend which is trickier since it's just a plugin and therefore we don't have a built-in setting in the compiler to check if it's enabled, not sure how we should deal with that.

[harpocrates]

Maybe a flag to opt out of this (implied by SJS and manually enabled in the Native plugin)? I'm really not familiar with the Dotty compiler plugin interface...