A recurring claim is that OOP languages, in general, are faster than FP languages – or specific to .Net, C# is faster than F#. So today, we take a look at the myth about F# being slow.
Functional-programming patterns considered slow
A couple of patterns used frequently in F# – or functional programming in general – are considered slow: recursion, lists (the singly linked list being the default in F#), and immutability (always creating new values instead of mutating existing variables).
But is this actually true? The answer is it depends on how you use them.
Recursion can be fast if it is tail-recursion, and the compiler translates it into a loop for you.
(Singly linked) lists are very fast when you only add elements at the head but slow for everything else. Even enumerating elements in an F# list is slower compared to enumerating a C# List (ResizeArray as it is called in F#). But F# lists are great when you use parallelism because they are immutable (not just read-only).
Immutability and the resulting need for creating new values for every change – compared to mutating existing variables – add pressure on the garbage collector. The garbage collector has to run more frequently, using maybe scarce resources. But again, immutability is great for parallel computing, which may save execution time.
Object-oriented programming patterns can also be slow
In a typical OOP design, there are quite some virtual method calls (virtual methods and interface calls). When these calls cannot be de-virtualized by the compiler, the call is rather expensive because of the additional v-table lookup and the fact that virtual methods cannot be inlined.
Distributing state over many objects can also result in inefficient algorithms and pressure on the garbage collector.
A word about LINQ
LINQ expressions in C# suffer from both many virtual calls and creating many new values. So it remains rather slow despite the many improvements over the different versions of the .Net framework.
But I need speeeeeeeeeeeeeeeeeeeeeed!
So when execution speed matters, FP patterns can be problematic when not taking good care to ensure that the easier parallelization outweighs the downsides of immutable data structures and that recursion is tail-recursive. And OOP patterns suffer from virtual calls and memory layout (state in many objects).
Luckily, in both C# and F#, we can fall back to using imperative code: simple loops, mutable variables, and many, many arrays and structs for efficient storage access and layout. And if we keep this code local to a function or method, it does not lower overall code simplicity.
If you don’t believe me that imperative code in F# is really fast, then head over to Matthew’s Fast F# channel.
But I need even more speed!!
What you can accomplish with C# or F# is limited by the .Net runtime. If you need even faster speed, then you probably have to look at another runtime. And be aware that you can call other runtimes from .Net, so maybe you can call algorithms running outside of .Net from your .Net code (P/Invoke).
Conclusions
IMHO, both C# and F# are more than fast enough for a typical business application. Sometimes, when speed is important, we can use an imperative style to get the execution time down. And the .Net platform has seen impressive performance improvements over the last few years.
For most teams, development speed is generally more important than execution speed.
Me 🙂
One reason why we chose F# is that we are developing our product faster with F# than C#.
As a final thought: before you optimize your code, please measure the execution time and see whether you improved the code – or just confused the compiler so that it cannot do its optimizations anymore.
Some links for further reading and watching:
