Monday, November 7, 2011

Scala Pitfalls: Trait Bloat

Those of you following the active development of the Scala programming language may have noticed interesting Subversion commits today (r25962-25964) claiming to reduce the size of scala-library.jar by about 1.5MB. That's no small amount for a library that was creeping up on 9MB as of Scala 2.9.x, yet zero functionality was lost. So I bet you're wondering: how was this possible, and why is it important?

Friends of mine know that I've been really picking up on Scala lately because, as a person who comes from a very heavy imperative/object-oriented programming background, I find it to be a good hybrid language that offers both clean OO and functional programming constructs. Try as I might, I doubt I'll ever bring myself to appreciate the Lisp-derived languages, so when weighing Scala vs., for instance, Clojure, I found the superior OO support in Scala to be the aspect that put it over the top.

Couple Scala's strong points with a rich library of components via its Java interoperability, and it's a pretty slick language for rapid development while retaining the compile-time checks that developers don't get in fully dynamic languages such as Ruby or Groovy. It has become my language of choice for prototyping personal projects, and I've started to build up a pretty beefy personal utility library consisting of various types useful for projects I'm working on.

One aspect of Scala's OO concepts harkens back to my days of heavy C++ development. It's a feature that still triggers plenty of controversy today, confounds those new to programming, and comes with plenty of problems. In short, Scala supports multiple inheritance. (Sorry, no Wikipedia link for that term today; apparently, Wikimedia's copyright duplication detector found that most of the page was C&P'd from a published book.)

Scala's multiple inheritance can still be quite complicated if the programmer allows it to be. However, it comes with several restrictions courtesy of the JVM, and a few rules intended to reduce the impact of traditionally understood problems with the concept, most famously the diamond problem so well-known in C++ circles. I wouldn't call the problem "solved" by any means, but as I once got a well-known AOP advocate to admit publicly at JBoss World, lack of multiple inheritance has caused more pain than it has relieved in Java. (The person in question admitted that almost all of his uses for AspectJ involve mix-in composition, a euphemism for a trimmed-down version of multiple inheritance.)

In Scala, basic types consist of classes and traits. There are also singleton objects, but these are simply syntactic sugar for all the usual code that is usually necessary to provide singleton behavior, and they replace Java's static concepts for the most part.

A Scala class is a concrete implementation class. These are directly represented by Java classes, which form a single inheritance tree. Every instance of a Scala class must have only a single inheritance hierarchy of classes, but may inherit from any number of traits.

A Scala trait, on the other hand, is represented by a Java interface, which forms a multiple inheritance tree. The difference with Java interfaces is that a Scala trait can include implementation code. If not explicitly overridden, that code becomes the implementation in the first Scala class in the inheritance tree. Thus Scala traits are actually mix-ins, not pure interfaces. They cannot be directly instantiated; a class must inherit from a trait in order to make use of it.

So back to the over 15% drop in the scala-library.jar size. How did this happen, and what does it have to do with Scala's multiple inheritance?

The way that trait implementation code is handled in the Scala compiler — due to restrictions of the JVM — leads to class file bloat, reduced JIT optimization, and increased memory usage. Note that these problems are not specific to Scala; other methodologies such as AOP mix-in composition suffer from extremely similar problems. Since Java interfaces are not allowed to contain implementation code*, the Scala compiler performs a few tricks to make it happen.

