Space 递归列表 zipWith 泄漏
Space leak with recursive list zipWith
我的 space 泄漏发生在我的一个个人项目中。但是我不希望有人在我的项目中解决它。我想了解一下。
我通过编写此算法重现了我的 space 漏洞:
u 是由以下定义的序列:
- u(0) = 1
- u(1) = 2
- u(2) = 1
- u(4) = 3
- …
- u(19) = 11
在此之后,u 被定义为:u(n) = u(n-5) + u(n-10) - u(n-15)
在 haskell 中很容易实施,对吗?
import System.Environment (getArgs)
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
++ zipWith3 go u' u'' u'''
where u' = drop 15 u
u'' = drop 10 u
u''' = drop 5 u
go a b c = a + b - c
main = do
args <- getArgs
let n = read $ args !! 0
putStrLn $ show $ u !! n
不幸的是,这个 space 泄漏:
$ time ./algo 9999999
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
1.17user 0.19system 0:01.37elapsed 100%CPU (0avgtext+0avgdata 865124maxresident)k
0inputs+0outputs (0major+215695minor)pagefaults 0swaps
看起来 haskell 正在缓存整个列表,而我希望它只缓存最后 20 个元素。
例如,这是我在 C 中的实现:
#include <stdint.h>
#include <stdio.h>
int main(int argc, char **argv)
{
size_t cursor;
int64_t buffer[20] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11};
int n = atoi(argv[1]);
for (cursor = 20; cursor <= n; cursor++) {
buffer[cursor%20] = buffer[(cursor+20-5)%20] + buffer[(cursor+20-10)%20] - buffer[(cursor+20-15)%20];
}
printf("%d\n", buffer[n%20]);
return 0;
}
$ ./a.out 9999999
5000001
我的 C 实现使用 O(n) 时间和 O(1) space。但看起来我的 haskell 实现使用的是 O(n) space.
为什么 Haskell 能够计算出 fibonnacci,但不能计算出我编造的序列?
我做错了什么?
你会如何在 Haskell 中实现这个算法?
那是堆栈溢出,但你也有 space 泄漏,这更容易用几句话解释。
当您执行索引 u !! n
时,u
看起来像
1 : 2 : 1 : ... : 11 : <go thunk> : ... : <go thunk> : <zipWith3 thunk>
然后您提取列表 u
中索引 n
处的最后一个 <go thunk>
。此时每个 <go thunk>
都引用了 u
的早期元素,因此(几乎)整个 u
必须保留在内存中(实际上不需要前五个左右的元素).
栈溢出就是为了求u的第9999999个元素,首先要求第9999994个元素,为了求值先要求第9999989个元素,等等。之后怎么办,比如说,评估第 9999994 个元素以完成对第 9999999 个元素的评估进入堆栈,并且有你的堆栈溢出(这也是一种 space 泄漏,我想)。
这两个问题都可以通过在构建列表或遍历列表时强制列表 u
的元素来解决。既然你说你不希望有人解决 space 泄漏问题,我会把那部分留作练习,尽管有一种特别巧妙且可能不那么明显的方法来做到这一点。
编辑添加:我想到的巧妙但可能过于聪明的修复只是将最后一行更改为
putStrLn $ show $ foldr ((:) $!) [] u !! n
可能了解其工作原理本身就足够了。
更直接的方法是在 max taldykin 的回答中,或者编写一个自定义索引函数,强制它在丢弃元素之前跳过它们。
这是遵循 Reid Barton 的回答的代码:
{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)
u :: [Int]
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
++ go u' u'' u'''
where u' = drop 15 u
u'' = drop 10 u
u''' = drop 5 u
go ((!a):as) ((!b):bs) ((!c):cs)
= a + b - c
: go as bs cs
它使用 BangPatterns 扩展来强制评估 thunk。 (我还添加了类型注释以使用 Int
s 而不是 Integer
s,后者更快一些。)
你可以看到它以常量 space 运行(1M in use
是输出的相关部分):
$ ./xx 99999999 +RTS -t
50000001
<<ghc: 8000065016 bytes, 15319 GCs, 36596/44312 avg/max bytes residency (2 samples), 1M in use, 0.00 INIT (0.00 elapsed), 2.82 MUT (2.78 elapsed), 0.01 GC (0.06 elapsed) :ghc>>
我的 space 泄漏发生在我的一个个人项目中。但是我不希望有人在我的项目中解决它。我想了解一下。
我通过编写此算法重现了我的 space 漏洞:
u 是由以下定义的序列:
- u(0) = 1
- u(1) = 2
- u(2) = 1
- u(4) = 3
- …
- u(19) = 11
在此之后,u 被定义为:u(n) = u(n-5) + u(n-10) - u(n-15)
在 haskell 中很容易实施,对吗?
import System.Environment (getArgs)
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
++ zipWith3 go u' u'' u'''
where u' = drop 15 u
u'' = drop 10 u
u''' = drop 5 u
go a b c = a + b - c
main = do
args <- getArgs
let n = read $ args !! 0
putStrLn $ show $ u !! n
不幸的是,这个 space 泄漏:
$ time ./algo 9999999
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
1.17user 0.19system 0:01.37elapsed 100%CPU (0avgtext+0avgdata 865124maxresident)k
0inputs+0outputs (0major+215695minor)pagefaults 0swaps
看起来 haskell 正在缓存整个列表,而我希望它只缓存最后 20 个元素。
例如,这是我在 C 中的实现:
#include <stdint.h>
#include <stdio.h>
int main(int argc, char **argv)
{
size_t cursor;
int64_t buffer[20] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11};
int n = atoi(argv[1]);
for (cursor = 20; cursor <= n; cursor++) {
buffer[cursor%20] = buffer[(cursor+20-5)%20] + buffer[(cursor+20-10)%20] - buffer[(cursor+20-15)%20];
}
printf("%d\n", buffer[n%20]);
return 0;
}
$ ./a.out 9999999
5000001
我的 C 实现使用 O(n) 时间和 O(1) space。但看起来我的 haskell 实现使用的是 O(n) space.
为什么 Haskell 能够计算出 fibonnacci,但不能计算出我编造的序列? 我做错了什么? 你会如何在 Haskell 中实现这个算法?
那是堆栈溢出,但你也有 space 泄漏,这更容易用几句话解释。
当您执行索引 u !! n
时,u
看起来像
1 : 2 : 1 : ... : 11 : <go thunk> : ... : <go thunk> : <zipWith3 thunk>
然后您提取列表 u
中索引 n
处的最后一个 <go thunk>
。此时每个 <go thunk>
都引用了 u
的早期元素,因此(几乎)整个 u
必须保留在内存中(实际上不需要前五个左右的元素).
栈溢出就是为了求u的第9999999个元素,首先要求第9999994个元素,为了求值先要求第9999989个元素,等等。之后怎么办,比如说,评估第 9999994 个元素以完成对第 9999999 个元素的评估进入堆栈,并且有你的堆栈溢出(这也是一种 space 泄漏,我想)。
这两个问题都可以通过在构建列表或遍历列表时强制列表 u
的元素来解决。既然你说你不希望有人解决 space 泄漏问题,我会把那部分留作练习,尽管有一种特别巧妙且可能不那么明显的方法来做到这一点。
编辑添加:我想到的巧妙但可能过于聪明的修复只是将最后一行更改为
putStrLn $ show $ foldr ((:) $!) [] u !! n
可能了解其工作原理本身就足够了。
更直接的方法是在 max taldykin 的回答中,或者编写一个自定义索引函数,强制它在丢弃元素之前跳过它们。
这是遵循 Reid Barton 的回答的代码:
{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)
u :: [Int]
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
++ go u' u'' u'''
where u' = drop 15 u
u'' = drop 10 u
u''' = drop 5 u
go ((!a):as) ((!b):bs) ((!c):cs)
= a + b - c
: go as bs cs
它使用 BangPatterns 扩展来强制评估 thunk。 (我还添加了类型注释以使用 Int
s 而不是 Integer
s,后者更快一些。)
你可以看到它以常量 space 运行(1M in use
是输出的相关部分):
$ ./xx 99999999 +RTS -t
50000001
<<ghc: 8000065016 bytes, 15319 GCs, 36596/44312 avg/max bytes residency (2 samples), 1M in use, 0.00 INIT (0.00 elapsed), 2.82 MUT (2.78 elapsed), 0.01 GC (0.06 elapsed) :ghc>>