c# - Why is this F# code so slow? -

a levenshtein implementation in c# , f#. c# version 10 times faster 2 strings of 1500 chars. c#: 69 ms, f# 867 ms. why? far can tell, exact same thing? doesn't matter if release or debug build.

edit: if comes here looking edit distance implementation, broken. working code here.

c#:

private static int min3(int a, int b, int c) {    return math.min(math.min(a, b), c); }  public static int editdistance(string m, string n) {    var d1 = new int[n.length];    (int x = 0; x < d1.length; x++) d1[x] = x;    var d0 = new int[n.length];    for(int = 1; < m.length; i++)    {       d0[0] = i;       var ui = m[i];       (int j = 1; j < n.length; j++ )       {          d0[j] = 1 + min3(d1[j], d0[j - 1], d1[j - 1] + (ui == n[j] ? -1 : 0));       }       array.copy(d0, d1, d1.length);    }    return d0[n.length - 1]; } 

f#:

let min3(a, b, c) = min (min b c)  let levenshtein (m:string) (n:string) =    let d1 = array.init n.length id    let d0 = array.create n.length 0    i=1 m.length-1       d0.[0] <-       let ui = m.[i]       j=1 n.length-1          d0.[j] <- 1 + min3(d1.[j], d0.[j-1], d1.[j-1] + if ui = n.[j] -1 else 0)       array.blit d0 0 d1 0 n.length    d0.[n.length-1] 

the problem min3 function compiled generic function uses generic comparison (i thought uses icomparable, more complicated - use structural comparison f# types , it's complex logic).

> let min3(a, b, c) = min (min b c);; val min3 : 'a * 'a * 'a -> 'a when 'a : comparison 

in c# version, function not generic (it takes int). can improve f# version adding type annotations (to same thing in c#):

let min3(a:int, b, c) = min (min b c) 

...or making min3 inline (in case, specialized int when used):

let inline min3(a, b, c) = min (min b c);; 

for random string str of length 300, following numbers:

> levenshtein str ("foo" + str);; real: 00:00:03.938, cpu: 00:00:03.900, gc gen0: 275, gen1: 1, gen2: 0 val : int = 3  > levenshtein_inlined str ("foo" + str);; real: 00:00:00.068, cpu: 00:00:00.078, gc gen0: 0, gen1: 0, gen2: 0 val : int = 3