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:
