Saturday, 31 January 2009

Mono 2.2 still leaks memory

We have previously discussed the fact that Mono is still built upon a conservative garbage collector (Boehm's GC). This means that Mono is not capable of identifying exactly what data is reachable and, consequently, has to resort to conservative guesses that can fail to deallocate garbage, i.e. leaking memory.

Boehm's own literature describes situations where the GC might be expected to leak (lazy lists and queues) but claims that no case has even been found in practice and they could not even construct a contrived example where memory was actually leaked. Readers of our previous posts have stated that our claims of memory leaks are "bogus". So we decided to put this issue to rest.

The following trivial F# program creates a cyclic list representing a queue, adds one element and then repeatedly adds one element and removes it again:

type 'a cell = { content: 'a; mutable next: 'a cell option }

let mutable tail = None
if tail = None then
let cell = { content = [||]; next = None } <- Some cell
tail <- Some cell
while true do
let tail' = Option.get tail
let cell = Some { content = [|1.;2.;3.;4.|]; next = tail'.next }
tail'.next <- cell
tail <- cell
let tail' = Option.get tail
tail'.next <- (Option.get tail'.next).next

This obviously requires only enough memory for at most two queue items, so any memory leaks will be obvious. Running this program on .NET, its memory consumption is steady at 11Mb. Running this program on Mono 2.2, the entire memory of the computer is leaked away in 60 seconds, the OS goes to swap and everything grinds to a halt.

We have also described situations where Mono 2.2 leaks stack space until the stack overflows. These results may be of interest to anyone else trying to find a usable VM to build upon.

Friday, 30 January 2009

Mono does not support tail call elimination

Tail call elimination is an essential feature for functional programming languages. This feature simply refers to the ability for one function to end with a function call without leaking stack space. Tail call elimination can be essential in heavily functional code such as parser combinators and libraries written in continuation passing style.

Lack of tail calls on the defacto-standard JVM has raised concerns around languages like Scala and Clojure. Fortunately, work is underway to address this issue by implementing tail call elimination on MLVM/OpenJDK.

Microsoft's .NET has had tail call elimination for eight years and the Mono project is designed to replicate the Common Language Infrastructure (CLI) that is responsible for this feature. The Mono team have been advertising tail call elimination on their VM for many years.

However, when we tested the elimination of tail calls on several VMs we discovered that tail calls are seriously broken on Mono but work on other VMs including .NET, LLVM and, of course, OCaml. Specifically, we ran the following trivial F# program that relies upon a tail call to a dynamic location, a function odd that is passed as an argument to the higher-order even function:

let even odd n = odd(n+1)

let odd n =
printf "%d\n" n
even odd (n+1)

let (_: int) =
even odd 0

This program prints odd integers indefinitely in OCaml or F# on .NET but attempting to run the executable generated by F# on Mono 2.2 results in a stack overflow almost immediately, as Mono leaks stack space until the stack is exhausted. So Mono cannot be relied upon to execute any functional programs correctly including F# programs.

This is of particular interest to us because several people have asked us for customer support when trying to run our F# code, such as the code from our book F# for Scientists, under Mono. Our advice is to steer well clear of Mono until it becomes stable and feature complete.

Interestingly, we also tried the same test on LLVM 2.2, writing the program in LLVM IR, and the tail calls are handled flawlessly provided the fast calling convention is used. As we have shown before, LLVM also generates vastly faster code than Mono 2.2.

Mono 2.2 vs OCaml vs .NET vs LLVM vs JDK

Mono 2.2 was recently shipped and a new JIT code generator was the main selling point promoted by the Mono project because it provides the first significant performance improvement Mono has seen for many years. We used the F# version of the SciMark2 benchmark to benchmark this new version of Mono against Mono 2.0 and some competing VMs using their native SciMark2 implementations:

The composite results show that the new code generator in Mono is indeed substantially better at producing code that is 40% faster on average than the previous code generator from Mono 2.0 according to these results. However, Mono 2.2 is still a long way behind its competitors. Specifically, both LLVM and Sun's JVM are over 2.2× faster than the latest version of Mono.

SciMark2 is composed of five different tests: Fast Fourier transform, successive over-relaxation, Monte Carlo, sparse matrix-vector multiply and LU matrix decomposition. We can get more detailed comparison of the VMs by looking at the individual scores on each of these five tests:

We can see immediately that the Monte Carlo test from the SciMark2 benchmark had anomalous results. Specifically, Mono 2.0 was 12× slower than LLVM and Mono 2.2 is now only 3× slower than LLVM. The Monte Carlo test is an int intensive random number generator.

These performance improvements in Mono are compelling but we are still deterred by some fundamental design flaws that undermine Mono's reliability.