performance - Haskell 在生成斐波那契数时(看似)随机暂停

Question

我在玩 GHCI，遇到了这个(对我来说)奇怪的小东西。

我试过这个:

λ> let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
λ> fibs

只是为了看看谣言的增长速度有多快，只是想玩一下。我认为 Haskell 在计算时显示每个 fib 的方式很酷，所以这是懒惰的一个很好的证明。

然而，当我看到数字墙放大时，列表生成会完全停止的瞬间跳过。通常我会认为它正在计算下一个数字，但它们似乎是随机发生的 - 计算下一个 fib 数字总是只是一个加法，所以不应该很慢。在一个数字上，ghci 停顿了将近一秒钟。

是什么导致了这些暂时的减速？为什么它们只会发生在特定的数字上而不是其他数字上？这不应该总是很快吗？

Answer 1

这几乎可以肯定是垃圾收集 (GC)，可能是更高代(即主要 GC)。在创建大量长期存在的垃圾的情况下，这些可能会导致严重的暂停。

如果您想看到这种情况发生，您可以制作一个快速的可执行文件并检查:

从 tmp.hs 开始:

module Main where

fibs = 1:1:zipWith (+) fibs (tail fibs)

main = print $ fibs !! 100000

编译 ghc -rtsopts tmp.hs
运行 ./tmp +RTS -s

     454,847,088 bytes allocated in the heap
     230,044,816 bytes copied during GC
       4,291,856 bytes maximum residency (226 sample(s))
      18,080,904 bytes maximum slop
              56 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       676 colls,     0 par    0.07s    0.07s     0.0001s    0.0023s
  Gen  1       226 colls,     0 par    0.27s    0.28s     0.0012s    0.0084s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.14s  (  0.14s elapsed)
  GC      time    0.34s  (  0.35s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.48s  (  0.49s elapsed)

  %GC     time      71.0%  (71.6% elapsed)

  Alloc rate    3,303,664,644 bytes per MUT second

  Productivity  28.9% of total user, 28.8% of total elapsed

这意味着 676 次次要垃圾收集和 226 次主要垃圾收集，第二代收集比次要收集花费的时间多约 12 倍。请注意，这只是第 10 万个数字，因此在更高的数字处暂停可能会更长。另请注意，GHCI 是一个解释器，因此会出现相关的减速。

顺便说一句，我确实尝试在打开优化的情况下编译和运行此示例。时间上没有明显差异，内存/GC 特性几乎相同。