Re: [Haskell-cafe] Analyzing slow performance of a Haskell program

On 9 August 2011 10:06, Bryan O'Sullivan wrote:

On Mon, Aug 8, 2011 at 9:24 AM, Chris Yuen wrote:

...

For reference I have asked the same question on StackOverflow. One person suggested that the reason might be that Int64 on Windows is broken ( http://stackoverflow.com/questions/6970904/analyzing-slow-performance-of-a-h... ).

No, they're barking up the wrong tree.

I've put an idiomatic Haskell translation of your C++ algorithm at https://gist.github.com/1133048#file_wordy.hs

(I've also included a copy of your original C++, with a bug fixed, in the same gist.)

As you can see, the two are almost identical. Not surprisingly, each one spends the bulk of its time computing word lengths.

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.

GHC generating bad assembly suggests trying the llvm codegen (see http://donsbot.wordpress.com/2010/02/21/smoking-fast-haskell-code-using-ghcs...). Compiling Bryan's code with $ ghc -O2 -fllvm Wordy.hs it now runs only 2x slower than the C++ code. Reiner