对于一个大数列的求和速度太慢

Question

任务：将前1500万个偶数相加。

Haskell：

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

MySum:: Int
MySum= sum $ take 15000000 evens

但是MySum太慢了，确切地说，比C/C++慢10-20倍。

我发现很多时候，一个自然编码的Haskell解决方案大约比C慢10倍。我原本以为GHC是一个非常优化的编译器，这样的任务似乎并不困难。

因此，人们可以期望Haskell比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： 我知道，偶数是[2,4..]，但函数even可能是其他的O(1)并且需要作为一个函数实现。

- Cartesius00

---

我相信我在[http://www.joachim-breitner.de/publications/CallArity-TFP.pdf call arity]的工作可以大大提高它的速度，通过允许sum融合，因此可以尝试使用GHC 7.9（当前的git HEAD）。 - Joachim Breitner

Answer 1

列表不是循环

因此，如果使用列表作为循环替代方式，在循环体较小的情况下，获得较慢的代码可能并不令人惊讶。

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

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

sum没有很好的消费能力，所以 GHC 目前还不能完全消除中间列表。

如果使用优化编译（并且不导出 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擅长优化的，我们在有限的人力资源投入这些优化之前，还有更重要的问题需要处理。

- Daniel Fischer

---

最后终于有一个聪明的回答了！其中关于导出的那一点非常出色。 - Cartesius00

我们如何强制GHC生成带有未装箱整数的版本？ - Cartesius00

通过不构建中间列表来实现。如果您按照上述循环编写代码，它只能处理未装箱的 Int# 类型。如果使用 -fllvm 编译，甚至可以在代码中保留 even n 而不是 n .&. 1 == 0 （这是另一种低级优化，但尚未在 GHC 中实现）。如果必须将某些内容放入列表中，则该内容必须被装箱，因此如果要使用未装箱，则需要帮助 GHC 避免使用列表。 - Daniel Fischer

@Martin，答案中已经反复告诉你列表不是循环，请注意这一点。 - AndrewC

我认为Yatima2975（下面）关于CAF减慢速度并掩盖一些问题的观点很重要。在我的机器上，使用ghc 8.0.2编译并使用-O2，如果我在mySum中用“filter even [1..]”替换“evens”，那么代码大约快了30倍，而sum似乎是一个良好的消费者。如果在这样做之后，我将mySum与优化的dumbSum进行比较，那么mySum只比dumbSum慢8倍。其中一些可能还反映出我使用的ghc版本比原始帖子发布时使用的版本新了约5年。 - George Co

由于Joachim的工作，正如他在上面提到的那样，sum现在是一个很好的消费者。很高兴看到GHC在这些年里得到了改进！然而，CAF仍然可能会导致时间和空间性能问题，这也是我几分钟前发帖的重点。 - George Co

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被消除之前触发。然后我们直接查找紧挨着列表构建器build的sum2（参见定义），并用直接算术运算替换它。）

（这种方法效果有好坏之分，因为它产生了以下 Core 代码：）

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的stream-fusion包，该包实际上实现了sum融合。

另一个解决方案是通过“hack”来绕过它 - 使用右折叠来实现左折叠：

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

实际上，使用当前版本的GHC，这确实可以生成接近完美的代码。另一方面，这通常不是一个好主意，因为它依赖于GHC能够聪明地消除部分应用的函数。即使是在链中加入filter也会破坏该特定优化。

- Peter Wortmann

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

应该是最快的。

- Will Ness

Answer 4

如果您希望确保只遍历列表一次，可以显式编写遍历：

nats = [1..] :: [Int]

requiredOfX :: Int -> Bool -- this way you can write a different requirement
requiredOfX x = even x

dumbSum :: Int
dumbSum = dumbSum' 0 0 nats
  where dumbSum' acc 15000000 _ = acc
        dumbSum' acc count (x:xs)
          | requiredOfX x = dumbSum' (acc + x) (count + 1) xs
          | otherwise     = dumbSum' acc (count + 1) xs

- amindfv

---

但是，如果这应该是正确的解决方案，我们可以把 Haskell 扔掉，留在 C。 - Cartesius00

很可能 GHC 会以这种方式优化代码，但这样你就可以客观比较你的实现。此外，我认为即使我们需要编写这样的函数，使用 Haskell 也有很多令人信服的理由。 - amindfv

@Martin Sure - 如果你的程序只是用来求偶数之和，那么用哪种编程语言编写其实没什么区别。 - Chris Taylor

@Martin 等等..你认为Haskell比C更糟糕是因为当你选择不在Haskell中使用递归时，你就不能享受使用递归的好处吗？当你选择不在C中使用循环或裸递归时，它对你有多大帮助？你使用C的基于列表的解决方案有多快？ - AndrewC

@AndrewC 如果我可以为评论授予声望点数，我会为那个评论授予的。真的。 :) “你的基于列表的 C 解决方案有多快？” 这是 T 恤材料。 :) - Will Ness

