为什么延迟模式匹配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和where模式中的模式被视为惰性模式匹配.)这意味着评估splitAt 1000000 (repeat 'a')依赖于匹配(,)由递归调用产生的构造函数splitAt 999999 ...,依此类推,一直到最终调用splitAt 0 ....这需要堆栈空间来评估.事实上,相当多.堆栈很可能需要多次生长以避免崩溃.

此外,在开始处理"aaaaa..."之前,整个结果字符串都是在堆上构建的length.(由于优化repeat,结果的第二个元素实际上是一个循环链表,它从不在整个递归计算中分配任何新的东西.)

当模式匹配变得懒惰时,事情会发生变化.返回值splitAt 1000000 (repeat 'a')被评估为('a':_thunk1, _thunk2)没有进行递归调用splitAt.这是一种被称为保护的核心运动的模式.进一步的评估隐藏在像(,)和的数据构造函数之后(:),因此只有在另一个案例表达式要求时才执行.

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 fusion工作.)

如果是这种情况,你会发现在懒惰情况下发生的分配更少 - 但严格的情况也同样糟糕.我不认为这可能发生在这里,但我不确定,因为我没有测试过.