Scala in the JVM Languages Summit Tuesday, Sep 30 2008 

Since I’ve seen no mention of this in Planet Scala (although it was discussed in #scala), here are some Scala-related links from the JVM Languages summit:

  • Optimizing Higher-Order Functions in Scala by Iulian Dragos. I haven’t tried the various optimisation flags in scalac yet, but I am curious if they will have any effect in the primitive collections with scala benchmark from a previous blog entry. These flags have been a bit buggy in the past, but hopefully recent fixes have solved the problems.
  • Scalify: Automatic translation from Java to Scala by Paul Phillips. This tool looks very interesting because the approach used is a lot more sophisticated than jatran. I have been meaning to take a look at it, but all of my code uses generics and it doesn’t support that yet.
  • Cliff Click’s post-Summit blog entry. It includes a link to the slides for his talk, “Fast Bytecodes for Funny Languages”. Scala is one of the languages covered (although very briefly) with the results coming from the translation of a simple Java micro-benchmark to Scala available here (in the comments). As expected, Scala can generate bytecode that is pretty much the same as Java if low-level constructs are used, but the performance suffers quite a bit if idiomatic Scala is used while dealing with primitives (at least with the default compilation flags).

For more general coverage of the summit:

Ricky Clarkson mentioned on IRC that videos of the talks will be made available on InfoQ and Google Video.

Update: John Rose’s post-summit blog entry is a nice round-up.

HotSpot JIT “Optimization” Saturday, Sep 27 2008 

I noticed Scala ticket #1377 the other day. Even though I think the bug is valid, it’s for different reasons to the ones supplied by the reporter. I had my doubts that the casts would have any measurable cost and the informal benchmark provided looked suspect. This is all described in the ticket, so I won’t go over it again here. The point of this blog is some weird behaviour I noticed in my version of the benchmark.

The benchmark looks like:

  def f(i: Iterator[_]) = i.hasNext

  def main(args: Array[String]) {
    test()
  }
    
  def test() {
    var i = 0
    while (i < 10) {
      val time = System.currentTimeMillis
      val result = inner()
      i += 1
      println("Time: " + (System.currentTimeMillis - time))
      println("Value: " + result)
    }
  }
    
  def inner() = {
    //val empty = Iterator.empty // checkcast occurs within loop
    val empty: Iterator&#91;_&#93; = Iterator.empty // checkcast outside loop
    var i = 0L
    while (i < 10000000000L) {
      f(empty)
      i += 1
    }
    i
  }
}
&#91;/sourcecode&#93;

According to this version of the benchmark the extra casts don't cause any performance difference, so I will just focus on the one without the extra casts. The results with JDK 6 Update 10 RC1 64-bit were:

<blockquote>
Time: 4903
Time: 4883
Time: 7213
Time: 7197
Time: 7203
Time: 7212
Time: 7185
Time: 7190
Time: 7210
Time: 7188
</blockquote>

That is odd. Instead of getting faster, the benchmark gets slower from the third iteration onwards. With JITs like these, we're better off with interpreters. ;) Ok, that's an exaggeration but let's investigate this further.

Before we do so, I should clarify two things. The ones paying attention might wonder where the "Value" output went. The purpose of that is just to make sure HotSpot does not optimize the inner loop away, so I trimmed it from the output. The second point is that the usage of a 64-bit JVM is important because the problem does not occur on the 32-bit version of HotSpot. I initially used the 64-bit version because it's much faster when performing operations on longs and I had to use a long index in the loop to allow the benchmark to take a reasonable amount of time.

Ok, so first step is to re-run the benchmark with -Xbatch and -XX:+PrintCompilation. The results of that were:

<blockquote>
  1   b   test.PerfTest$::f (7 bytes)
  2   b   scala.Iterator$$anon$5::hasNext (2 bytes)
  1%  b   test.PerfTest$::inner @ 12 (35 bytes)
Time: 4938
  3   b   test.PerfTest$::inner (35 bytes)
Time: 4861
Time: 7197
Time: 7199
Time: 7241

</blockquote>

Ok, so it seems like the inner loop got JIT'd a second time and that made it slower than the previous version, which sounds like a bug. I converted the code into Java and it turns out that we don't need much more than a loop in the inner method to reproduce the problem:


static long inner() {
  long i = 0L;
  for (; i < 10000000000L; ++i);
  return i;
}
&#91;/sourcecode&#93;

Before reporting the bug to Sun, I was curious if -XX:+UnlockDiagnosticVMOptions -XX:+LogCompilation would give any interesting information. I pasted some parts that someone that is not a HotSpot engineer might understand with the help of <a href="http://wikis.sun.com/display/HotSpotInternals/LogCompilation+overview">this</a>.


