5

I implemented a sequential version of the LCS algorithm in F#, and ran it against two strings of 100,000 characters each. It consistently took around 490 seconds to run to completion. I expected something closer to 70 seconds.

After a lot of troubleshooting, I tracked this down to my use of a custom max function - removing that reduced the run time to 42 seconds.

Can anyone tell me why using a custom max function has such a massive performance hit? In this instance it was 12x slower to use a custom max function over System.Math.Max Operators.max!

This is the function I was using:

let max (a:int) (b:int) : int = if a > b then a else b
Kane Armstrong
  • 106
  • 1
  • 4
  • 3
    Try adding `inline`. – ildjarn Apr 19 '16 at 07:15
  • 2
    @ildjarn Thanks! That answers my question. – Kane Armstrong Apr 19 '16 at 08:11
  • 4
    Why don't you use the operator 'max'? [Operators.max](https://msdn.microsoft.com/en-us/library/ee353702.aspx) [Example](https://dotnetfiddle.net/Qbk4l4) – FoggyFinder Apr 19 '16 at 08:54
  • 2
    @ildjarn: Why doesn't F# inline a function like this itself? – sshine Apr 19 '16 at 09:41
  • @FoggyFinder looks like I was mistaken as to which max function F# uses by default. Thanks for pointing this out. Now that I think about it, its pretty obvious given "max" vs "Max"! Operators.max is the one I switched to prior to asking the question, rather than Math.Max. – Kane Armstrong Apr 19 '16 at 11:41
  • I think this is essentially the same question as the one above - which has a couple of answers with more detailed explanations on how F# comparison is compiled. – Tomas Petricek Apr 19 '16 at 13:21
  • @TomasPetricek in this case the function is not generic though. Does inline change the performance characteristic of comparison even though the function is restricted to int? If so why? Thx. – s952163 Apr 19 '16 at 14:49
  • 1
    @s952163 : Because it is still inlined, avoiding the overhead of a function call... – ildjarn Apr 19 '16 at 18:54
  • @TomasPetricek Thanks Tomas - that is indeed a helpful answer. – Kane Armstrong Apr 19 '16 at 23:05
  • @SimonShine : That would be a very complex criteria to define... – ildjarn May 10 '16 at 14:38
  • @ildjarm: Are you saying it would be complex to define when it is possible or when it leads to an improvement? – sshine May 10 '16 at 14:45
  • @SimonShine : Both what constitutes an improvement, and when the implied possible change in semantics is actually desired. Both seem quite subjective to me. – ildjarn May 14 '16 at 12:44
  • @ildjarn: What change of semantics occurs when inlining functions? I was thinking of improvements in running time, as inlining necessarily takes up more space. Since the effects of inlining on instruction caches is non-trivial, I'm not proposing that writing inlining heuristics is obvious. – sshine May 14 '16 at 14:13
  • @SimonShine : Stack traces are lost for exceptions, type inference works differently (esp. for numeric types). – ildjarn May 15 '16 at 00:28

0 Answers0