haskell - 为什么 splitAt 函数的惰性模式匹配版本更快？

Question

splitAt函数可以实现如下(https://wiki.haskell.org/Lazy_pattern_match):

import Prelude hiding (splitAt)
splitAt :: Int -> [a] -> ([a], [a])
splitAt n xs =
  if n<=0
     then ([], xs)
     else
        case xs of
          [] -> ([], [])
          y:ys ->
            case splitAt (n-1) ys of
              ~(prefix, suffix) -> (y : prefix, suffix) -- Here using lazy pattern match

main :: IO ()
main = do
  let r = splitAt 1000000 $ repeat 'a'
  print $ length $ fst r

并且使用严格的模式匹配会大大降低速度。

time ./lazy     -- 0.04s user 0.00s system 90% cpu 0.047 total
time ./strict   -- 0.12s user 0.02s system 96% cpu 0.147 total

我无法得到原因。根据文章，严格版本可能需要更多内存和所有递归调用来检查模式是否适合。但我认为惰性版本也需要所有递归调用，并且需要内存来包含递归函数调用的结果。是什么造成了这种差异？

Answer 1

有很多不同之处。

让我们看看有和没有 ~ 的变体之间的操作差异。在第 11 行。

GHC Haskell 中的评估是由模式匹配驱动的。当模式在 case 表达式或函数定义的 LHS 中匹配时，需要对模式中的构造函数进行求值。 (let 中的模式以及绑定(bind)被视为惰性模式匹配的地方。)这意味着评估 splitAt 1000000 (repeat 'a')取决于匹配 (,)递归调用 splitAt 999999 ... 产生的构造函数，依此类推，一直到最后一次调用 splitAt 0 ... .这需要堆栈空间来评估。事实上，相当多。堆栈很可能必须增长几次以避免崩溃。

此外，整个结果字符串 "aaaaa..."发生这种情况时，在 length 之前建立在堆上永远开始处理它。 (由于 repeat 中的优化，结果的第二个元素实际上是一个循环链表，它在整个递归评估中从不分配任何新的东西。)

当模式匹配变得懒惰时，事情就会改变。来自 splitAt 1000000 (repeat 'a') 的返回值被评估为 ('a':_thunk1, _thunk2)无需递归调用 splitAt .这是一种称为 protected 核心递归的模式。进一步的评估隐藏在数据构造函数后面，如 (,)和 (:) ，因此只有在另一个 case 表达式要求时才执行。

调用 fst扔掉_thunk2 ，所以它永远不会被评估。调用 length首先使用第一个 (:)构造函数，抛出 'a'值，然后对 _thunk1 进行递归调用.此时，内存中没有任何内容仍然引用(:)。构造函数，因此垃圾收集器在下一次运行时可以自由地回收它。 ('a' 值是共享的，所以仍然有指向它的指针，所以在这个过程中它既不会被收集也不会被分配。)
_thunk1 时会发生什么被评估有点微妙。它递归调用 splitAt 999999 ... .结果是 ('a':_thunk3, _thunk4) . _thunk4 没有任何保留，因此无论何时都可以免费进行垃圾收集。评价length如上所述进行。 (:)构造函数不再保存在内存中，并且可以自由收集。

评估以这种方式进行，只保留一个 (:)一次在堆上的构造函数，并且根本不消耗任何堆栈空间。而 GHC 的垃圾收集器的运行时间取决于驻留集的大小。因为最多有一个(:)构造函数驻留，在这种情况下它运行得非常快。

我怀疑在这种情况下，这就是您所看到的速度差异。您应该尝试使用参数 +RTS -s 运行这两个程序。并查看有关最大驻留大小和垃圾收集器运行时间的统计信息。

不过，GHC 可能在优化方面非常聪明。我没有检查过，但我知道在某些情况下它可以根据显式 (:) 重写算法申请条款 build 功能。如果这样做，它将允许 foldr/build fusion 删除 (:) 的分配。完全构造函数。 (是的，length 是根据 foldr 定义的，通过一些非常酷的技巧来提高效率，主要是为了让 foldr/build 融合工作。)

如果是这种情况，您会发现在惰性情况下发生的分配更少 - 但在严格情况下会同样糟糕。我认为这不太可能在这里发生，但我不确定，因为我还没有测试过。