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
– Thomas M. DuBuisson, Commented Dec 18, 2014 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 for a bunch of advice. This one might be particularly relevant. — Tikhon Jelvis
– Tikhon Jelvis, Commented Dec 19, 2014 at 0:22
Do you have LLVM? it runs in 1.3 sec on my machine with -O2 -fllvm. — András Kovács
– András Kovács, Commented Dec 19, 2014 at 0: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
– spacepotato, Commented Dec 19, 2014 at 0:53

Community · Accepted Answer · 2017-05-23 12:12:48Z

5

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.

edited May 23, 2017 at 12:12

CommunityBot

11 silver badge

answered Dec 19, 2014 at 1:20

spacepotato

1837 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

spencerlyon2 · Accepted Answer · 2014-12-19 01:03:15Z

0

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

answered Dec 19, 2014 at 1:03

spencerlyon2

9,7464 gold badges33 silver badges41 bronze badges

1 Comment

spacepotato Over a year ago

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

Collectives™ on Stack Overflow

Making Haskell Code faster

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related