Making Haskell Code faster

Question

Does anyone know how to make this Haskell code fun faster? I am doing Project Euler #14. This code runs in 4.029 seconds:

collatz :: Int -> Int64 -> Int                                                                                                                                                 
collatz c 1 = c                                                                 
collatz c k                                                                     
    | even k    = collatz (c+1) (k `div` 2)                                     
    | otherwise = collatz (c+1) (3*k + 1)                                       

main = do                    
    print $ maximum (map (\i -> (collatz 1 i, i)) [1..1000000])

Memoizing the collatz function actually increases the runtime, so I did not do any memoization. The comparable C code runs in 0.239 seconds:

int main(int argc, char *argv[])
{
    int maxlength = 0;
    int maxstart = 1;
    for (int i = 1; i <= 1000000; i++) {
        unsigned long k = i;
        int length = 1;
        while (k > 1) {
            length += 1;
            if (k % 2 == 0)
                k = k / 2;
            else
                k = 3*k + 1;
        }
        if (length > maxlength) {
            maxlength = length;
            maxstart = i;
        }
    }
    printf("%d, %d\n", maxlength, maxstart);
    return 0;
}

The Haskell code is compiled with ghc -O3 and the C code is compiled with gcc -std=c99 -O3.

Strictness annotations are the first thing followed by `shiftR x 1` instead of `div x 2` (yes, some key optimizations are still missing). This gets you to striking distance from C. — Thomas M. DuBuisson, Dec 18 '14 at 23:57
This particular Project Euler problem has spawned a whole bunch of similar performance questions in the past. Take a look at [this search](http://stackoverflow.com/search?q=[haskell]+collatz) for a bunch of advice. [This one](http://stackoverflow.com/questions/13669134/c-vs-haskell-collatz-conjecture-speed-comparison/13669277#13669277) might be particularly relevant. — Tikhon Jelvis, Dec 19 '14 at 00:22
Do you have LLVM? it runs in 1.3 sec on my machine with -O2 -fllvm. — András Kovács, Dec 19 '14 at 00:52
Yes, llvm does the optimizations of making the division a right shift and the even test a bitwise and. Compiling the code as is with -fllvm, or manually changing the above problems, my code runs in 0.420 seconds now. Thanks for the help everyone. — spacepotato, Dec 19 '14 at 00:53

score 5 · Answer 1 · edited May 23 '17 at 12:12

It was brought to my attention that this question is largely a repost. See here.

The main problem with the code is that ghc by default does not optimize integer divisions. To fix my code manually,

collatz c k                                                                     
    | k .&. 1 == 0 = collatz (c+1) (k `shiftR` 1)                                     
    | otherwise    = collatz (c+1) (3*k + 1)

However, if LLVM is installed on the machine, one could compile the original code with

ghc -O2 -fllvm code.hs

LLVM does the necessary optimizations. Both solutions make my code run at approxmiately 0.420 seconds, which is much closer to the comparable C code.

score 0 · Answer 2 · answered Dec 19 '14 at 01:03

Here is a solution from the haskell wiki:

import Data.Array
import Data.List
import Data.Ord (comparing)

syrs n =
    a
    where
    a = listArray (1,n) $ 0:[1 + syr n x | x <- [2..n]]
    syr n x =
        if x' <= n then a ! x' else 1 + syr n x'
        where
        x' = if even x then x `div` 2 else 3 * x + 1

main =
    print $ maximumBy (comparing snd) $ assocs $ syrs 1000000

Computation time on my machine:

haskell|master⚡ ⇒ ghc -O2 prob14_memoize.hs
[1 of 1] Compiling Main             ( prob14_memoize.hs, prob14_memoize.o )
Linking prob14_memoize ...
haskell|master⚡ ⇒ time ./prob14_memoize
(837799,524)
./prob14_memoize  0.63s user 0.03s system 99% cpu 0.664 total

Compared to original:

haskell|master⚡ ⇒ ghc -O2 prob14_orig.hs
[1 of 1] Compiling Main             ( prob14_orig.hs, prob14_orig.o )
Linking prob14_orig ...
haskell|master⚡ ⇒ time ./prob14_orig
(525,837799)
./prob14_orig  2.77s user 0.01s system 99% cpu 2.777 total

Yes, but the problem size is small enough that the overhead from memoization actually makes it slower. This code runs in 0.911 seconds as opposed to the original code which runs in 0.420 seconds. Both were compiled with ghc -O2 -fllvm — spacepotato, Dec 19 '14 at 01:12

Making Haskell Code faster

2 Answers2