optimization - Haskell 基准测试/优化非严格归约的 nf/whnf

Question

我正在尝试优化一个旨在获取大型数据集的库，并且
然后对其应用不同的操作。现在图书馆正在工作，我想要
来优化它。

我的印象是非严格评估允许
GHC 组合操作，以便数据只迭代一次
编写函数的顺序，以便对参数进行排序以促进 whnf 减少。
(并可能减少对每个数据执行的操作数量)

为了测试这一点，我编写了以下代码:

import Criterion.Main

main = defaultMain
       [ bench "warmup (whnf)" $ whnf putStrLn "HelloWorld",
         bench "single (whnf)" $ whnf single [1..10000000],
         bench "single (nf)"   $ nf   single [1..10000000],
         bench "double (whnf)" $ whnf double [1..10000000],
         bench "double (nf)"   $ nf   double [1..10000000]]

single :: [Int] -> [Int]
single lst = fmap (* 2) lst

double :: [Int] -> [Int]             
double lst =  fmap (* 3) $ fmap (* 2) lst

使用 Criterion 库进行基准测试，我得到以下结果:

benchmarking warmup (whnf)
mean: 13.72408 ns, lb 13.63687 ns, ub 13.81438 ns, ci 0.950
std dev: 455.7039 ps, lb 409.6489 ps, ub 510.8538 ps, ci 0.950

benchmarking single (whnf)
mean: 15.88809 ns, lb 15.79157 ns, ub 15.99774 ns, ci 0.950
std dev: 527.8374 ps, lb 458.6027 ps, ub 644.3497 ps, ci 0.950

benchmarking single (nf)
collecting 100 samples, 1 iterations each, in estimated 107.0255 s
mean: 195.4457 ms, lb 195.0313 ms, ub 195.9297 ms, ci 0.950
std dev: 2.299726 ms, lb 2.006414 ms, ub 2.681129 ms, ci 0.950

benchmarking double (whnf)
mean: 15.24267 ns, lb 15.17950 ns, ub 15.33299 ns, ci 0.950
std dev: 384.3045 ps, lb 288.1722 ps, ub 507.9676 ps, ci 0.950

benchmarking double (nf)
collecting 100 samples, 1 iterations each, in estimated 20.56069 s
mean: 205.3217 ms, lb 204.9625 ms, ub 205.8897 ms, ci 0.950
std dev: 2.256761 ms, lb 1.590083 ms, ub 3.324734 ms, ci 0.950

GHC 是否优化了“double”功能，使得列表只有
由 (* 6) 操作一次？ nf 结果表明情况确实如此，因为
否则“double”的平均计算时间将是“single”的两倍

有什么区别让whnf版本跑得这么快？我可以
只假设实际上没有执行任何操作(或者只是第一个
减少中的迭代)

我什至使用了正确的术语吗？

Answer 1

使用 -ddump-simpl 查看 GHC 生成的核心(中间代码)选项，我们可以确认GHC确实融合了map的两个应用。合二为一(使用 -O2 )。转储的相关部分是:

Main.main10 :: GHC.Types.Int -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs]
Main.main10 =
  \ (x_a1Ru :: GHC.Types.Int) ->
    case x_a1Ru of _ { GHC.Types.I# x1_a1vc ->
    GHC.Types.I# (GHC.Prim.*# (GHC.Prim.+# x1_a1vc 2) 3)
    }

Main.double :: [GHC.Types.Int] -> [GHC.Types.Int]
GblId
[Arity 1
 NoCafRefs
 Str: DmdType S]
Main.double =
  \ (lst_a1gF :: [GHC.Types.Int]) ->
    GHC.Base.map @ GHC.Types.Int @ GHC.Types.Int Main.main10 lst_a1gF

注意 GHC.Base.map 只有一种用法在 Main.double ，引用组合函数 Main.main10它既加 2 又乘以 3。这可能是 GHC 首先内联 Functor 的结果。列表的实例，以便 fmap变成 map ，然后 applying a rewrite rule允许两个应用程序 map被融合，加上一些更多的内联和其他优化。

WHNF 意味着该表达式仅计算为“最外层”数据构造函数或 lambda。在这种情况下，这意味着第一个 (:)构造函数。这就是为什么它要快得多的原因，因为几乎没有任何工作正在完成。查看我对 What is Weak Head Normal Form? 的回答更多细节。