F# seems slower than other languages… what can I d

问题:

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)

回答1:

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).

回答2:

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.