我正在分析where
子句对Haskell程序性能的影响。
在Haskell, The craft of functional programming, Thomspson,第20.4章,我发现了以下例子:
exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]
exam2 :: Int -> [Int]
exam2 n = list ++ list
where list = [1 .. n]
而且,我引述,
计算[exam1]所用的时间将是
O(n)
,使用的空间将是O(1)
,但我们必须计算两次表达式[1 .. n]
。...
[exam2]的效果是计算列表
[1 .. n]
一次,以便我们在计算它之后保存它的值,以便能够再次使用它。...
如果我们通过在
where
条款中引用它来保存某些东西,我们必须支付它占据的空间的罚款。
所以我疯狂地认为-O2
旗帜必须处理这个并为我选择最佳行为。我使用Criterion分析了这两个例子的时间复杂度。
import Criterion.Main
exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]
exam2 :: Int -> [Int]
exam2 n = list ++ list
where list = [1 .. n]
m :: Int
m = 1000000
main :: IO ()
main = defaultMain [ bench "exam1" $ nf exam1 m
, bench "exam2" $ nf exam2 m
]
我用-O2
编译,并找到:
benchmarking exam1
time 15.11 ms (15.03 ms .. 15.16 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 15.11 ms (15.08 ms .. 15.14 ms)
std dev 83.20 μs (53.18 μs .. 122.6 μs)
benchmarking exam2
time 76.27 ms (72.84 ms .. 82.75 ms)
0.987 R² (0.963 R² .. 0.997 R²)
mean 74.79 ms (70.20 ms .. 77.70 ms)
std dev 6.204 ms (3.871 ms .. 9.233 ms)
variance introduced by outliers: 26% (moderately inflated)
有什么区别!那为什么会这样?我认为exam2
应该更快但内存效率低(根据上面的引用)。但不,它实际上要慢得多(可能内存效率低,但需要进行测试)。
也许它更慢,因为[1 .. 1e6]
必须存储在内存中,这需要花费很多时间。你怎么看?
PS:我找到了a possibly related question,但不是真的。
您可以使用-ddump-simpl
检查GHC Core并观察生成的优化代码GHC。 Core不像Haskell那样可读,但通常人们仍然可以了解正在发生的事情。
对于exam2
,我们得到了无聊的代码:
exam2
= \ (n_aX5 :: Int) ->
case n_aX5 of { GHC.Types.I# y_a1lJ ->
let {
list_s1nF [Dmd=<S,U>] :: [Int]
[LclId]
list_s1nF = GHC.Enum.eftInt 1# y_a1lJ } in
++ @ Int list_s1nF list_s1nF
}
粗略地说,这将list_s1nF
定义为[1..n]
(eftInt
= enum from to)并调用++
。这里没有内联。 GHC因为使用两次而害怕内联list_s1nF
,并且在这种情况下内联定义可能是有害的。事实上,如果let x = expensive in x+x
被内联,expensive
可能会被重新计算两次,这很糟糕。在这里GHC信任程序员,认为如果他们使用let / where
他们希望只计算一次。未能内联list_s1nF
阻止进一步优化。
因此,此代码分配list = [1..n]
,然后复制导致1:2:...:n:list
,其中尾部指针指向原始列表。复制任意列表需要遵循指针链并为新列表分配单元格,这比[1..n]
更直观,exam1
只需要为新列表分配单元格并保持计数器。
相反,exam1
= \ (w_s1os :: Int) ->
case w_s1os of { GHC.Types.I# ww1_s1ov ->
PerfList.$wexam1 ww1_s1ov
}
进一步优化:经过一些小的拆箱后
PerfList.$wexam1
= \ (ww_s1ov :: GHC.Prim.Int#) ->
let {
n_a1lT :: [Int]
[LclId]
n_a1lT = GHC.Enum.eftInt 1# ww_s1ov } in
case GHC.Prim.># 1# ww_s1ov of {
__DEFAULT ->
letrec {
go_a1lX [Occ=LoopBreaker] :: GHC.Prim.Int# -> [Int]
[LclId, Arity=1, Str=<L,U>, Unf=OtherCon []]
go_a1lX
= \ (x_a1lY :: GHC.Prim.Int#) ->
GHC.Types.:
@ Int
(GHC.Types.I# x_a1lY)
(case GHC.Prim.==# x_a1lY ww_s1ov of {
__DEFAULT -> go_a1lX (GHC.Prim.+# x_a1lY 1#);
1# -> n_a1lT
}); } in
go_a1lX 1#;
1# -> n_a1lT
}
我们得到了实际的工人功能。
[1..n]
在这里,第一个“enum to to”++
被内联,这也引发了go_a1lX
的内联。由此产生的递归函数:
仅依赖于n_a1lT
和基本算术。当递归结束时,返回[1..n]
,这是exam3 :: Int -> [Int]
exam3 n = list1 ++ list2
where list1 = [1 .. n]
list2 = [1 .. n]
的第二个“枚举”。这没有内联,因为它不会触发更多优化。
这里,没有生成列表然后复制,因此我们获得了更好的性能。
请注意,这也会产生优化的代码:
exam4 :: Int -> [Int]
exam4 n = list () ++ list ()
where list () = [1 .. n]
除此之外,由于GHC不会自动缓存函数的结果,因此可以内联。
qazxswpoi