Target audience: Intermediate
Estimated reading time: 3'
Recursion refers to the technique where a function invokes itself, either directly or indirectly, and such a function is termed a recursive function.
Some problems can be more effortlessly addressed using recursive algorithms. In this article, we will assess the performance of Scala's tail recursion in comparison to iterative approaches.
Overview
In Scala, the tail recursion is a commonly used technique to apply a transformation to the elements of a collection. The purpose of this post is to evaluate the performance degradation of the tail recursion comparatively to iterative based methods.For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted.
Test benchmark
Let's consider a "recursive" data transformation on an array using a sliding window. For the sake of simplicity, we create a simple polynomial transform on a array of values
{X0, ... ,Xn, ... Xp}
with a window w, defined as
f(Xn) = (n-1)Xn-1 + (n-2)Xn-2 + ... + (n-w)Xn-w.
Such algorithms are widely used in signal processing and technical analysis of financial markets (i.e. moving average, filters).
def polynomial(values: Array[Int]): Int =
(if(values.size < W_SIZE)
values
else
values.takeRight(W_SIZE)
).sum
The first implementation of the polynomial transform is a tail recursion on each element Xn of the array. The transform f compute f (values(cursor)) from the array values[0, ... , cursor-1] as describe in the code snippet below
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | class Evaluation(values: Array[Int]) {
def recurse(f: Array[Int] => Int): Array[Int] = {
@scala.annotation.tailrec
def recurse(
f: Array[Int] => Int,
cursor: Int,
results: Array[Int]): Boolean = {
if( cursor >= values.size) // exit condition
true
else {
val arr = f(values.slice(cursor+1, cursor-W_SIZE))
results.update(cursor, arr)
recurse(f, cursor+1, results)
}
}
val results = new Array[Int](values.size)
recurse(f, 0, results)
results
}
}
|
The second implementation relies on the scanLeft method that return a cumulative of transformed value f(Xn).
def scan(f: Array[Int] => Int): Array[Int] =
values.zipWithIndex.scanLeft(0)((sum, vn) =>
f(values.slice(vn._2+1, vn._2-W_SIZE))
)
Finally, we implement the polynomial transform on the sliding array window with a map method.
def map(f: Array[Int] => Int): Array[Int] =
values.zipWithIndex.map(vn => f(values.slice(vn._2+1, vn._2-W_SIZE)))
Performance evaluation
For the test, each of those 3 methods is executed 1000 on a dual core i7 with 8 Gbyte RAM and MacOS X Mountain Lion 10.8. The first test consists of executing the 3 methods and varying the size of the array from 10 to 90. The test is repeated 5 times and the duration is measured in milliseconds.
The tail recursion is significantly faster than the two other methods. The scan methods (scan, scanLeft, scanRight) have significant overhead that cannot be "amortized" over a small array. It is worth noticing that the performance of map and scan are similar. The relative performance of those 3 methods is confirmed while testing with large size array (from 1,000,000 to 9,000,000 items).
Thank you for reading this article. For more information ...
References
- Programming in Scala M. Odersky, L. Spoon, B. Venners - Artima 2010
- Scala for the Impatient - C. Horstman - Addison-Wesley - 2012
- Scala for Machine Learning - Patrick Nicolas - Packt Publishing
- github.com/patnicolas
---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning.
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3