<nmethod compile_id='1' compile_kind='osr' compiler='C2' entry='0x000000002ee0d000' size='520' address='0x000000002ee0ced0' relocation_offset='264' code_offset='304' stub_offset='400' consts_offset='420' scopes_data_offset='424' scopes_pcs_offset='456' dependencies_offset='504' oops_offset='512' method='test/PerfTest inner ()J' bytes='19' count='1' backedge_count='14563' iicount='1' stamp='0.054'/>
<writer thread='12933456'/>
<task_queued compile_id='1' method='test/PerfTest inner ()J' bytes='19' count='2' backedge_count='5000' iicount='2' blocking='1' stamp='4.965' comment='count' hot_count='2'/>
<writer thread='43477328'/>
  1   b   test.PerfTest::inner (19 bytes)
<nmethod compile_id='1' compiler='C2' entry='0x000000002ee0d240' size='488' address='0x000000002ee0d110' relocation_offset='264' code_offset='304' stub_offset='368' consts_offset='388' scopes_data_offset='392' scopes_pcs_offset='424' dependencies_offset='472' oops_offset='480' method='test/PerfTest inner ()J' bytes='19' count='2' backedge_count='5000' iicount='2' stamp='4.966'/>
<...>

<task compile_id='1' compile_kind='osr' method='test/PerfTest inner ()J' bytes='19' count='1' backedge_count='14563' iicount='1' osr_bci='5' blocking='1' stamp='0.050'>
<...>
<task_done success='1' nmsize='120' count='1' backedge_count='14563' stamp='0.054'/>

<task compile_id='1' method='test/PerfTest inner ()J' bytes='19' count='2' backedge_count='5000' iicount='2' blocking='1' stamp='4.965'>
<...>
<task_done success='1' nmsize='88' count='2' backedge_count='5000' stamp='4.966'/>

So, it seems like the inner method was first JIT’d through on-stack-replacement (i.e. OSR). Usually, on-stack-replacement does not produce the best code, so HotSpot recompiles the method again once it gets the chance. Unfortunately, it generates slower code for some reason even though the compiled method size is smaller (88 instead of 120).

We could go deeper in this investigation by using a debug JVM like Kohsuke Kawaguchi did here, but I decided to just file a bug and let the HotSpot engineers handle it. :) I will update the blog once a bug number is assigned (I wonder when Sun is going to fix their bug database so that the bug id becomes available after submission of a bug…).

Update: The bug is now available in the Sun database.

Array variance and method overloading Sunday, Sep 21 2008 

One of these days I used jatran to translate the code for a simple Swing application from Java to Scala. Jatran’s translation had a few issues (some of which have been fixed since I tried it) so there were quite a few compiler errors after it finished. I fixed them and launched the application.

It was at this point that I noticed a change in behaviour and it was not clear why it was happening. After some investigation, it turned out that it was caused by the fact that variance of arrays in Scala is different from Java combined with poor usage of method overloading.

TreePath has two constructors that do different things, but one of them takes a supertype of the other:

public TreePath(Object[] path)
public TreePath(Object singlePath)

Because arrays are nonvariant in Scala, it means that scalac chooses the constructor that takes an Object for the following code:

def pathToRoot: Array[TreeNode] = ...
val treePath = new TreePath(pathToRoot)

On the other hand, arrays are covariant in Java so the constructor that takes an Object[] is chosen by javac for the equivalent Java code. One way to force scalac to choose the correct constructor is to cast the result of pathToRoot:

def pathToRoot: Array[TreeNode] = ...
val treePath = new TreePath(pathToRoot.asInstanceOf[Array[AnyRef]])

It’s a subtle issue that may affect other people automatically converting Java code to Scala, so I thought I’d bring it up in case it saves them some time. :)

Efficient Scala with Primitive Collections Monday, Sep 15 2008 

When dealing with large collections of primitives in Java/Scala, one can achieve substantial memory savings by using something like GNU Trove. Performance should also be better, but the difference may be small if the boxing does not happen in the performance-sensitive parts of the application. Using Trove is not as seamless as it should be because its collections don’t implement java.util interfaces (there are decorators, but they cause a lot of boxing defeating the purpose of using Trove in the first place). However, the advantages outweigh the disadvantages in some cases.

I wanted to use Trove collections from Scala conveniently without losing the efficiency benefits. Convenience in this case means the ability to pass anonymous functions to the usual suspects (i.e. map, flatMap, filter, etc.). One would ordinarily just write a wrapper, sprinkle some implicits and that would be it. Unfortunately, a naive wrapper will not meet the efficiency requirements.

