Hi all,<br><br>Thanks Bryan, reading your clean code was good for my Haskell health :)<br><br>I took your code and did some more research. I think I have found the answer. I have written an extensive analysis in my blog post <a href="http://cfc.kizzx2.com/index.php/in-search-of-performance-in-haskell/">http://cfc.kizzx2.com/index.php/in-search-of-performance-in-haskell/</a> (comments are very much welcome, btw :)<br>
<br>Here are summaries of key points:<br><br>- I was using GHC 32-bit. Int is 32-bit there, so I needed Int64. It turns out 64-bit operations in 32-bit programs are just darn slow. Maybe it's a Windows problem. On Linux 64 bit GHC Int is 64 bit so everything just works. Changing Int64 to Int liberates me from many `fromIntegral` which saved 20%<br>
- Changing `divMod` to `quotRem` saved another 20%<br>- Using `Data.Vector.Unboxed` and `unsafeIndex` saved another 15% or so<br>- Moving the "length" arrays to `where` clause in `solve` with bang patterns on them save some more.<br>
<br>This was a great learning experience! Now I have more questions :P<br><br>1. Why are bangs needed on the length arrays?<br><br>If I remove them from below, performance drops 10%. I thought `unsafeIndex` is straight in both arguments, no?<br>
<br>wordLength i = go i<br> where<br> go n<br> | n < 10 = lengthOnes !! n<br> | n < 20 = lengthTeens !! (n-10)<br> | n < 100 = (lengthTens !! (n // 10)) + (lengthOnes !! (n % 10))<br> | n < 1000 = (lengthOnes !! (n // 100)) + 7 + go (n % 100)<br>
| n < 1000000 = go (n // 1000) + 8 + go (n % 1000)<br> | otherwise = go (n // 1000000) + 7 + go (n % 1000000)<br> !lengthOnes = lengthVec ones<br> !lengthTens = lengthVec tens<br> !lengthTeens = lengthVec teens<br>
<br>2. Why the single element worker wrapper pattern (`go` functions) increases performance?<br><br>If we change wordLength to <br><br>wordLength n<br> | n < 10 = lengthOnes !! n<br> | n < 20 = lengthTeens !! (n-10)<br>
| n < 100 = (lengthTens !! (n // 10)) + (lengthOnes !! (n % 10))<br> | n < 1000 = (lengthOnes !! (n // 100)) + 7 + wordLength (n % 100)<br> | n < 1000000 = wordLength (n // 1000) + 8 + wordLength (n % 1000)<br>
| otherwise = wordLength (n // 1000000) + 7 + wordLength (n % 1000000)<br> where<br> !lengthOnes = lengthVec ones<br> !lengthTens = lengthVec tens<br> !lengthTeens = lengthVec teens<br><br>The performance drops by another 10%. This really surprised me. `go i` seemed obvious to me and I don't understand how it could make any difference. The full source code is available to GHC so it shouldn't be related to call-by-pointer problem? If this is the case, shouldn't we always wrap a "go" function for **any** recursive functions?<br>
<br>Thanks!<br>
<br>Chris<br><br><div class="gmail_quote">On Tue, Aug 9, 2011 at 9:09 AM, Reiner Pope <span dir="ltr"><<a href="mailto:reiner.pope@gmail.com" target="_blank">reiner.pope@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="gmail_quote"><div><div></div><div>On 9 August 2011 10:06, Bryan O'Sullivan <span dir="ltr"><<a href="mailto:bos@serpentine.com" target="_blank">bos@serpentine.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="gmail_quote"><div>On Mon, Aug 8, 2011 at 9:24 AM, Chris Yuen <span dir="ltr"><<a href="mailto:kizzx2%2Bhaskell@gmail.com" target="_blank">kizzx2+haskell@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>For reference I have asked the same question on StackOverflow. One person suggested that the reason might be that Int64 on Windows is broken (<a href="http://stackoverflow.com/questions/6970904/analyzing-slow-performance-of-a-haskell-program/6976448#6976448" target="_blank">http://stackoverflow.com/questions/6970904/analyzing-slow-performance-of-a-haskell-program/6976448#6976448</a>).<br>
</blockquote><div><br></div></div><div>No, they're barking up the wrong tree.</div><div><br></div><div>I've put an idiomatic Haskell translation of your C++ algorithm at <a href="https://gist.github.com/1133048#file_wordy.hs" target="_blank">https://gist.github.com/1133048#file_wordy.hs</a></div>
<div><br></div><div>(I've also included a copy of your original C++, with a bug fixed, in the same gist.)</div><div><br></div><div>As you can see, the two are almost identical. Not surprisingly, each one spends the bulk of its time computing word lengths.</div>
<div><br></div><div>GHC simply doesn't do a great job of compiling fairly tight code like this. gcc generates about 100 lines of assembly that's mostly easy to follow (except for some bit-twiddling tricks to avoid div instructions). Although the Core it generates looks fine, GHC spends quite a bit of time in its generated assembly on what looks to me like STG housekeeping (it spends only 0.3% of its time in the garbage collector, because it doesn't allocate memory). The overall result is that the Haskell code runs about 5x more slowly than the C++ code.</div>
</div>
<br></blockquote><div><br></div></div></div><div>GHC generating bad assembly suggests trying the llvm codegen (see <a href="http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs-new-llvm-codegen/" target="_blank">http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs-new-llvm-codegen/</a>). Compiling Bryan's code with</div>
<div><br></div><div>$ ghc -O2 -fllvm Wordy.hs</div><div><br></div><div>it now runs only 2x slower than the C++ code.</div><div><br></div><font color="#888888"><div>Reiner</div></font></div>
</blockquote></div><br>