总结一大堆数字太慢了 [英] Summing a large list of numbers is too slow

问题描述

任务：总计前15,000,000个偶数。

Haskell：

  nats = [1 ..] :: [Int] 
 evens =过滤偶数nats :: [Int] 
 
 MySum :: Int 
 MySum = sum $ take 15000000 evens 
  

...但 MySum 需要长时间。更准确地说，大约比C / C ++慢10-20倍。

很多次我发现，Haskell解决方案自然编码比C慢10倍。我预计GHC是一个非常优化的编译器，而且这样的任务看起来并不困难。所以，人们会预期比C慢1.5-2倍。 哪里有问题？

这可以解决得更好吗？

将它与以下内容进行比较：

  long long sum = 0; 
 int n = 0，i = 1; （$; 
 
 for（;;）{
 
 if（i％2 == 0）{
 sum + = i; 
 n ++; 
} 
 
 if（n == 15000000）
 break; 
 
 i ++; 
} 
  

编辑1 ：我真的知道，可以在O（1）中计算。请耐心等待。

编辑2 ：我真的知道，evens是 [2,4 ..] ，但函数 even 可能是其他的 O（1），需要实现为一个函数。

解决方案

列表不是循环

如果使用列表作为循环替换，你会感到很惊讶，如果循环体很小，你会得到较慢的代码。

  nats = [1 ..] :: [Int] 
 evens =过滤偶数nats :: [Int] 
 
 dumbSum :: Int 
 dumbSum = sum $ take 15000000 evens 
  

sum 不是好消费者，因此GHC不是（还）能够完全消除中间列表。

如果使用优化进行编译（并且不导出 nat ），GHC非常聪明，可以将过滤器与枚举进行融合，

  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 ＃） - > 
让{b $ b r_au7 :: GHC.Prim.Int＃ - > [GHC.Types.Int] 
 [LclId，Str = DmdType] 
 r_au7 = 
 case x_aV2 wild_Xl {
 __DEFAULT  - > Main.main_go（GHC.Prim。+＃wild_X11）; 
 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} {
 lvl_s1Rp :: [GHC.Types.Int] 
 [LclId] 
 lvl_s1Rp = 
 GHC.Types .: 
 @ GHC.Types.Int wild_atm（GHC 。$] 
 \（m_aUL :: GHC.Prim.Int＃） - >。类型。[] @ GHC.Types.Int）} in 
 \ 
 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 
} 
} 
结束记录} 
  

就像GHC的融合需要它一样。您将留下拳击 Int s并构造列表单元格。如果你给它一个循环，就像你给它的C编译器一样，

  module Main其中
 
导入Data.Bits 
 
 main :: IO（）
 main =打印dumbSum 
 
 dumbSum :: Int 
 dumbSum = go 0 0 1 
其中
 go :: Int  - > Int  - > Int  - > Int 
 go sm ct n 
 | ct> = 15000000 = sm 
 | n& ;. 1 == 0 = go（sm + n）（ct + 1）（n + 1）
 |否则= go sm ct（n + 1）
  

您可以得到C以及你期望的Haskell版本。

这种算法不是GHC被教导的优化，有限的人力投入之前，进入这些优化。

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.

解决方案

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 Ints 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.

这篇关于总结一大堆数字太慢了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！