为什么lazy模式匹配splitAt函数的版本更快？

问题描述：

该splitAt功能可以被实现为以下的（https://wiki.haskell.org/Lazy_pattern_match）：为什么lazy模式匹配splitAt函数的版本更快？

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

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

答

有一堆的差异。

让我们看到的变体之间的操作差别有和没有~上线11

评价GHC Haskell是通过模式匹配来驱动。当模式在函数定义的case表达式或LHS中匹配时，它要求对模式中的构造函数进行求值。（在让图案和where绑定被视为懒惰的模式相匹配。）因此，这意味着评估splitAt 1000000 (repeat 'a')取决于匹配(,)构造由递归调用产生于splitAt 999999 ...，依此类推，下至splitAt 0 ...最后调用的所有道路。这需要堆栈空间进行评估。事实上，它其实很多。为了避免崩溃，堆栈必须多次生长才有可能。

此外，整个结果字符串"aaaaa..."是建立在堆上，而这种情况正在发生，之前曾经length开始对其进行处理。（由于repeat中的优化，结果的第二个元素实际上是一个循环链表，它在整个递归评估中从不分配任何新内容。）

当模式匹配变得很懒时，事情就会改变。来自splitAt 1000000 (repeat 'a')的返回值被评估为('a':_thunk1, _thunk2)，而没有对splitAt进行递归调用。这是一种被称为守护核心的模式。进一步的评估隐藏在像(,)和(:)这样的数据构造器后面，因此只有在另一个案例表达式要求时才会执行。

致电fst丢掉_thunk2，所以它永远不会被评估。通过消耗第一(:)构造，扔出去的'a'值，然后在_thunk1作出递归调用length开始呼叫。此时，内存中没有任何东西仍然指向构造函数(:)，所以垃圾收集器可以在下一次运行时*回收它。（'a'的值是共享的，所以仍有指向它的指针，所以在此过程中它既不被收集也不被分配。）

当_thunk1被评估时会发生什么有点微妙。它会递归调用splitAt 999999 ...。结果为('a':_thunk3, _thunk4)。 _thunk4没有任何东西，所以随时都可以随意收集垃圾。如上所述进行length的评估。构造函数(:)不再存储在内存中，可以*收集。

评估以这种方式进行，只有一次持有堆上的单个构造函数(:)，并且根本不烧任何堆栈空间。 GHC的垃圾收集器的运行时间取决于驻留集的大小。因为最多只有一个(:)构造函数驻留，所以在这种情况下它确实快速地变为。

我怀疑在这种情况下，这是你看到的速度差异。您应该尝试运行这两个程序，其参数为+RTS -s，并查看关于最大常驻大小和垃圾收集器运行时间的统计信息。尽管如此，有可能GHC在真的是巧妙的优化。我没有检查过它，但是我知道在某些情况下，它可以根据build函数根据显式(:)应用程序重写算法。如果这样做，它将允许foldr/build融合，完全删除构造函数的分配。（是的，length是在foldr方面通过提高效率一些很酷的技巧定义，主要是为了让foldr相似/建立融合工作。）

如果是这样的话，你会发现更小的分配发生在偷懒案件 - 但严格的情况会一样糟糕。我不认为这可能会发生在这里，但我不确定，因为我没有测试过。

为什么lazy模式匹配splitAt函数的版本更快？

相关推荐