title: Analyzing slow performance of a Haskell program
body: <p>I was trying to solve <a href="http://www.itasoftware.com/careers/puzzle_archive.html" rel="nofollow noreferrer">ITA Software's "Word Nubmers" puzzle</a> using a brute force approach. It looks like my Haskell version is more than 10 times slower than a C#/C++ version.</p>
  
  <h2>The answer</h2>
  
  <p>Thanks to <a href="https://stackoverflow.com/questions/6970904/analyzing-slow-performance-of-a-haskell-program/6992417#6992417">Bryan O'Sullivan's answer</a>, I was able to "correct" my program to acceptable performance. You can read his code which is much cleaner than mine. I am going to outline the key points here.</p>
  
  <ul>
  <li><code>Int</code> is <code>Int64</code> on Linux GHC x64. Unless you <code>unsafeCoerce</code>, you should just use <code>Int</code>. This saves you from having to <code>fromIntegral</code>. Doing <code>Int64</code> on Windows 32-bit GHC is just <strong>darn</strong> slow, avoid it. (This is in fact not GHC's fault. As mentioned in my blog post below, 64 bit integers in 32-bit programs is slow in general (at least in Windows))</li>
  <li><code>-fllvm</code> or <code>-fvia-C</code> for performance.</li>
  <li>Prefer <code>quotRem</code> to <code>divMod</code>, <code>quotRem</code> already suffices. That gave me 20% speed up.</li>
  <li>In general, prefer <code>Data.Vector</code> to <code>Data.Array</code> as an "array"</li>
  <li>Use the wrapper-worker pattern liberally.</li>
  </ul>
  
  <p>The above points were enough to give me about 100% boost over my original version.</p>
  
  <p><a href="http://cfc.kizzx2.com/index.php/in-search-of-performance-in-haskell/" rel="nofollow noreferrer">In my blog post</a>, I have detailed a step-by-step illustrated example of how I turned the original program to match Bryan's program. There are other points mentioned there as well.</p>
  
  <h2>The original question</h2>
  
  <p>(This may sound like a "could you do the work for me" post, but I argue that such a concrete example would be very instructive since profiling Haskell performance is often seen as a myth)</p>
  
  <p>(As noted in the comments, I think I have misinterpreted the problem. But who cares, we can focus on performance in a different problem)</p>
  
  <p>Here's a my version of a quick recap of the problem:</p>
  
  <pre><code>A wordNumber is defined as
  
  wordNumber 1 = "one"
  wordNumber 2 = "onetwo"
  wordNumber 3 = "onethree"
  wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen"
  ...
  
  Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]'
  </code></pre>
  
  <p>From an imperative perspective, a naive algorithm would be to have 2 counters, one for sum of numbers and one for sum of lengths. Keep counting the length of each wordNumber and "break" to return the result.</p>
  
  <p>The imperative brute-force approach is implemented in C# here: <a href="http://ideone.com/JjCb3" rel="nofollow noreferrer">http://ideone.com/JjCb3</a>. It takes about 1.5 minutes to find the answer on my computer. There is also an <a href="http://ideone.com/vZGhh" rel="nofollow noreferrer">C++ implementation</a> that runs in 45 seconds on my computer.</p>
  
  <p>Then I implemented a brute-force Haskell version: <a href="http://ideone.com/ngfFq" rel="nofollow noreferrer">http://ideone.com/ngfFq</a>. It cannot finish the calculation in 5 minutes on my machine. (Irony: it's has more lines than the C# version)</p>
  
  <p>Here is the <code>-p</code> profile of the Haskell program: <a href="http://hpaste.org/49934" rel="nofollow noreferrer">http://hpaste.org/49934</a></p>
  
  <h2>Question: How to make it perform comparatively to the C# version? Are there obvious mistakes I am making?</h2>
  
  <p>(Note: I am fully aware that brute-forcing it is not the correct solution to this problem. I am mainly interested in making the Haskell version perform comparatively to the C# version. Right now it is at least 5x slower so obviously I am missing something obvious)</p>
  
  <p>(Note 2: It does not seem to be space leaking. The program runs with constant memory (about 2MB) on my computer)</p>
  
  <p>(Note 3: I am compiling with `ghc -O2 WordNumber.hs)</p>
  
  <p>To make the question more reader friendly, I include the "gist" of the two versions.</p>
  
  <pre><code>// C#
  long sumNum = 0;
  long sumLen = 0;
  
  long target = 51000000000;
  long i = 1;
  
  for (; i &lt; 999999999; i++)
  {
      // WordiLength(1)   = 3   "one"
      // WordiLength(101) = 13  "onehundredone"
      long newLength = sumLen + WordiLength(i);
      if (newLength &gt;= target)
          break;
  
      sumNum += i;
      sumLen = newLength;
  }
  Console.WriteLine(Wordify(i)[Convert.ToInt32(target - sumLen - 1)]);
  </code></pre>
  
  <p>-</p>
  
  <pre><code>-- Haskell
  -- This has become totally ugly during my squeeze for 
  -- performance
  
  -- Tail recursive
  -- n-th number (51000000000 in our problem) -&gt; accumulated result -&gt; list of 'zipped' left to try
  -- accumulated has the format (sum of numbers, current lengths of the whole chain, the current number)
  solve :: Int64 -&gt; (Int64, Int64, Int64) -&gt; [(Int64, Int64)] -&gt; (Int64, Int64, Int64)
  solve !n !acc@(!sumNum, !sumLen, !curr) ((!num, !len):xs)
      | sumLen' &gt;= n = (sumNum', sumLen, num)
      | otherwise = solve n (sumNum', sumLen', num) xs
      where
          sumNum' = sumNum + num
          sumLen' = sumLen + len
  
  -- wordLength 1   = 3    "one"
  -- wordLength 101 = 13   "onehundredone"
  wordLength :: Int64 -&gt; Int64
  -- wordLength = ...
  
  solution :: Int64 -&gt; (Int64, Char)
  solution !x =
      let (sumNum, sumLen, n) = solve x (0,0,1) (map (\n -&gt; (n, wordLength n)) [1..])
      in (sumNum, (wordify n) !! (fromIntegral $ x - sumLen - 1))
  </code></pre>