Performance-related features in F# and C#

Many people expect the performance of F# to be comparable to the performance of C# "because they both compile to the same intermediate language (CIL)". Although the VM obviously places the same ceiling on the performance of both F# and C# there are some features that affect performance differently between the two language implementations.

Firstly, C# and F# don't actually compile down to the same CIL because only F# generates tail calls. This affects performance when mutually recursive functions that represent the different states of a state machine tail call each other in order to move between states. This design pattern often appears in the context of asynchronous workflows that can tail call each other in F# but this will not even be possible with the new async support in C# 5.

Secondly, the implementation of delegates on .NET is currently quite inefficient and, consequently, F# uses its own FastFunc type for high-performance first-class functions.

Thirdly, F# uses .NET metadata to convey inline functions so that they can be exported across APIs and, of course, that can dramatically improve performance in certain circumstances. Moreover, F#'s inlining allows functions passed as arguments to higher-order functions to be completely inlined and type specialized. Our F# for Numerics library makes extensive use of this feature to ensure that per-type functions such as comparison are specialized, giving performance in F# up to 2,350× faster than the equivalent C# (!). In fact, some of our numerical routines are consistently several times faster than vendor-tuned Fortran in libraries like the Intel MKL.

Finally, pattern matching can be extremely laborious to express in C# because the language lacks pattern matching but it is almost impossible to maintain optimized C# code equivalent to many non-trivial pattern matches. In contrast, the F# compiler aggressively optimizes pattern matches during compilation.

Conversely, the C# compiler can be better at optimizing computations over value types (e.g. complex arithmetic).

Parsing mathematical expressions using active patterns

Active patterns allow arbitrary user-defined functions to be used to dissect values during pattern matching. This opens up some interesting possibilities with regard to parsing because it allows active patterns to be used to destructure streams of data when known patterns are encountered.

The following code sample creates several mutually-recursive active patterns that form a recursive descent parser for mathematical expressions:

> let rec (|Term|_|) = function
    | Factor(e1, t) ->
        let rec aux e1 = function
          | '+'::Factor(e2, t) -> aux (e1 + e2) t
          | '-'::Factor(e2, t) -> aux (e1 - e2) t
          | t -> Some(e1, t)
        aux e1 t
    | _ -> None
  and (|Factor|_|) = function
    | '-'::Factor(e, t) -> Some(-e, t)
    | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
    | Atom(e, t) -> Some(e, t)
    | _ -> None
  and (|Atom|_|) = function
    | c::t when '0'<=c && c<='9' -> Some(int(string c), t)
    | '('::Term(e, ')'::t) -> Some(e, t)
    | _ -> None;;
val ( |Term|_| ) : char list -> (int * char list) option
val ( |Factor|_| ) : char list -> (int * char list) option
val ( |Atom|_| ) : char list -> (int * char list) option

For example, the following parses the expression 1 + 2 × (3 - 4) × -5:

> let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
val e : int * char list = (11, [])

The F# programming language is descended from the MetaLanguages (ML) family that were specifically bred for metaprogramming including parsing. For more information on metaprogramming with F#, read the following articles in The F#.NET Journal:

• Parsing text with Lex and Yacc (30th September 2007).
• Optimizing a simple bytecode interpreter (31st October 2007).
• Parser combinators (30th November 2007).
• Language-oriented programming: The Term-level Interpreter (31st December 2007).
• Language-oriented programming: Term Rewriting (16th August 2008).
• Run-time code generation using System.Reflection.Emit (31st August 2008).
• Parsing and visualizing binary Geographic Information System data (30th November 2009).

Most popular F# samples

Here's a short-list of our most popular blog posts that describe example F# programs:

• Lorenz attractor.
• Sieve of Eratosthenes.
• Visualizing a complete graph.
• Parametric plots.
• Dragon curve.
• Bookworm challenge.
• Red-black trees.
• Anagrams.
• Mini hash table.
• Symbolic manipulation.
• Pythagoras tree.
• Morris sequences.
• Happy numbers.
• Java vs F#.
• F# vs Unmanaged C++ for parallel numerics.
• John Conway's Game of Life.
• Evolution: the weasel program.
• Foreign Function Interface (FFI).

Numerical methods: matrix inversion

The F#.NET Journal just published an article about numerical methods:

"Matrix inversion is one of the most important numerical methods with many practical applications. In practice, the numerical instability of matrix inverses leads to the use of linear solvers that effectively premultiply by the inverse of a matrix without having to explicitly compute the matrix inverse. This article disregards numerical accuracy in order to write the simplest possible function that computes the inverse of a matrix. The resulting function is just 8 lines of F# code and the remainder of the article is devoted to examining the generality and parallelization of this tiny function. We find that our tiny solution is up to 4.3× faster than Mathematica 7's built-in matrix inversion..."

To read this article and more, subscribe to The F#.NET Journal today!