Haskell State monad vs state 作为参数性能测试
Haskell State monad vs state as parameter performance test
我开始学习 State Monad,一个想法困扰着我。我们可以将所有内容包装到状态 monad,而不是将累加器作为参数传递。
所以我想比较使用 State monad 与将其作为参数传递之间的性能。
所以我创建了两个函数:
sum1 :: Int -> [Int] -> Int
sum1 x [] = x
sum1 x (y:xs) = sum1 (x + y) xs
和
sumState:: [Int] -> Int
sumState xs = execState (traverse f xs) 0
where f n = modify (n+)
我在输入数组 [1..1000000000] 上比较了它们。
- sumState 运行时间在15s左右
- sum1 5s左右
我们可以看到明显的赢家,但我意识到 sumState 可以优化为:
- 我们可以使用严格版本的修改
- 我们不需要地图列表输出,所以我们可以使用traverse_代替
所以新的优化状态函数是:
sumState:: [Int] -> Int
sumState xs = execState (traverse_ f xs) 0
where f n = modify' (n+)
运行 时间大约为 350 毫秒。这是一个巨大的进步。太震撼了。
为什么修改后的sumState比sum1有更好的性能? sum1 是否可以优化以匹配甚至优于 sumState?
我还尝试了 sum as
的其他不同实现
- 使用内置的 sum 函数,这给了我大约 240ms ((sum [1..x] ::Int))
- 使用严格的 foldl',这在 240 毫秒左右给出了相同的结果(使用隐式 [Int] -> Int)
这是否意味着使用 foldl 函数或 State monad 传递累加器而不是将其作为参数传递给函数更好?
感谢您的帮助。
编辑:
每个函数都在单独的文件中,具有自己的主要函数,并使用“-O2”标志编译。
main = do
x <- (read . head ) <$> getArgs
print $ <particular sum function> [1..x]
运行时间是通过 linux.
上的 time 命令测得的
更多解释为什么 traverse
较慢:traverse f xs
具有类型 State [()]
并且构建了 [()]
(单位元组列表)在求和期间上升。如果您不使用惰性状态,这会阻止进一步的优化并导致内存泄漏。
更新:我认为 GHC 应该能够注意到单元元组列表从未被使用过,所以我打开了 a GHC issue。
在这两种情况下,为了获得最佳性能,我们希望将求和与枚举 [1..x]
合并(或融合)到一个紧密的递归循环中,该循环简单地递增并相加,直到达到 x
.生成的代码看起来像这样:
sumFromTo :: Int -> Int -> Int -> Int
sumFromTo s x y
| x == y = s + x
| otherwise = sumFromTo (s + x) (x + 1) y
这避免了对列表 [1..x]
的分配。
base
库使用 foldr/build
融合(也称为快捷方式融合)实现此优化。 sum
、foldl'
和 traverse
(对于列表)函数是使用 foldr
函数实现的,[1..x]
是使用 build
函数实现的。 foldr
和 build
函数具有特殊的优化规则,因此可以将它们融合。您的自定义 sum1
函数不使用 foldr
,因此它永远不能以这种方式与 [1..x]
融合。
具有讽刺意味的是,困扰您实施 sumState
的同样问题也是 sum1
的问题。你没有严格的积累,所以你像这样建立thunks:
sum 0 [1, 2, 3]
sum (0 + 1) [2, 3]
sum ((0 + 1) + 2) [3]
sum (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3)
((1 + 2) + 3)
(3 + 3)
6
如果您对 sum1
添加严格性,您应该会看到效率的显着提高,因为您消除了 thunk (((0 + 1) + 2) + 3)
的非尾递归评估,这是 [= 的昂贵部分=12=]。使用严格累加使这更有效:
sum1 x [] = []
sum1 x (y : xs) = x `seq` sum1 (x + y) xs
应该可以为您提供与 sum
相当的性能(尽管如另一个答案所述,GHC 可能无法正确使用融合来为您提供列表中 sum
的真正神奇性能 [1..x]
).
我开始学习 State Monad,一个想法困扰着我。我们可以将所有内容包装到状态 monad,而不是将累加器作为参数传递。
所以我想比较使用 State monad 与将其作为参数传递之间的性能。
所以我创建了两个函数:
sum1 :: Int -> [Int] -> Int
sum1 x [] = x
sum1 x (y:xs) = sum1 (x + y) xs
和
sumState:: [Int] -> Int
sumState xs = execState (traverse f xs) 0
where f n = modify (n+)
我在输入数组 [1..1000000000] 上比较了它们。
- sumState 运行时间在15s左右
- sum1 5s左右
我们可以看到明显的赢家,但我意识到 sumState 可以优化为:
- 我们可以使用严格版本的修改
- 我们不需要地图列表输出,所以我们可以使用traverse_代替
所以新的优化状态函数是:
sumState:: [Int] -> Int
sumState xs = execState (traverse_ f xs) 0
where f n = modify' (n+)
运行 时间大约为 350 毫秒。这是一个巨大的进步。太震撼了。
为什么修改后的sumState比sum1有更好的性能? sum1 是否可以优化以匹配甚至优于 sumState?
我还尝试了 sum as
的其他不同实现- 使用内置的 sum 函数,这给了我大约 240ms ((sum [1..x] ::Int))
- 使用严格的 foldl',这在 240 毫秒左右给出了相同的结果(使用隐式 [Int] -> Int)
这是否意味着使用 foldl 函数或 State monad 传递累加器而不是将其作为参数传递给函数更好?
感谢您的帮助。
编辑:
每个函数都在单独的文件中,具有自己的主要函数,并使用“-O2”标志编译。
main = do
x <- (read . head ) <$> getArgs
print $ <particular sum function> [1..x]
运行时间是通过 linux.
上的 time 命令测得的更多解释为什么 traverse
较慢:traverse f xs
具有类型 State [()]
并且构建了 [()]
(单位元组列表)在求和期间上升。如果您不使用惰性状态,这会阻止进一步的优化并导致内存泄漏。
更新:我认为 GHC 应该能够注意到单元元组列表从未被使用过,所以我打开了 a GHC issue。
在这两种情况下,为了获得最佳性能,我们希望将求和与枚举 [1..x]
合并(或融合)到一个紧密的递归循环中,该循环简单地递增并相加,直到达到 x
.生成的代码看起来像这样:
sumFromTo :: Int -> Int -> Int -> Int
sumFromTo s x y
| x == y = s + x
| otherwise = sumFromTo (s + x) (x + 1) y
这避免了对列表 [1..x]
的分配。
base
库使用 foldr/build
融合(也称为快捷方式融合)实现此优化。 sum
、foldl'
和 traverse
(对于列表)函数是使用 foldr
函数实现的,[1..x]
是使用 build
函数实现的。 foldr
和 build
函数具有特殊的优化规则,因此可以将它们融合。您的自定义 sum1
函数不使用 foldr
,因此它永远不能以这种方式与 [1..x]
融合。
具有讽刺意味的是,困扰您实施 sumState
的同样问题也是 sum1
的问题。你没有严格的积累,所以你像这样建立thunks:
sum 0 [1, 2, 3]
sum (0 + 1) [2, 3]
sum ((0 + 1) + 2) [3]
sum (((0 + 1) + 2) + 3) []
(((0 + 1) + 2) + 3)
((1 + 2) + 3)
(3 + 3)
6
如果您对 sum1
添加严格性,您应该会看到效率的显着提高,因为您消除了 thunk (((0 + 1) + 2) + 3)
的非尾递归评估,这是 [= 的昂贵部分=12=]。使用严格累加使这更有效:
sum1 x [] = []
sum1 x (y : xs) = x `seq` sum1 (x + y) xs
应该可以为您提供与 sum
相当的性能(尽管如另一个答案所述,GHC 可能无法正确使用融合来为您提供列表中 sum
的真正神奇性能 [1..x]
).