gpt4 book ai didi

performance - haskell ; where子句的执行

转载 作者:行者123 更新时间:2023-12-04 14:53:47 26 4
gpt4 key购买 nike

我在分析 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]
而且,我引用,

The time taken to calculate [exam1] will be O(n), and the space used will be O(1), but we will have to calculate the expression [1 .. n] twice.

...

The effect [of exam2] is to compute the list [1 .. n] once, so that we save its value after calculating it in order to be able to use it again.

...

If we save something by referring to it in a where clause, we have to pay the penalty of the space that it occupies.


所以我发疯了,认为 -O2 flag 必须处理这个问题并为我选择最佳行为。我使用 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 = 枚举 f​​rom 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
}

在这里,第一个“枚举 from to” [1..n]被内联了,这也触发了 ++ 的内联。 .生成的递归函数 go_a1lX仅依赖于 :和基本算术。当递归结束时, n_a1lT返回第二个“从到的枚举” [1..n] .这不是内联的,因为它不会触发更多优化。

在这里,没有生成列表然后复制,因此我们获得了更好的性能。

请注意,这也会产生优化的代码:
exam3 :: Int -> [Int]
exam3 n = list1 ++ list2
where list1 = [1 .. n]
list2 = [1 .. n]

除此之外,由于 GHC 不会自动缓存函数的结果,因此可以内联。
exam4 :: Int -> [Int]
exam4 n = list () ++ list ()
where list () = [1 .. n]

关于performance - haskell ; where子句的执行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55902855/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com