title: Why is this F# code so slow?
body: <p>A Levenshtein implementation in C# and F#. The C# version is 10 times faster for two strings of about 1500 chars. C#: 69 ms, F# 867 ms. Why? As far as I can tell, they do the exact same thing? Doesn't matter if it is a Release or a Debug build. </p>
  
  <p>EDIT: If anyone comes here looking specifically for the Edit Distance implementation, it is broken. Working code is <a href="https://bitbucket.org/vgrit/clrsquirrel/src/82840c2ce95b/ClrSquirrel/ClrSquirrel.fs" rel="noreferrer">here</a>.</p>
  
  <p><strong>C#</strong>:</p>
  
  <pre class="lang-cs prettyprint-override"><code>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];
     for (int x = 0; x &lt; d1.Length; x++) d1[x] = x;
     var d0 = new int[n.Length];
     for(int i = 1; i &lt; m.Length; i++)
     {
        d0[0] = i;
        var ui = m[i];
        for (int j = 1; j &lt; 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];
  }
  </code></pre>
  
  <p><strong>F#</strong>:</p>
  
  <pre class="lang-ml prettyprint-override"><code>let min3(a, b, c) = min a (min b c)
  
  let levenshtein (m:string) (n:string) =
     let d1 = Array.init n.Length id
     let d0 = Array.create n.Length 0
     for i=1 to m.Length-1 do
        d0.[0] &lt;- i
        let ui = m.[i]
        for j=1 to n.Length-1 do
           d0.[j] &lt;- 1 + min3(d1.[j], d0.[j-1], d1.[j-1] + if ui = n.[j] then -1 else 0)
        Array.blit d0 0 d1 0 n.Length
     d0.[n.Length-1]
  </code></pre>