3
\$\begingroup\$

I'm new to Haskell, and I'm wondering why my programs are so slow compared to other languages.

Haskell, 6 seconds (x64, -O2):

nextCollatz :: Int -> Int
nextCollatz x = if even x
    then quot x 2
    else 3 * x + 1

collatzLength :: Int -> Int
collatzLength x = if x == 1
    then 0
    else 1 + collatzLength (nextCollatz x)

main = print . show . sum . map collatzLength $ [1..3000000]

Julia, 0.8 seconds (excluding the compilation time):

function main()
    sum = 0
    for i = [1:3000000]
        while i > 1
            i = isodd(i) ? 3 * i + 1 : i >> 1
            sum += 1
        end
    end
    sum
end

println(main())

Maybe the comparison isn't fair, but I'd like to know how to improve my Haskell code to bring it on par with other high-level languages such as Julia and JavaScript.

While memoization and parallelization would definitely help, currently I'm concerned with efficient iteration and arithmetic.

\$\endgroup\$
5
\$\begingroup\$

Your initial version - 6.834 seconds.

Version with quot and even operations replaced with bitwise - 6.651 seconds.

This version - 0.928 seconds:

import Data.Bits

tOdd sum 1 = sum
tOdd sum x = tEven (sum + (tEven2 0 x)) (x - 1)

tEven sum x = tOdd (sum + (tOdd2 0 x)) (x - 1)

tEven2 sum x | (x .&. 2) == 0 = tEven2 (sum + 1) (x `shiftR` 1)
tEven2 sum x | otherwise      = tOdd2 (sum + 1) (x `shiftR` 1)

tOdd2 sum 1 = sum
tOdd2 sum x = tEven2 (sum + 1) (3 * x + 1)

main = print . show $ tEven (0 :: Int) (3000000 :: Int)

The previous with -O3 -fllvm -optlo-O3 flags - 0.686 seconds.

The previous with all functions supported with INLINE pragma - 0.604 seconds.

More than 10 times faster than initially :)

Yes, low-level numeric operations and iterations are hard in Haskell, the language doesn't suite well for this.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ OMG, this is impressive. I like your trick with (x .&. 2) and splitting the function into even and odd to save some calls and avoid checking parity. Thank you! \$\endgroup\$ – Alexey Lebedev May 16 '14 at 20:05
3
\$\begingroup\$

This one is based on my original code with improvements suggested by leventov. Down to 0.7 seconds from the initial 6 seconds thanks to tail recursion and bitwise operations.

import Data.Bits

collatzLength :: Int -> Int -> Int
collatzLength sum x
    | x == 1       = sum
    | testBit x 0  = collatzLength (sum + 2) (shiftR (3*x + 1) 1)
    | otherwise    = collatzLength (sum + 1) (shiftR x 1)

main = print $ foldl collatzLength 0 [1..3000000]
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Your program is non-portable: you might have an Int overflow. An Int is only guaranteed to hold up to 229 - 1, though the limit could be larger on some systems.

The Collatz sequence for 159487 goes rather high.

collatzSeq :: Integer -> [Integer]
collatzSeq 1 = [1]
collatzSeq x
  | even x    = x : collatzSeq (x `div` 2)
  | otherwise = x : collatzSeq (3 * x + 1)

*Main> maximum $ collatzSeq 159487
17202377752
*Main> (maximum $ collatzSeq 159487) < 2 ^ 29
False

Therefore, you should be using an Int64 or Integer for this problem.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Yeah, I ran into this issue when I tried using Word32 and got an overflow on 159487. But Integer and Int64 were 3 times slower than Int in my experiments. \$\endgroup\$ – Alexey Lebedev May 16 '14 at 22:25
  • \$\begingroup\$ That's weird that Int64 performs slower than Int, if Int is already 64-bit arithmetic on your machine. \$\endgroup\$ – 200_success May 16 '14 at 22:50
  • \$\begingroup\$ Yes, that's so weird. In the first example in my answer if I change Int to Int64 the execution time goes up from 0.6 to 20 seconds! But it the second example I've added Int64 and the execution time went down from 0.95 to 0.85. I've checked and rechecked several times. \$\endgroup\$ – Alexey Lebedev May 16 '14 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.