Let’s start with the implementation that relies on an anonymous inner class to work out the baseline performance we’re aiming at. A simple implementation that serves the purpose is a method that sums all the elements of a TIntArrayList and returns it (preventing HotSpot from optimising it out).

  private def sumWithInnerClass(list: TIntArrayList): Int = {
    var sum = 0
    val p = new TIntProcedure() {
      def execute(i: Int) = {
        sum += i
        true
      }
    }
    list.forEach(p)
    sum
  }

This code is not much better than the Java equivalent (if at all), but it performs quite well. After a few iterations to allow the JVM to warm-up, it takes about 120ms to sum a list with 100 million items.

Let’s try a more convenient version of the code:

  implicit def toIntProcedureWithBoxing(f: Int => Unit): TIntProcedure = new TIntProcedure() {
    def execute(i: Int) = {
      f(i)
      true
    }
  }

  private def sumWithFunctionAndBoxing(list: TIntArrayList): Int = {
    var sum = 0
    list.forEach{x:Int => sum += x}
    sum
  }

We define an implicit from Int => Unit (which really means Function1[Int, Unit]) to a TIntProcedure and that allows us to pass an anonymous function to forEach. For the record, I am aware that a fold would have been a nicer way to define the sum (no need for the var), but I wanted to keep it similar to the initial version since I was interested in the performance difference caused by the wrapper. The results were certainly not encouraging, the boxing caused by calling Function1[Int, Unit] from TIntProcedure resulted in performance over 10 times worse: 1300ms on average.

That is not acceptable, so we need a way to avoid the boxing. Fortunately, the anonymous function for Function[Int, Unit] actually defines an apply(i: Int) method… but unfortunately we have no way to cast to the anonymous inner class generated by the Scala compiler, so we can’t invoke it. A possible solution is to generate traits like the following for the primitive types we care about and have the anonymous functions implement them when appropriate.

trait IntFunction[+R] extends Function1[Int, R] {
  def apply(i: Int): R
}

This gets more complicated once you consider that a function can take up to 22 parameters, but let’s for now assume that we only care about the case we use in our benchmark. I tried to think of ways to achieve this and it seemed like some compiler hacking was required. Given all my experience hacking compilers (read: none), I thought “why not?”.

To make my life easier, I decided not to read any documentation (not even sure if there’s any ;)) and settled for browsing and grep’ing the sources. Not too long after, I found what I was looking for, UncurryTransformer.tranform. After some analysis, it seemed like all that was needed was a conditional like:

        if (formals.head == IntClass.tpe && restpe == UnitClass.tpe) {
          anonClass setInfo ClassInfoType(
            List(ObjectClass.tpe, IntFunctionClass.tpe, fun.tpe, ScalaObjectClass.tpe), newScope, anonClass);
        }

Ok, I lie. I also defined IntFunctionClass in Definitions.scala. This is probably obvious, but I will mention it anyway, this is not a complete or general solution and it has a few limitations. However, it’s good enough to continue with the next part of the experiment. We can now define the following:

  implicit def toIntProcedure(f: Int => Unit): TIntProcedure = new TIntProcedure() {
    def execute(i: Int) = {
      f.asInstanceOf[IntFunction[_]](i)
      true
    }
  }
  
  private def sumWithFunction(list: TIntArrayList): Int = {
    var sum = 0
    list.forEach{x: Int => sum += x}
    sum
  }

We cast to IntFunction before calling apply, avoiding the boxing of the int. The performance for this was around 120ms to sum 100 million ints, which is about the same as the initial version. It seems like HotSpot does a very good job of inlining, so the additional indirection is basically free.

Ok, so the hack works. It’s relatively ugly, but at least the cast is encapsulated in the implicit converter and during normal usage, one does not have to deal with it. With more changes to the compiler, I believe it would be possible for Int => Unit to translate to IntFunction[Unit] or even IntUnitFunction instead of Function1[Int, Unit] and the cast would then not be needed. There are certainly some issues that would have to be worked out, but there are some nice performance benefits too.

It would solve issues like #1297 (where Range is 25 times slower than the while loop _after_ the fix) and mitigate #1338. It’s worth noting that work on scalar replacement through escape analysis in HotSpot and optimisation phases for the Scala compiler may reduce the amount of boxing that takes place, reducing the problem shown here. It’s unclear to what extent until we can try them out though.

The benchmark code can be found here. For my tests, I used JDK 6 Update 10 rc1 on an 8 core Mac Pro with the following options:

-XX:MaxPermSize=256m -Xms192m -Xmx2560m -server -XX:+UseConcMarkSweepGC

I think that’s enough for a first blog entry. Until next time. :)