为什么严格的长度函数表现得明显更快？

Question

为了更好地理解评估模型，我反复讨论了定义，并为列表的长度编写了两个。

天真的定义：

len :: [a] -> Int
len [] = 0
len (_:xs) = 1 + len xs

严格(和尾递归)定义：

slen :: [a] -> Int -> Int
slen [] n = n
slen (_:xs) !n = slen xs (n+1)

len [1..10000000]大约需要5-6秒才能执行.

slen [1..10000000] 0大约需要3-4秒才能执行.

我很好奇为什么。在我检查这些性能之前，我确信它们会执行大致相同的操作，因为len最多只能再进行一次评估。为示范目的：

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 4

和

slen [a,b,c,d] 0
= slen [b,c,d] 1
= slen [c,d]   2
= slen [d]     3
= slen []      4
= 4

是什么使slen显着地更快？

我还写了一个尾递归懒惰函数(和slen一样，但很懒)，试图接近原因--也许是因为它是尾递归的--但是它的表现与天真的定义差不多。

Answer 1

len的最后一步不是O(1)。把n个数相加是O(n)。len还使用O(n)内存，而slen使用O(1)内存。

它使用O(n)内存的原因是每一次内存都会消耗掉一些内存。所以当你有这样的事情时：

1 + 1 + 1 + 1 + len []

有五个未评估的块(包括len [])

在GHCi中，我们可以使用:sprint命令更容易地检查这种thunk行为。:sprint命令打印给定的值，而不强制计算任何块(您可以从:help中学到更多)。我将使用conses ((:))，因为我们可以更容易地一次评估每一次，但原理是相同的。

λ> let ys = map id $ 1 : 2 : 3 : [] :: [Int] -- map id prevents GHCi from being too eager here
λ> :sprint ys
ys = _
λ> take 1 ys
[1]
λ> :sprint ys
ys = 1 : _
λ> take 2 ys
[1,2]
λ> :sprint ys
ys = 1 : 2 : _
λ> take 3 ys
[1,2,3]
λ> :sprint ys
ys = 1 : 2 : 3 : _
λ> take 4 ys
[1,2,3]
λ> :sprint ys
ys = [1,2,3]

未评估的块由_表示，您可以看到原始ys中有嵌套在彼此内部的4块，列表的每个部分(包括[])都有一个。

在Int中没有一种很好的方法可以看到这一点，因为它的评估更多的是全部或者根本没有，但是它仍然以同样的方式构建了一个嵌套的thunk。如果你能看到它是这样的，它的评估应该是这样的：

len [a,b,c,d]
= 1 + len [b,c,d]
= 1 + 1 + len [c,d]
= 1 + 1 + 1 + len [d]
= 1 + 1 + 1 + 1 + len []
= 1 + 1 + 1 + 1 + 0
= 1 + 1 + 1 + 1       -- Here it stops building the thunks and starts evaluating them
= 1 + 1 + 2
= 1 + 3
= 4

Answer 2

David Young的回答正确地解释了评价顺序上的差异。你应该以Haskell概述的方式来考虑他的评估。

让我给你们展示一下核心的不同之处。我认为随着优化的进行，它实际上更加可见，因为评估结果是一个显式的case语句。如果您以前从未玩过Core，请参阅关于主题：Reading GHC Core的规范所以问题。

用ghc -O2 -ddump-simpl -dsuppress-all -ddump-to-file SO27392665.hs生成核心输出。您将看到GHC将len和slen分为递归的"worker“函数、$wlen或$wslen以及非递归的”包装器“函数。因为绝大部分时间都花在递归的“工作人员”上，所以请关注它们：

Rec {
$wlen
$wlen =
  \ @ a_arZ w_sOR ->
    case w_sOR of _ {
      [] -> 0;
      : ds_dNU xs_as0 ->
        case $wlen xs_as0 of ww_sOU { __DEFAULT -> +# 1 ww_sOU }
    }
end Rec }

len
len =
  \ @ a_arZ w_sOR ->
    case $wlen w_sOR of ww_sOU { __DEFAULT -> I# ww_sOU }

Rec {
$wslen
$wslen =
  \ @ a_arR w_sOW ww_sP0 ->
    case w_sOW of _ {
      [] -> ww_sP0;
      : ds_dNS xs_asW -> $wslen xs_asW (+# ww_sP0 1)
    }
end Rec }

slen
slen =
  \ @ a_arR w_sOW w1_sOX ->
    case w1_sOX of _ { I# ww1_sP0 ->
    case $wslen w_sOW ww1_sP0 of ww2_sP4 { __DEFAULT -> I# ww2_sP4 }
    }

您可以看到，$wslen只有一个case，而$wlen只有两个。如果您查看David的答案，您可以跟踪$wlen中发生的事情:它对最外层的列表构造函数([]/:)进行案例分析，然后对$wlen xs_as0 (即len xs)进行递归调用，它也会对$wlen xs_as0进行case，即强制累积的thunk。

另一方面，在$wslen中，只有一个case语句。在递归分支中，有一个未加框的加法，(+# ww_sP0 1)，它不会创建thunk。

(注:这个答案的前一个版本曾指出，使用-O，GHC可以专门化$wslen，但不能使用$wlen来使用未装箱的Int#。事实并非如此。)