Mark's IT Blog

The scala compiler has partial tail call optimization (http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html).

Running some like methods with and without allowing the scala compiler to optimize demonstrated the performance improvements gained by this optimization.

First up, simple factoral functions (source: http://myadventuresincoding.wordpress.com/2010/06/20/tail-recursion-in-scala-a-simple-example/):

//this function will be tail recusive optimized
def tFactorial(number: Long) : Long = {
 def tfactorialWithAccumulator(accumulator: Long, number: Long) : Long = {
 if (number == 1) 
 return accumulator
 else
 tfactorialWithAccumulator(accumulator * number, number - 1)
 }
 tfactorialWithAccumulator(1, number)
}

//Non-tail recursive function
def ntFactorial(number:Long) : Long = {
 if (number == 1)
 return 1
 number * ntFactorial (number - 1)
}

For explanation of these functions and why/not they are tail recursive see the source above.

Results:

Non-Tail recursive average response time: approx 7 ms

Tail recursive average response time: approx 0.7ms

The number of test conducted was limited to about 10 each and the test environment was an Ubuntu VM. The results will not be highly accurate but with a difference this significant it is clear that tail optimized recursion is very different from normal recursion (On a JVM). Looking at the purepath for each method reveals tail-recursion optimization working as expected and saving alot of execution time:

The next example looks at what the compiler does if there is extra code within a tail optimized funtion:

// Tail recursive version 
 def execTest3Tail(loopCount: Int): String = {
 def test2WithAccumulator(accumulator: Int, number: Int): String = {
 println("Hello World " + accumulator + "\n")
 if (accumulator >= loopCount)
 return "Completed"
 else
 test2WithAccumulator(loopCount, (accumulator + 1))
 }
 test2WithAccumulator(1, loopCount)
 }

// Non-Tail recursive version
 def execTest3nt(loopCount: Int, cur: Int): String = {
 println("Hello World " + cur + "\n") 
 if (cur >= loopCount)
 return "Completed"
 else
 execTest3nt(loopCount, (cur + 1))
 }

The output of the non-tail recursive function was as expected, printing all of the output expected. The scala compiler optimized over the expected (perhaps incorrectly expected) behaviour of the optimized function. The output was:

enter num of iterations:1000
Hello World 1

Hello World 1000

Completed

As the function was optimized not to run through all of the loops – the println’s simply did not occur. The purepath comparision:

 

After some initial JVM monitoring yesterday, I looked at response times today. First thing I had to do was modify the respective classes slightly to get a non-constructor method doing all the work. This made it much easier to gather and chart the results within dynaTrace (though I did later find that there was a check box in dynaTrace to monitor constructors).

The tests today were again on 3 implementations of the Fibonacci sequence:

Java – see source

Scala Simple – see source

Scala Advanced – see source

Test environment info

I spent most of the day playing with dynaTraces monitoring and reporting tools so did not actually do that much testing. The tests I did run where quite short. The first being execution of the fib sequence returning the 10,000 value, the second stretching to 100,000. The charts below show the time results for each test, if more than one test was executed for an implementation in a 30 second cycle, the chart shows the average.

*Update 16-JUL: Retested on host machine (not running in VM) results where much more consistent despite having a number of other services operating at the same time. There are some clear results this time:

 

From the results it appears that the variations in response times are most likely caused by external factors (ie: OS or other services taking resouces, Garbage collections etc). I will really need to increase the sample size to get a better understanding of what is influencing response times.

Trying to make some comparisons between Scala and Java. Using dynaTrace I can get very useful and granular insight into the behaviours of each.  To keep things as comparable as possible the tests will be on simple, short algorithms. Large iterations will be conducted so garbage collection and space complexity can be analysed.

Thanks to Julio Faerman for his post and the implementations I have used from that post – see: http://www.infoq.com/articles/scala-java-myths-facts

With dynaTrace I can get information about the JVM behaviour but also about the behaviour of specific classes and methods. This will not only allow me to make some comparison between Java and Scala implementations but also understand more about what happens when Scala is compiled to byte code.

To start with, nice and simple test – Fibonacci sequence

Three implementations will be tested:

Java Fibonacci  – see code

Scala Simple Fibonacci  – see code

Scala Advanced Fibonacci  – see code

I am running the tests from a controller class with a main method. From there I can instantiate the classes above. Read more about dynaTrace to see how it uses sensors in the JVM to grab a great deal of useful data about the JVM and about classes and methods.

Just to get things rolling, checked out how running the Fib sequence to the 10 million number in the sequence would affect the JVM.  This tests would have taken a long time to complete so after I saw stable behaviour (ie: two sequences) I kill the JVM and moved on to the next sequence. 

The charts below have been modified for human readability. For example, Garbage Collection in the charts was factored up. The charts are also stacked for readability. Within the dynaTrace client this is much easier to read with mouse over pop-ups.

What can be taken from this fairly simple example is that code may work and appear to be performing well. In reality it may be wreaking havoc on the JVM. Next post will look at the response times of these implementations.

 

Test details:

Environment:

Virtual Machine: Ubuntu 12.04 LTS 32 bit - 3072MB, 2 Processors

Physical Host: Windows 7 64-bit - 8GB, i7-2620M @ 2.70 GHz

Versions:

java version "1.6.0_24"
OpenJDK Runtime Environment (IcedTea6 1.11.1) (6b24-1.11.1-4ubuntu3)
OpenJDK Server VM (build 20.0-b12, mixed mode)

Scala compiler version 2.9.2

Run script:

#!/bin/bash
scala_path=/usr/share/java/scala-library.jar
java -Xmx2048m -cp $scala_path:. -agentpath:/home/mark/Desktop/performance_testing/dynatrace/agent/lib/libdtagent.so=name=TestJVM_scala_vs_java,server=192.168.242.60:9998 PerformanceController