2

我正在尝试不同的方法来获取斐波那契数列的给定索引处的数字，它们基本上可以分为两类：

  • 建立一个列表并查询一个索引
  • 使用变量（可能是单独的或元组的，没有列表）

我选择了两者的一个例子：

fibs1 :: Int -> Integer
fibs1 n = fibs1' !! n
    where fibs1' = 0 : scanl (+) 1 fibs1'

fib2 :: Int -> Integer
fib2 n = fib2' 1 1 n where
    fib2' _ b 2 = b
    fib2' a b n = fib2' b (a + b) (n - 1)

谎言1：

real    0m2.356s
user    0m2.310s
sys     0m0.030s

谎言2：

real    0m0.671s
user    0m0.667s
sys     0m0.000s

两者均使用 64 位 GHC 7.6.1 和-O2 -fllvm. 它们的核心转储长度非常相似，但它们在我不太擅长解释的部分上有所不同。

fibs1对于 n = 350000 ( Stack space overflow)失败，我并不感到惊讶。但是，我对它使用了这么多内存这一事实感到不舒服。

我想澄清一些事情：

  1. 为什么 GC 在整个计算过程中不处理列表的开头，即使其中大部分很快变得无用？
  2. 为什么 GHC 不将列表版本优化为可变版本，因为一次只需要两个元素？

编辑：对不起，我混合了速度结果，修复了。不过，我的三个疑问中有两个仍然有效；）。

4

1 回答 1

4

为什么 GC 在整个计算过程中不处理列表的开头，即使其中大部分很快变得无用？

fibs1使用大量内存并且很慢，因为scanl它很懒，它不评估列表元素，所以

fibs1' = 0 : scanl (+) 1 fibs1'

生产

0 : scanl (+) 1 (0 : more)
0 : 1 : let f2 = 1+0 in scanl (+) f2 (1 : more')
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in scanl (+) f3 (f2 : more'')
0 : 1 : let f2 = 1+0 in f2 : let f3 = f2+1 in f3 : let f4 = f3+f2 in scanl (+) f4 (f3 : more''')

等等，所以你很快就会得到一个巨大的嵌套重击。当这个 thunk 被评估时，它被压入堆栈，在 250000 到 350000 之间的某个点，它对于默认堆栈来说变得太大了。

并且由于每个列表元素在未评估时都包含对前一个元素的引用，因此无法对列表的开头进行垃圾收集。

如果您使用严格的扫描，

fibs1 :: Int -> Integer
fibs1 n = fibs1' !! n
  where
    fibs1' = 0 : scanl' (+) 1 fibs1'
    scanl' f a (x:xs) = let x' = f a x in x' `seq` (a : scanl' f x' xs)
    scanl' _ a [] = [a]

当第k-th 个列表单元产生时，它的值已经被评估，所以不引用先前的，因此列表可以被垃圾收集（假设没有其他东西持有对它的引用），因为它被遍历。

通过该实现，列表版本大约与fib2（它仍然需要分配列表单元格，因此它分配更多一点，因此可能会慢一点，但差异很小，因为斐波那契数变得如此之大以至于列表构造开销变得可以忽略不计）。

的想法scanl是，它的结果是增量消耗的，因此消耗会强制元素并防止大型 thunk 的积累。

为什么 GHC 不将列表版本优化为可变版本，因为一次只需要两个元素？

它的优化器无法看穿算法来确定这一点。scanl对编译器是不透明的，它不知道做什么scanl。

如果我们采用确切的源代码scanl（重命名或隐藏scanl前奏曲，我选择重命名），

scans                   :: (b -> a -> b) -> b -> [a] -> [b]
scans f q ls            =  q : (case ls of
                                []   -> []
                                x:xs -> scans f (f q x) xs)

并编译导出它的模块（使用-O2），然后查看生成的接口文件

ghc --show-iface Scan.hi

我们得到（例如，编译器版本之间的细微差别）

Magic: Wanted 33214052,
       got    33214052
Version: Wanted [7, 0, 6, 1],
         got    [7, 0, 6, 1]
Way: Wanted [],
     got    []
interface main:Scan 7061
  interface hash: ef57dac14815e2f1f897b42a007c0c81
  ABI hash: 8cfc8dab79de6a51fcad666f1869574f
  export-list hash: 57d6805e5f0b5f76f0dd8dfb228df988
  orphan hash: 693e9af84d3dfcc71e640e005bdc5e2e
  flag hash: 1e8135cb44ef6dd330f1f56943d1f463
  used TH splices: False
  where
exports:
  Scan.scans
module dependencies:
package dependencies: base* ghc-prim integer-gmp
orphans: base:GHC.Base base:GHC.Float base:GHC.Real
family instance modules:
import  -/  base:Prelude 1cb4b618cf45281dc97748b1831bf0cd
d79ca4e223c0de0a770a3b88a5e67687
  scans :: forall b a. (b -> a -> b) -> b -> [a] -> [b]
    {- Arity: 3, HasNoCafRefs, Strictness: LLL -}
vectorised variables:
vectorised tycons:
vectorised reused tycons:
scalar variables:
scalar tycons:
trusted: safe-inferred
require own pkg trusted: False

并且看到接口文件没有暴露函数的展开，只有它的类型、数量、严格性，并且它没有引用 CAF。

当一个模块导入被编译时，编译器所要做的就是接口文件暴露的信息。

在这里，除了发出对函数的调用外，没有任何信息可以允许编译器执行任何其他操作。

如果展开被暴露，编译器就有机会内联展开并分析知道类型和组合函数的代码，以生成更多不构建 thunk 的急切代码。

然而，的语义scanl是最大的惰性，输出的每个元素都是在检查输入列表之前发出的。这导致 GHC 不能使添加变得严格，因为如果列表包含任何未定义的值，这会改变结果：

scanl (+) 1 [undefined] = 1 : scanl (+) (1 + undefined) [] = 1 : (1 + undefined) : []

尽管

scanl' (+) 1 [undefined] = let x' = 1 + undefined in x' `seq` 1 : scanl' (+) x' []
                         = *** Exception: Prelude.undefined

可以做一个变种

scanl'' f b (x:xs) = b `seq` b : scanl'' f (f b x) xs

这将为1 : *** Exception: Prelude.undefined上述输入产生，但如果列表包含未定义的值，任何严格性确实会改变结果，因此即使编译器知道展开，它也无法使评估严格 - 除非它可以证明没有未定义列表中的值，这一事实对我们来说是显而易见的，但编译器却不是[而且我认为教编译器认识到这一点并能够证明不存在未定义的值并不容易]。

于 2012-12-06T21:25:41.880 回答