Is immutatble data always slower than mutable state? I was challenged in a discussion over at Reddit about this issue, and I decided to perform a little experiment to back up a rough estimate with some numbers. I was surprised and delighted to see that I could make my case very strong indeed by showing that no, immutable data can be twice as fast as mutable data in a modern functional language.
I concocted a trivial synthetic benchmark using simple records intended to emulate typical business entities:
module P0 = struct
type person = { name: string; age: int; balance: float }
end
module P1 = struct
type person = { name: string; mutable age: int; mutable balance: float }
end
let test0 =
let module E = struct
open P0
let rec test p iters =
if iters == 0 then p.balance else
test { p with balance = p.balance +. 1. } (iters - 1)
end in E.test { P0.name="John Doe"; P0.age=19; P0.balance=100.}
let test1 =
let module E = struct
open P1
let test p iters =
for i = 1 to iters do
p.balance <- p.balance +. 1.
done
end in E.test { P1.name="John Doe"; P1.age=19; P1.balance=100.}
The module P0 encapsulates an immutable business record; test0 is the attendant test that uses functional record updating and recursion in a classicaly pure idiom. The module P1, on the other hand, with its corresponding test test1 show the typical imperative use of a mutable record. The test and timing harness for both functions is simple enough:
let test times f iters =
let best = ref infinity in
for i = 1 to times do
let t = Sys.time () in
let _ = f iters in
let t = Sys.time () -. t in
if !best > t then
best := t
done;
float iters /. !best
let () =
let iters = 1_000_000 in
Printf.printf "Immutable record: %f updates/s\n"
(test 5 test0 iters);
Printf.printf "Mutable record: %f updates/s\n"
(test 5 test1 iters)
I tested this code with the OCaml bytecode compiler on a 1.6/2.0 GHz Intel Atom computer with Windows XP, and compiled with both the bytecode and native compilers, without optimization, on a 2.2 GHz Core2 Duo MacBook Pro computer with Mac OS X 10.5.7. The results are as follows:
| System | Immutable (upd/s) | Mutable (upd/s) | Speedup (Δ%) |
|---|---|---|---|
| 1.6 GHz Atom/Win XP/Bytecode | 3,048,780 | 3,558,719 | 16.73 |
| 2.0 GHz Atom/Win XP/Bytecode | 4,000,000 | 4,566,210 | 14.16 |
| 2.2 GHz Core2 Duo/Mac OS/Bytecode | 17,750,324 | 20,418,581 | 15.03 |
| 2.2 GHz Core2 Duo/Mac OS/Native | 128,882,588 | 58,400,981 | -54.69 |
The speedup afforded by imperative mutation in bytecode is modest, in all cases around 15%. On the other hand, the penalty incurred by mutation under the native compiler is more than double.
Of course, my correspondent was right in that the situation with current object-oriented languages is very different. I translated the benchmark straightforwardly into Java, and the result is what "common sense" would let us expect: Java is heavily oriented to mutation, or rather, it penalizes immutability quite heavily. I tried both client and server VMs, under the Windows environment detailed above:
| System | Immutable (upd/s) | Mutable (upd/s) | Speedup (×) |
|---|---|---|---|
| 1.6 GHz Atom/Win XP/Client | 22,831,050 | 107,526,882 | 4.71 |
| 1.6 GHz Atom/Win XP/Server | 37,735,849 | 322,580,645 | 8.55 |
The difference is dramatic: mutation is between 4.7 and 8.5 times faster than functional update in Java, and even twice as fast than native OCaml code on a faster machine. Moral of the story: test your assumptions with experiments. The benchmark code is:
public final class MutTest {
private static final class Person0 {
public final String name;
public final int age;
public final double balance;
public Person0(String name, int age, double balance) {
this.name = name;
this.age = age;
this.balance = balance;
}
public Person0 deposit(double amount) {
return new Person0(this.name, this.age, this.balance + amount);
}
}
private static final class Person1 {
public String name;
public int age;
public double balance;
public Person1(String name, int age, double balance) {
this.name = name;
this.age = age;
this.balance = balance;
}
public void deposit(double amount) {
this.balance += amount;
}
}
private interface Test {
double test(int iters);
}
private static final Test TEST0 = new Test() {
public double test(int iters) {
Person0 person = new Person0("John Doe", 19, 100.0);
for (int i = 0; i != iters; i++) {
person = person.deposit(1.0);
}
return person.balance;
}
};
private static final Test TEST1 = new Test() {
public double test(int iters) {
Person1 person = new Person1("John Doe", 19, 100.0);
for (int i = 0; i != iters; i++) {
person.deposit(1.0);
}
return person.balance;
}
};
private static double test(int times, Test test, int iters) {
long best = Long.MAX_VALUE;
double balance;
for (int i = 0; i != times; i++) {
long now = System.currentTimeMillis();
balance = test.test(iters);
now = System.currentTimeMillis() - now;
if (best > now)
best = now;
}
return (double) iters / ((double) best / 1000.0);
}
public static void main(String[] args) {
final int iters = 10000000;
System.out.printf("Immutable record: %f updates/s\n", test(5, TEST0, iters));
System.out.printf("Mutable record: %f updates/s\n", test(5, TEST1, iters));
}
}
