Summing a large list of numbers is too slow

ghc, haskell

Solution

Lists are not loops

So don't be surprised if using lists as a loop replacement, you get slower code if the loop body is small.

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

`sum` is not a "good consumer", so GHC is not (yet) able to eliminate the intermediate lists completely.

If you compile with optimisations (and don't export `nat`), GHC is smart enough to fuse the `filter` with the enumeration,

Rec {
Main.main_go [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> [GHC.Types.Int]
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.main_go =
  \ (x_aV2 :: GHC.Prim.Int#) ->
    let {
      r_au7 :: GHC.Prim.Int# -> [GHC.Types.Int]
      [LclId, Str=DmdType]
      r_au7 =
        case x_aV2 of wild_Xl {
          __DEFAULT -> Main.main_go (GHC.Prim.+# wild_Xl 1);
          9223372036854775807 -> n_r1RR
        } } in
    case GHC.Prim.remInt# x_aV2 2 of _ {
      __DEFAULT -> r_au7;
      0 ->
        let {
          wild_atm :: GHC.Types.Int
          [LclId, Str=DmdType m]
          wild_atm = GHC.Types.I# x_aV2 } in
        let {
          lvl_s1Rp :: [GHC.Types.Int]
          [LclId]
          lvl_s1Rp =
            GHC.Types.:
              @ GHC.Types.Int wild_atm (GHC.Types.[] @ GHC.Types.Int) } in
        \ (m_aUL :: GHC.Prim.Int#) ->
          case GHC.Prim.<=# m_aUL 1 of _ {
            GHC.Types.False ->
              GHC.Types.: @ GHC.Types.Int wild_atm (r_au7 (GHC.Prim.-# m_aUL 1));
            GHC.Types.True -> lvl_s1Rp
          }
    }
end Rec }

but that's as far as GHC's fusion takes it. You are left with boxing `Int`s and constructing list cells. If you give it a loop, like you give it to the C compiler,

module Main where

import Data.Bits

main :: IO ()
main = print dumbSum

dumbSum :: Int
dumbSum = go 0 0 1
  where
    go :: Int -> Int -> Int -> Int
    go sm ct n
        | ct >= 15000000 = sm
        | n .&. 1 == 0   = go (sm + n) (ct+1) (n+1)
        | otherwise      = go sm ct (n+1)

you get the approximate relation of running times between the C and the Haskell version you expected.

This sort of algorithm is not what GHC has been taught to optimise well, there are bigger fish to fry elsewhere before the limited manpower is put into these optimisations.

Problem

Task: "Sum the first 15,000,000 even numbers." Haskell: ``` nats = [1..] :: [Int] evens = filter even nats :: [Int] MySum:: Int MySum= sum $ take 15000000 evens ``` ...but `MySum` takes ages. More precisely, about 10-20 times slower than C/C++. Many times I've found, that a Haskell solution coded naturally is something like 10 times slower than C. I expected that GHC was a very neatly optimizing compiler and task such this don't seem that tough. So, one would expect something like 1.5-2x slower than C. Where is the problem? Can this be solved better? This is the C code I'm comparing it with: ``` long long sum = 0; int n = 0, i = 1; for (;;) { if (i % 2 == 0) { sum += i; n++; } if (n == 15000000) break; i++; } ``` Edit 1: I really know, that it can be computed in O(1). Please, resist. Edit 2: I really know, that evens are `[2,4..]` but the function `even` could be something else `O(1)` and need to be implemented as a function.

Original source