F# code optimization or is it really that slow?

Question

I was looking for a way to do proper algorithmic coding using .NET with all the benefits of modern languages (e.g. I like a strong type checking, operator overloading, lambdas, generic algorithms). Usually I write my algorithms (mainly image prozessing) in C++. As F# as a language seems to be quite interesting I played a bit, but it seems to be very slow. As a most simple test I just did some array manipulation -> brightness increase of an image:

let r1 = rgbPixels |> Array.map (fun x -> x + byte(10) )

It seems to be a factor of at least 8 times slower than a compared C++ implementation - even worse for more complex algorithms e.g. 2D convolution. Is there some faster way or do I miss any specific compiler settings (yes, building release with optimization on...)? I'm willing to pay for the nice and high abstracion, but such an overhead is not nice (I would need to parallelize on 8 cores to compensate :) ) - at least it destroys the motivation to learn further... My other option would be to leave my heavier algos in C++ and interface with manged C++, but this is not nice, as mainting the managed wrapper would be quite a burden.

Answer 1

If you are worried about performance one of the important things to remember is that F# by default does not mutate anything. This requires copying in many naive implementations of algorithms, such as the one you described.

EDIT: I have no idea why, but simple tests of the following code provides inferior results to Array.map. Be sure to profile any algorithm you try when performing these kinds of optimizations. However I got very similar results between for and map.

Array.map creates a new array for the result of the operation, instead you want Array.iteri.

rgbPixels |> Array.iteri (fun i x -> rgbPixels.[i] <- x + 10uy)

Note that this could be wrapped up in your own module as below

module ArrayM =
    let map f a = a |> Array.iteri (fun i x -> a.[i] <- f x)

Unfortunately this is a necessary evil since one of the primary tenants of functional programming is to stick to immutable objects as much as your algorithm will allow, and then once finished, change to mutation where performance is critical. If you know your performance is critical from the get-go, you will need to start with these kinds of helpers.

Also note that there is probably a library out there that provides this functionality, I just don't know of it off hand.

Answer 2

I think that it's safe to say that idiomatic F# will often fail to match the performance of optimized C++ for array manipulation, for a few reasons:

1. Array accesses are checked against the bounds of the array in .NET to ensure memory safety. The CLR's JIT compiler is able to elide bounds checks for some stereotypical code, but this will typically require you to use a for loop with explicit bounds rather than more idiomatic F# constructs.
2. There is typically a slight amount of overhead to using abstractions like lambdas (e.g. fun i -> ...). In tight loops, this small overhead can end up being significant compared to the work that's being done in the loop body.
3. As far as I am aware, the CLR JIT compiler doesn't take advantage of SSE instructions to the same degree that C++ compilers are able to.

On the other side of the ledger,

1. You will never have a buffer overflow in F# code.
2. Your code will be easier to reason about. As a corollary, for a given level of total code complexity, you can often implement a more complex algorithm in F# than you can in C++.
3. If necessary you can write unidiomatic code which will run at closer to the speed of C++, and there are also facilities for interoperating with unsafe C++ code if you find that you need to write C++ to meet your performance requirements.