Let's give a simple example without multiple inheritance to show what the Scala compiler does with it:
trait A {
  def foo: Int
  def bar = 2
  def baz = bar

class B extends A {
  override def foo = 1
  override def baz = 3
The compiler will create three, not two, class files from the above:
  • A.class
  • A$class.class
  • B.class
These class files contain the equivalent of the following Java code:
public interface A {
  int foo();
  int bar();
  int baz();

public final class A$class {
  public static int bar(A a) { return 2; }
  public static int baz(A a) { return; }

public class B implements A {
  public int foo() { return 1; }
  public int bar() { return A$; }
  public int baz() { return 3; }
Notice what it did there with the method? Since class B didn't override the trait's default implementation, the Scala compiler created a stub that defers the method to A$, which is the trait's code. For every case where a trait method is never overridden by the time a class inherits from it, a stub such as the one above is generated. C++ programmers will see some similarity to template instantiation here: the method's code doesn't actually exist until all the type resolution is complete.

The bytecode for is all of three opcodes:
invokespecial A$;)I
At first glance, this doesn't look like a large cost for using traits with implementation code, and it basically isn't. The Sun/Oracle JVM is even smart enough to see bytecode like this and eliminate it [almost] completely in the JIT compilation process. This isn't everything, though. Scala stores some metadata in the class file, for the benefit of compiling client code which has no access to the original source. In the case here, it's only a few bytes, but that size gets larger when parameterized type signatures are involved.

The combination of these farms of stub methods, which can resemble jump tables to those familiar with assembler code, with the extra data added for Scala type signatures caused the collection classes to bloat up significantly between 2.7.x and 2.9.x. Frankly, the collections inherited from too many traits with too many default implementations, resulting in things like an extra 40kB of uncompressed class file size for every incidence of this sort of code:
  ... = new Iterator[X] {
    def hasNext = ...
    def next = ...
...or the similar construct "extends Iterator[X]" on a named class. Iterator inherits from several traits with default implementations, and is itself a trait with many default implementations. So upon encountering the above construct, the compiler generates an anonymous concrete class with (as of 2.9.1) a whopping 102 stub methods. Yep, the collection classes are incredibly flexible because they are so method-rich, but that same method-rich nature can lead to unexpected compilation side effects.

Fortunately, there's an escape hatch. By deliberately triggering the stub method generation at a known point in the class inheritance chain, it's possible to reduce the number of generated stubs for every specialization needed throughout the library. This is done with a very simple construct: an abstract class that inherits from the commonly-specialized trait. For instance,
abstract class AbstractIterator[+A] extends Iterator[A]
This one line, added to Iterator.scala in the standard library, generates that 40k of stub code in a single, centralized place: an abstract class containing only the 102 stub methods. Then, in all the places where a specialization of Iterator is needed, a modification of the previous example changes simply to:
  ... = new AbstractIterator[X] {
    def hasNext = ...
    def next = ...
The result is that the above anonymous class, rather than clocking in at about 41kB, is now about 1kB. Wash, rinse, repeat throughout the standard library, and the total uncompressed size drops more than 3MB, resulting in a compressed jar file that is 1.5MB leaner. (See the diff for the actual changes involved.)

While I haven't been able to do meaningful benchmarks on the changed library code yet, my past experience with the Sun JIT suggests that this change will result in more efficient JIT usage and lower memory costs — since there's exactly one instance of each method to recompile, not many methods that defer to it — in addition to the reduction in class file size.

Not all the work is complete yet, either. I have some pending changes, more minor in scope, to apply this trick to other parts of the standard library. I'm expecting about another 300-400kB reduction in scala-library.jar when all is done.

And it doesn't end here. This optimization can be applied to your own code, too. If your codebase makes extensive use of specialized collection traits, or has its own "huge trait farm" issues, creating an abstract base class is a good optimization trick to use.

For Scala 2.10, the AbstractX classes are marked as private to the Scala library, since their presence is not a guaranteed part of the library (...yet?). But you can still create your own AbstractIterator (and so forth) classes just like above in your own packages, and you will gain the same benefits as the standard library by centralizing the generation of trait stubs by the Scala compiler.

Extra thanks go to Paul Phillips of Typesafe for some minor handholding as I grappled with building the Scala source, and temporary access to a beefy build machine where I could run "ant dist" dozens of times a day to make sure I didn't do something boneheaded.

(* JVM experts will note that Java interface class files actually can contain code, but only as part of the static initialization method <clinit>. This is how it's possible to put "constants" in Java interfaces with actual code on the right-hand side of the = sign.)


  1. Excellent work, Todd. Thanks for doing this. :)


  2. Renaming the Ghost classes from A$class to A$_ reduces 4 chars. Wont this approach help to reduce the jar file size?

  3. Ramesh,

    It would save 4 bytes per stub call in uncompressed class file size, but the difference is minimal once compression is added (thanks to the repeated string "$class"). The real savings comes from eliminating the stubs completely, which is what the big change does here.

  4. Wow, that's impressive, thanks for the work (and the post!)

  5. Java 8 adds default methods to interfaces. Scala might be able to take advantage of them to reduce this bloat. The VM dispatches them at runtime so you don't need the duplicated delegation methods.

    1. Yes. As a matter of fact, Scala 2.12 is working on using exactly this. Because of linearization, some synthetic methods are still required. (Where two traits define a method body, one has to "win" in an inheriting class/trait, and a small delegator method is required to make that happen.) But that's a *much* smaller impact.