[Caml-list] Case study in optimization: porting a compiler from OCaml to F#

["Jon Harrop" <jon@ffconsultancy.com>]

There has been some discussion here about the implications of single- vs
multi-threaded garbage collectors and, in particular, their performance in
the context of the kinds of metaprogramming that OCaml has traditionally
been used for.

I recently ported a compiler written in OCaml to the F# programming language
for a client and performance turned out to be an issue so I'd like to
present this as a case study to provide some real data. Unfortunately I
cannot disclose precise details.

The original compiler was 15kLOC of OCaml code. The amounts of DSL code that
it consumes and C code that it produces can be considerable and compilation
can take minutes. Consequently, performance is valued by my client's
customers and, therefore, the original code had been optimized for OCaml's
performance characteristics.

A direct translation of the OCaml code to F# proved to be over 10x slower.
This was so slow that it impeded testing my translation so I did some
optimization early. Specifically, profiling indicated that the biggest
problem was the high rate of exceptions being raised and caught. Exceptions
are around 600x slower on .NET than in OCaml so this can quickly degrade
performance. I changed all of the hot paths to use union types (usually
option types) instead of exceptions, according to F# idioms. Although this
incurs a lot of unnecessary boxing in F# the performance improvements were
substantial and the F# version became 5x slower than the OCaml.

On a related note, thorough testing showed that my almost-blind translation
of 15kLOC of code was completely error free. I think this is a real
testament to the power of ML's static type system. The only error I have
introduced so far occurred when I was replacing the use of an exception in a
function with a union type.

After demonstrating the correctness of the translation, my effort turned to
trying to improve performance in an attempt to compete with the original
OCaml code. I had believed that this could well prove to be prohibitively
difficult or even impossible because symbolic code is OCaml's main strength.
However, I have managed to make the F# around 8x faster than it was and, in
particular, substantially faster than the original OCaml.

So this non-trivial symbolic code base has not had its performance suffer
from the adoption of a multicore-friendly garbage collector.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com