F# relies on slow .NET features

I reported earlier that the N-Queens problem on F# was too slow. I translated the benchmark in C# and it ran 2X faster than F#. It was essentially the same program… lots of recursion and list processing. So how can F# be 2X slower than C# for the same code? One simple instruction: isinst. I learned long ago that type checking on the CLR is too slow for dynamic languages. Though F# is statically typed, it still performs type checking on discriminated union types. Specifically, operations on lists must always check if the list is null. F# does this by checking if the object is a Nil class: “obj is Nil” in C#. Type checking is extremely slow and should be avoided whenever possible in hotspots. List processing is definitely a hot spot.

When I rewrote the N-Queens problem I used my own list class which used null to represent Nil. Checking “obj == null” is extremely fast. I then modified my list to use a Nil class and performance dropped down to F# speed. The solution I used with my Scheme compiler was to use null to represent the end of the list. An alternative is skip the nil check and wrap the list access in a try-catch. It only fails in the exceptional situation anyway, since properly written code will check for nil before it calls hd. This should speed up list performance dramatically.

Advertisements

4 comments

  1. Jon Harrop

    Without seeing your code it is difficult to say but F#’s lists are designed for genericity and not efficiency.

    Also, .NET exceptions are incredibly slow so you’re highly unlikely to be able to use them to optimize code. In general, you must avoid them at all costs in performance critical code.

    Note that this is in stark contrast to other functional programming languages like OCaml, where lists are ~5x faster and exceptions are ~600x faster than in F#.

    If you want your F# code to run fast then you must write it like an efficient C# program. In this case, that probably means using a mutable stack and not lists or exceptions.

  2. Don Syme

    Hi Pinku,

    If you do want to use “null” as a representation for your empty lists, you can define your own list type as follows:

    [<CompilationRepresentation(CompilationRepresentationFlags.PermitNull)>]
    type MyList =
    | Nil
    | Cons of ‘a * MyList

    Original versions of F# used “null” as a representation for the empty list. However, this choice is not a good one for the default list type in the language. This is primarily because it means the “list” type can’t implement the “IEnumerable” interface. This is deeply confusing to users: imagine the bewilderment that appears on the face of any .NET programmer if you try to tell them that “F# lists are not IEnumerable”.

    After much discussion about the pros and cons of a 4% performance drop for some benchmarks, we decided that F# lists would be for generality, and not for optimal Scheme-like programming. Basically, we made a choice that the small drop in efficiency that comes from using a non-null representation for lists is worth the simplicity that choice brings to programming.

    Kind regards
    Don

  3. Steven Burns

    I would have been happy with F#’s lists not being IEnumerable as long as I had a method that returned a proxy class that was IEnumerable.
    F# compiler could be smart about handling list’s as sequences and for interoperability I would have relied on a proxy class.
    But, that’s just my two cents and I’m sure your analysis was deeper than anything I could be thinking from the top of my head at 11pm on a given Tuesday.
    I just regret that lists became slower because they are the most commonly used structure in pretty much all the F# you see around.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s