总结一大堆数字太慢了

Question

任务:"总计前15,000,000个偶数."

哈斯克尔:

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

MySum:: Int
MySum= sum $ take 15000000 evens

......但MySum需要很长时间.更确切地说,比C/C++慢大约10-20倍.

很多时候我发现,自然编码的Haskell解决方案比C慢10倍.我预计GHC是一个非常优化的编译器和任务,这样看起来并不那么难.

所以,人们会期望比C慢1.5-2倍.问题出在哪里？

这可以更好地解决吗？

这是我用它比较的C代码:

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),需要作为一个功能来实现.

Answer 1

列表不是循环

因此,如果使用列表作为循环替换,请不要感到惊讶,如果循环体很小,则会得到较慢的代码.

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

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

sum 不是一个"好消费者",所以GHC(还)不能完全消除中间名单.

如果使用optimisations进行编译(并且不导出nat),GHC足够聪明,可以filter与枚举融合,

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 }

但就GHC的融合而言,这就是它.你留下了拳击Int和构建列表单元格.如果你给它一个循环,就像你把它交给C编译器,

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)

您可以获得预期的C和Haskell版本之间的运行时间的近似关系.

这种算法并不是GHC所教导的优化方法,在将有限的人力投入到这些优化之前,还有更大的鱼类在其他地方进行炒作.

Answer 2

列表融合无法在这里工作的问题实际上相当微妙.假设我们定义了RULE将列表融合的权利:

import GHC.Base
sum2 :: Num a => [a] -> a
sum2 = sum
{-# NOINLINE [1] sum2 #-}
{-# RULES "sum" forall (f :: forall b. (a->b->b)->b->b).
                sum2 (build f) = f (+) 0 #-}

(简短的解释是我们定义sum2为别名sum,我们禁止GHC尽早内联,因此RULE有机会在sum2被淘汰之前触发.然后我们sum2直接寻找list-builder旁边build(参见定义)并替换它通过直接算术.)

这取得了成功,因为它产生了以下核心:

Main.$wgo =
  \ (w_s1T4 :: GHC.Prim.Int#) ->
    case GHC.Prim.remInt# w_s1T4 2 of _ {
      __DEFAULT ->
        case w_s1T4 of wild_Xg {
          __DEFAULT -> Main.$wgo (GHC.Prim.+# wild_Xg 1);
          15000000 -> 0
        };
      0 ->
        case w_s1T4 of wild_Xg {
          __DEFAULT ->
            case Main.$wgo (GHC.Prim.+# wild_Xg 1) of ww_s1T7 { __DEFAULT ->
            GHC.Prim.+# wild_Xg ww_s1T7
            };
          15000000 -> 15000000
        }
    }

哪个好,完全融合的代码 - 我们$wgo在非尾部调用位置调用的唯一问题.这意味着我们不是在看循环,而是在一个深度递归的函数中,具有可预测的程序结果:

Stack space overflow: current size 8388608 bytes.

这里的根本问题是Prelude的列表融合只能融合正确的折叠,并且将和计算为右折叠直接导致过多的堆栈消耗.显而易见的解决方法是使用可以实际处理左侧折叠的融合框架,例如Duncan的流融合包,它实际上实现了sum融合.

另一种解决方案是破解它 - 并使用右折叠实现左折叠:

main = print $ foldr (\x c -> c . (+x)) id [2,4..15000000] 0

这实际上产生了与当前版本的GHC接近完美的代码.另一方面,这通常不是一个好主意,因为它依赖于GHC足够聪明以消除部分应用的功能.已经filter在链中添加一个将打破特定的优化.

Answer 3

首先汇总15,000,000个偶数:

{-# LANGUAGE BangPatterns #-}

g :: Integer    -- 15000000*15000001 = 225000015000000
g = go 1 0 0
  where
    go i !a c  | c == 15000000 = a       
    go i !a c  | even i = go (i+1) (a+i) (c+1)
    go i !a c           = go (i+1) a c

应该是最快的.