The question is in two parts. The first is conceptual. The next looks at the same question more concretely in Scala.
- Does using only immutable data structures in a programming language make implementing certain algorithms/logic inherently more computationally expensive in practice? This draws to the fact that immutability is a core tenet of purely functional languages. Are there other factors that impact this?
- Let's take a more concrete example. Quicksort is generally taught and implemented using mutable operations on an in-memory data structure. How does one implement such a thing in a PURE functional way with a comparable computational and storage overhead to the mutable version. Specifically in Scala. I have included some crude benchmarks below.
More Details:
I come from an imperative programming background (C++, Java). I have been exploring functional programming, specifically Scala.
Some of the primary principles of pure functional programming:
- Functions are first class citizens.
- Functions do not have side effects and hence objects/data structures are immutable.
Even though modern JVMs are extremely efficient with object creation and garbage collection is very inexpensive for short lived objects, it's probably still better to minimize object creation right? At least in a single-threaded application where concurrency and locking is not an issue. Since Scala is a hybrid paradigm, one can choose to write imperative code with mutable objects if necessary. But, as someone who has spent a lot of years trying to reuse objects and minimize allocation. I would like a good understanding of the school of thought that would not even allow that.
As a specific case, I was a little surprised by this code snippet in this tutorial 6 . It has a Java version of Quicksort followed by a neat looking Scala implementation of the same.
Here is my attempt to benchmark the implementations. I haven't done detailed profiling. But, my guess is that the Scala version is slower because the number of objects allocated is linear (one per recursion call). Is there any way chance that tail call optimizations can come into play? If I am right, Scala supports tail call optimizations for self-recursive calls. So, it should only be helping it. I am using Scala 2.8.
Java version
public class QuickSortJ {
public static void sort(int[] xs) {
sort(xs, 0, xs.length -1 );
}
static void sort(int[] xs, int l, int r) {
if (r >= l) return;
int pivot = xs[l];
int a = l; int b = r;
while (a <= b){
while (xs[a] <= pivot) a++;
while (xs[b] > pivot) b--;
if (a < b) swap(xs, a, b);
}
sort(xs, l, b);
sort(xs, a, r);
}
static void swap(int[] arr, int i, int j) {
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
Scala version
object QuickSortS {
def sort(xs: Array[Int]): Array[Int] =
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
Scala Code to compare implementations
import java.util.Date
import scala.testing.Benchmark
class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {
val ints = new Array[Int](100000);
override def prefix = name
override def setUp = {
val ran = new java.util.Random(5);
for (i <- 0 to ints.length - 1)
ints(i) = ran.nextInt();
}
override def run = sortfn(ints)
}
val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " )
benchImmut.main( Array("5"))
benchMut.main( Array("5"))
Results
Time in milliseconds for five consecutive runs
Immutable/Functional/Scala 467 178 184 187 183
Mutable/Imperative/Java 51 14 12 12 12
