29

I like F# ; I really, really do. Having been bitten by the "functional programming"-bug, I force myself to use it when I have the opportunity to. In fact, I recently used it (during a one week vacation) to code a nice AI algorithm.

However, my attempts so far (see a SO question related to my first attempt here) seem to indicate that, though undoubtedly beautiful... F# has the slowest execution speed of all the languages I've used.

Am I doing something wrong in my code?

I verbosely explain what I did in my blog post, and in my experiments, I see OCaml and the rest of the group running anywhere from 5x to 35x faster than F#.

Am I the only one with such experiences? I find it disheartening that the language I like the most, is also the slowest one - sometimes by far...

EDIT: Direct GitHub link, where the code lives in various language forms...

EDIT2: Thanks to Thomas and Daniel, speed improved considerably:

  • Greatest speed boost: moving from "ref" to "mutable" gave a whopping 30%.
  • Removing exceptions and using while/flagChecks gave another 16%.
  • Switching from discriminated unions to enums gave another 5%.
  • "inline" gave 0.5-1%

EDIT3: Dr Jon Harrop joined the fight: 60% speedup, by making ScoreBoard operate directly on the "enumerated" version of the data. The imperative version of F# now runs 3-4 times slower than C++, which is a good result for a VM-based runtime. I consider the problem solved - thanks guys!

EDIT4: After merging all optimizations, these are the results (F# reached C# in imperative style - now if only I could do something about functional style, too!)

  • real 0m0.221s: That was C++
  • real 0m0.676s: That was C# (imperative, C++ mirror)
  • real 0m0.704s: That was F# (imperative, C++ mirror)
  • real 0m0.753s: That was OCaml (imperative, C++ mirror)
  • real 0m0.989s: That was OCaml (functional)
  • real 0m1.064s: That was Java (imperative)
  • real 0m1.955s: That was F# (functional)
14
  • I think your question is a good one but needs a more positive question-like title. Maybe something like "F# seems slower than other languages. How can I speed it up?"
    – Zan Lynx
    Jul 22, 2011 at 18:03
  • I agree with @Zan. Your question seems to be a rant in its current state. Jul 22, 2011 at 18:06
  • 6
    I think that the question still feels more like a rant. You reference a blog post, but it's unlikely that someone would read a long post in order to answer your question. Could you refine the question and find one particular piece of code that is slower in F# and that is short enough to fit into a question? Jul 22, 2011 at 18:19
  • 1
    @ttsiodras - Well, how did Jon Harrop find the solution in the first case? I assume he bechmarked the program and found the bottle-neck. Then he replaced the slow part with something faster. To ask a question, you need either a reasonably sized code sample (that someone can benchmark) or know what the bottle-neck is (so that someone can advise on more efficient approach). Jul 22, 2011 at 18:59
  • 1
    @ttsiodras: Your C++ code uses the board array in-place whereas your F# implementation copies it unnecessarily in the inner loop. You are also using arrays like [|(0,0); (1,1); (2,2); (3,3)|] that are obviously pointless. Fixing these obvious discrepancies immediately makes the F# almost 2× faster than before.
    – J D
    Jul 23, 2011 at 11:24

2 Answers 2

17

Unless you can give a reasonably sized code sample, it's difficult to tell. Anyway, the imperative F# version should be as efficient as the imperative C# version. I think one approach is to benchmark the two to see what is causing the difference (then someone can help with making that bit faster).

I briefly looked at your code and here are some assorted (untested) suggestions.

  • You can replace discriminated union Cell with an enum (this means you'll use value types and integer comparison instead of reference types and runtime type tests):

    type Cell =    
      | Orange = 1
      | Yellow = 2
      | Barren = 3
    
  • You can mark some trivial functions as inline. For example:

    let inline myincr (arr:int array) idx =
      arr.[idx] <- arr.[idx] + 1
    
  • Don't use exceptions for control-flow. This is often done in OCaml, but .NET exceptions are slow and should be only used for exceptions. You can replace the for loop in your sample with a while loop and a mutable flag or with a tail-recursive function (a tail-recursive function is compiled into a loop, so it will be efficient, even in imperative solution).

4
  • Tried the discriminated to enum: it gave a 5% speedup. Unexpected, thanks! Inlining didn't seem to help in any place I tried it... Will try removing the exception and report back.
    – ttsiodras
    Jul 22, 2011 at 19:29
  • Removing exceptions improved speed by another 16%. Imperative F# is now 60% slower than C#. Anything else I can try?
    – ttsiodras
    Jul 22, 2011 at 19:45
  • Following a suggestion from @Daniel thru chat, I moved from using "ref" to using "mutable" - and got another 10%. I am feeling positively hopeful - anything else, guys?
    – ttsiodras
    Jul 22, 2011 at 19:55
  • I was wrong - the speedup was in fact 30% when I moved from "ref" to "mutable" (already commited on GitHub). Wow, imperative F# is now at only 25% distance from C#... I consider it good enough.
    – ttsiodras
    Jul 22, 2011 at 20:04
12

This isn't an answer, per se, but have you tried writing the exact same code in F# and C#, i.e., imperative F# code? The speed should be similar. If you're comparing terse functional code with heavy use of higher-order functions, sequence expressions, lazy values, complex pattern matching, etc.--all things that allow for shorter, clearer (read, more maintainable) code--well, there is frequently a trade-off. Generally, development/maintenance time is much greater than execution time, so it's usually considered a desirable trade-off.

Some references:
F# and C# 's CLR is same then why is F# faster than C#
C# / F# Performance comparison
https://stackoverflow.com/questions/142985/is-a-program-f-any-more-efficient-execution-wise-than-c

Another point to consider: in a functional language you're working at a higher level and it becomes very easy to overlook the costs of operations. For example, Seq.sort seems innocent enough, but naive use of it can doom performance. I'd recommend poring over your code, asking yourself along the way if you understand the cost of each operation. If you're not feeling reflective, a faster way to do this is, of course, with a profiler.

10
  • Actually, I did - if you go to my "Moving to imperative style" section in the blog post, you'll see that once I coded in C# (and got a 2x over F#) I re-wrote in imperative style for both OCaml and F#. F# remained well behind C# (6 seconds vs 3 seconds, a 2x). Not to mention that OCaml had 1.4 and C++ had 0.2 seconds...
    – ttsiodras
    Jul 22, 2011 at 18:40
  • I'd like to see your imperative F# code. There's no reason it should perform much different than C#.
    – Daniel
    Jul 22, 2011 at 18:44
  • By all means - as said in the blog post, the code lives in GitHub: github.com/ttsiodras/Score4/tree/master - navigate in the F# folder, it contains both the imperative and functional solutions.
    – ttsiodras
    Jul 22, 2011 at 18:48
  • 2
    Sorry, I guess I'm lazy, I'm not reading a long blog post. ;-) Thanks for the link.
    – Daniel
    Jul 22, 2011 at 18:48
  • 4
    @ttsiodras: Cool. I'd still recommend profiling until it's on par with C#. There must be a reason for the difference. Here is a free one.
    – Daniel
    Jul 22, 2011 at 20:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.