F# at the ICFP programming contest
Some weeks ago the International Conference on Functional Programming ran its annual programming contest. In this competition teams of any size from all over the Internet compete with each other to solve programming puzzles set by the contest organizers. Two small groups from MSR Cambridge entered on the spur of the moment, one of researchers and one of interns (and yes, the interns pipped the researchers in the final analysis!)
This year's task initially concerned writing an interpreter for a virtual machine. The specification of the virtual machine was very simple and was given as part of the problem definition. The interpreter implementation needed to be very fast as it was used to run a mini operating system which served as the basis for the rest of the contest. Many teams initially wrote their interpreters in their favourite functional or scripting language but found that they had to re-write it in C to gain the required performance.
F# is a high-level and functional language, so it's not surprising that it was excellent for the rapid design and prototyping of the interpreter. However, it also ran with excellent performance, sufficient that it is was not necessary to re-write the code in a "faster" language, and indeed the fully managed and verifiable F# implementation has a speed comparable to C implementations. The C implementations can perform faster pinned memory allocation, use native pointers in the interpreter’s state and avoid indirect and bounds-checked array access. Despite this, the F# implementation is only 10-15% slower than the fastest C implementations. The code for the F# interpreter is attached.
We looked at two performance optimizations using "unsafe" C-like techniques.
- A bottleneck in a managed CLR implementation is memory access via managed arrays. To interpret one memory access instruction in the interpreter requires two bounds-checked array lookups, whereas an unmanaged implementation can get away with an addition and a pointer dereference. To avoid the array bounds-checking we tried pinning allocated arrays and using unverifiable code to access the memory without bounds checks. This can be done very elegantly in F# simply by writing low-level code that directly uses CLR byte code via inline assembly blocks. Unverifiable byte-code will give the same memory access performance as C code. However the cost of allocating a pinned array on the CLR is so large that this approach halved the performance of the interpreter in the benchmark. So although the memory access performance improved, the memory allocation performance (which is another bottleneck for a managed CLR implementation) declined to such an extent as to produce a net decrease in performance.
- However, unverifiable memory access to a pinned array can still be used to improve memory access to the "registers" array in the interpreter as this array only needs to be pinned once at start-up. Also aligning elements in the registers array to 8-byte boundaries improves performance again. The code for an "unsafe" version of the F# implementation uses these optimizations through inline assembly block is also attached. It gives a performance gain of about 5%.
The whole issue of performance-impairing bounds checks could be completely and elegantly solved if the Microsoft .NET Framework 2.0 CLR implemented the no.rangecheck instruction prefix as documented in the ECMA specification, and this instruction could be immediately utilized from F# (see below). This prefix tells the JIT compiler to skip the bounds checking on an array access. So regular byte-code instructions for accessing an array can simply be marked with this prefix to eliminate the bounds-checking overhead. Of course the resulting code is still unverifiable but compared to the current approach: the array does not have to be pinned (avoiding bounds checking was the sole reason we needed to pin the arrays above) and array access code does not need to be re-factored to use a different instruction sequence. If this prefix were in the CLR then fast (albeit unsafe) array access could be implemented in F# simply by defining different array brackets, e.g.
let (.[]) (arr: 'a[]) (idx:int) = (# "no.rangecheck ldelem" arr idx : 'a #)
On the topic of memory allocation, the attached F# implementations use one CLR memory allocation for every memory allocation in the interpreted code. A more efficient scheme might be to allocate a single CLR array for the interpreter’s heap and "manage" that heap yourself. This would reduce the memory allocation performance overhead and remove one layer of indirection from memory access.
Finally, the very best C implementations reported so far used runtime code generation. We believe these results could be replicated very nicely using .NET Reflection.Emit or Lightweight code generation, though haven’t tried that.