algorithm - haskell 垃圾收集器

Question

我有一个简单的玩具示例，它似乎与垃圾收集器在可以回收哪些数据结构(也称为内存泄漏)方面存在分歧。我并不是想提出该算法的内存效率更高的版本(这里有更好的算法的一个很好的集合: Haskell Wiki - Prime numbers ，而是解释为什么垃圾收集器没有识别旧的、超出范围和未使用的部分)列表以回收该内存。

代码在这里:

import Data.List (foldl')

erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
    | c < x = (x,y) : erat' (c,b) xs
    | c == x = (x+y,y) : erat' (c,True) xs
    | c > x = (x+y,y) : erat' (c,b) xs
erat' (c,b) []
    | b = []
    | otherwise = [(c,c)]

erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []

primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]

本质上，用正整数调用 primes 将返回直到并包括该数字的所有素数的列表。素数对及其高水位倍数的列表以及包含候选值和 bool 值的对(对于素数为 False，对于非素数为 True)传递给erat'。对erat'的每个非递归调用都会传递一个新列表，并且我希望输出最多包含从列表开头到第一次更改点的某些共享单元。

一旦传递给erat'的列表中的修改单元超出范围，内存就应该被标记为可恢复，但是正如您在尝试使用足够大的数字(例如1,000,000，例如1,000,000)调用素数时所看到的)，内存利用率可以迅速飙升至数十GB。

现在的问题是:为什么会发生这种情况？分代垃圾收集器不应该检测取消引用的列表单元来回收它们吗？而且，它应该很容易检测到它们没有引用，因为:

a) 没有任何东西可以引用比自身更老的数据结构； b)不能有更新的引用，因为这些单元格/片段甚至不再是可引用数据结构的一部分，因为它超出了范围？

当然，可变数据结构可以解决这个问题，但我觉得在这种情况下诉诸可变性会放弃 Haskell 的一些理论原则。

感谢发表评论的人(特别是卡尔)，我稍微修改了算法以增加严格性(以及开始穿过新素数的平方的优化，因为较低的倍数也会被较低素数的倍数交叉)。

这是新版本:

import Data.List (foldl')

erat' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat' (c,b) ((x,y):xs)
    | c < x = x `seq` (x,y) : erat' (c,b) xs
    | c == x = x `seq` (x+y,y) : erat' (c,True) xs
    | c > x = x `seq` (x+y,y) : erat' (c,b) xs
erat' (c,b) []
    | b = []
    | otherwise = [(c*c,c)] -- lower multiples would be covered by multiples of lower primes

erat :: [Integer] -> [(Integer,Integer)]
erat = foldl' (\a c -> erat' (c,False) a) []

primes :: Integer -> [Integer]
primes n = map snd $ erat [2..n]

内存消耗似乎仍然相当大。此算法是否有任何其他更改可以帮助降低总内存利用率？

由于威尔指出我没有提供完整的统计数据，因此这些是上面列出的素数更新版本的运行数字，以 100000 作为参数:

应用威尔建议的更改后，内存使用量现在大幅下降。例如，再次查看 100000 的素数运行:

最后，这是合并建议的更改后的最终代码:

import Data.List (foldl')

erat'' :: (Integer, Bool) -> [(Integer,Integer)] -> [(Integer,Integer)]
erat'' (c,b) ((x,y):xs)
    | c < x  = (x,  y) : if x==y*y then (if b then xs 
                                              else xs++[(c*c,c)])
                                   else erat'' (c,b)    xs 
    | c == x = (x+y,y) : if x==y*y then            xs 
                                   else erat'' (c,True) xs 
    | c > x  = (x+y,y) : erat'' (c,b)    xs 
erat'' (c,True)  [] = []
erat'' (c,False) [] = [(c*c,c)]


primes'' :: Integer -> [Integer]
primes'' n = map snd $ foldl' (\a c -> (if null a then 0 else 
        case last a of (x,y) -> y) `seq` erat'' (c,False) a) [] [2..n]

最后运行 1,000,000 次来感受一下这个新版本的性能:

Answer 1

在存在懒惰的情况下，假设 a) 是错误的。事实上，您的代码几乎完全由生成旧 cons 单元指向的 cons 单元组成。 erat' 使用一个列表元素，然后生成一个指向元组的 (:) 构造函数和一个未计算 thunk，它将执行递归调用埃拉特'。只有当稍后评估该 thunk 时，(:) 列表构造函数才会真正将其尾部作为数据结构指向。所以，是的，您在 erat' 中分配的几乎每个 (:) 实际上都是向前指向时间的。 (唯一的异常(exception)是最后一个 - [foo] 将在其 (:) 时指向预先存在的 [] 构造函数构造函数已分配。)

假设 b) 在懒惰的情况下是无稽之谈。范围决定 Haskell 中的可见性，而不是生命周期。生命周期取决于评估和可达性。

因此，运行时发生的事情是您在 erat 中构建 erat' 调用管道。他们中的每一个都保留着已评估的尽可能多的输入，并慢慢地消耗它。有趣的是，您的代码不会提前评估任何内容 - 看起来它实际上应该流得很好 - 除了管道太深这一事实。创建的管道大约有 n 个阶段 - 这是(低效!)试除法，而不是埃拉托斯特尼筛法。您应该只将质数添加到管道中，而不是每个数字。