Answer 5

首先，你可以像年轻的高斯一样聪明地计算总和，时间复杂度为O(1)。

除了有趣的事情之外，你的Haskell解决方案使用了列表。我相当确定你的C/C++解决方案没有使用列表。（Haskell列表非常容易使用，因此人们往往会在可能不合适的情况下使用它们。）尝试对此进行基准测试：

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 1     = result
               | otherwise  = f (n + result) (n - 2)

使用GHC编译，加入-O2参数。该函数是尾递归的，因此编译器可以非常高效地实现它。 更新: 如果你想使用even函数，也是可能的：

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 0     = result
               | even n     = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

你也可以轻松地将过滤功能作为参数传递：

sumFilter :: (Integral a) => (a -> Bool) -> a -> a
sumFilter filtfn = f 0
  where
    f result n | n <= 0     = result
               | filtfn n   = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

- Petr

---

虽然你作弊并省略了even函数，但那可能是答案。但这也意味着，GHC是个白痴，甚至不能优化这个简单的filter场景。 - Cartesius00

@amindfv 这绝对是正确的，但优化器还远非完美。 - Cartesius00

@Martin 请发布你的C/C++版本，这样我们可以进行比较。 - Petr

@PetrPudlák，Petr，他在那里。但是不要再想了。结论是必须用尾递归来编写它，并且当前的GHC无法对其进行优化。这就是我想知道的全部内容 :-) - Cartesius00

@Martin，如果ghc因为无法优化这个简单的代码而被称为白痴，那么谁才是拒绝最佳优化的白痴呢？你知道有一个O(1)算法，请使用它。当你真正遇到Haskell速度方面的问题时，我会感兴趣的。你又一次毫无意义地拒绝了良好的编程，而选择了竞争编译器。 - AndrewC

@Petr，你的最新版本仍然没有完全遵循OP规范。你必须使用单独的计数器来计算成功的数字 - 对于任意过滤函数，我们不知道从哪里开始。但这并不重要。 :) - Will Ness

Answer 6

严格版本的工作速度更快：

foldl' (+) 0 $ take 15000000 [2, 4..]

- Cfr

---

不好意思，它在我的电脑上并没有起作用。 - Cartesius00

[2,4...]，even函数同样是必不可少的。 - Cartesius00

@Martin：应该是可以的。你是怎么编译你的程序的？ - Sarah

尝试一下: ghc -fllvm -optc-O2 -O2 foo.hs -fforce-recomp。 - Cartesius00

@Sarah，你低估了GHC。由于类型已经被定义为“Int”，它自己就使得另一个版本变得严格了，因此与“foldl' (+) 0”没有区别。 - Daniel Fischer

Answer 7

需要注意的是，nats和evens被称为常量应用形式或简称为CAF。基本上，这些对应于没有任何参数的顶层定义。 CAF有点奇怪，例如是可怕的单态限制的原因; 我不确定语言定义甚至允许CAFs内联。

在我心目中Haskell执行的方式，当dumbSum返回一个值时，evens将被评估为类似于2：4：...：30000000：<thunk>，而nats则为1：2：... ：30000000：<thunk>，其中<thunk>代表尚未查看的内容。如果我的理解是正确的，那么这些：的分配确实必须发生，并且不能被优化掉。

因此，一种在不太改变代码的情况下加快速度的方法是简单地编写：

dumbSum :: Int
dumbSum = sum . take 15000000 . filter even $ [1..]

或者

dumbSum = sum $ take 15000000 evens where
    nats = [1..]
    evens = filter even nats

在我的机器上，使用-O2编译，这似乎可以使速度提高约30%。

我不是GHC专家（我甚至从未对Haskell程序进行过分析！），所以我的想法可能完全错误。

- yatima2975

---

不使用 -O2 编译选项时，该程序的 OP 代码（加上“main = print dumbSum”定义）需要数百 MB 的内存才能运行，但是使用 -O2 编译选项时，它可以独立地在 1MB 内存中运行。我认为这意味着使用 -O2 编译选项时，列表不会被保留。 - Will Ness

@WillNess：好的，我没想到去检查空间使用情况。GHC比我想象中要聪明！感谢您的纠正！ - yatima2975