One magnitude slower generating hailstone sequence in haskell than in c

Question

In his blog post The Glasgow Haskell Compiler and LLVM, David Terei used an example that generated hailstone sequence to compare GHC performance with C. I decide to run it myself and the result is unbelievable: the GHC version is more than one magnitude slower. The code is innocent enough:

import Data.Word

collatzLen :: Int -> Word32 -> Int
collatzLen c 1 = c
collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2
               | otherwise      = collatzLen (c+1) $ 3*n+1

pmax x n = x `max` (collatzLen 1 n, n)

main = print . solve $ 1000000
    where solve xs = foldl pmax (1,1) [2..xs-1]

Except substituting foldl with foldl', I don't think I can do anything to it. GHC version finds the answer in 45+ seconds, no matter which backend I use, while C version uses merely 1.5 seconds!

My setup is Haskell platform 2011.2.0.1 (32bit) + OS X 10.6.6 vs. gcc 4.2.1. David used GHC 6.13 in his post. Is this a known bug of GHC 7.0.3? Or I must have missed something very obvious.

EDIT: Turns out I did miss something obvious. By simply using -O2 flag, ghc produces very fast code now.

which compile flags are you using? For me, this code executes in 4s when compiled with ghc-7.0.4 -O2. '-O' is only slightly slower. — John L
@John L, I used --make -fforce-recomp -fllvm. By using -O2 as you suggested, ghc is on par with gcc. Thanks. — edwardw
@eternalmatt my question was why ghc produced slow code in this case. It has been solved. — edwardw

edwardw edwardw · Accepted Answer · 2011-07-13T16:30:51

My question was why GHC produced such slow code in this particular case. The answer is to use optimization flag, -O, -O2, etc. By using it, I saw execution time dropped from 45+ seconds to 0.6 second, ~80x improvement.

One magnitude slower generating hailstone sequence in haskell than in c

1 Answers