<div class="gmail_quote">On 9 August 2011 10:06, Bryan O'Sullivan <span dir="ltr"><<a href="mailto:bos@serpentine.com">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 class="im">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>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/">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><div>Reiner</div><meta http-equiv="content-type" content="text/html; charset=utf-8"></div>