Haskell 中的迭代和垃圾收集
iterate and garbage collection in Haskell
我有一个关于 GHC 如何实现简单代码的问题。一个性能问题,也是一个技术问题。
这是 John Hughes 的“为什么函数式编程很重要”一文中的一个简单示例。平方根计算。
要进行计算,我们需要先前的近似值,我们可以使用迭代函数来创建具有近似值的列表:
[a0, f(a0), f(f(a0), ...] 等等
然后within它方便的时候就停了:
within eps (a:b:xs) = if abs(a-b) < eps then b else within eps (b:xs)
问题是这是如何以常量 space 执行的?
GC 是否知道在递归调用中,within eps (b: xs)
列表的头部 a
不再在范围内,然后被收集?
如果是这种情况,那么在每次迭代中,GHC 是否总是会创建然后销毁内存中的一个位置(变量)?这怎么能像在变量总是被重用的过程语言中一样好呢?
Does the GC know in the recursive call, within eps (b: xs)
that head a
of the list is no longer in scope and then it is collected?
正确。
If this is the case, then at each iteration, would the GHC always create and then destroy a location in memory (variable)?
对于这个例子,几乎可以肯定是的。在某些情况下,列表融合可以将基于列表的算法变成紧密的、非分配的循环;如果您仅使用内置函数来生成和使用列表,则最有可能发生这种情况。
how can this perform as well as in a procedural language where the variable is always reused?
分配器和 GC 已针对进行大量分配和收集进行了调整。通常分配只是碰撞一个指针。偶尔你会遇到 GC,但只有一个 Float
需要从第一代复制到第二代(或者只需要一个 Float
和一些闭包或其他什么——你明白了,大部分不需要触及数据,因为它无法访问),这同样非常便宜。显然会有一些开销,但通常您所做的计算非常复杂,需要花费大部分 运行 时间。
我有一个关于 GHC 如何实现简单代码的问题。一个性能问题,也是一个技术问题。
这是 John Hughes 的“为什么函数式编程很重要”一文中的一个简单示例。平方根计算。
要进行计算,我们需要先前的近似值,我们可以使用迭代函数来创建具有近似值的列表:
[a0, f(a0), f(f(a0), ...] 等等
然后within它方便的时候就停了:
within eps (a:b:xs) = if abs(a-b) < eps then b else within eps (b:xs)
问题是这是如何以常量 space 执行的?
GC 是否知道在递归调用中,within eps (b: xs)
列表的头部 a
不再在范围内,然后被收集?
如果是这种情况,那么在每次迭代中,GHC 是否总是会创建然后销毁内存中的一个位置(变量)?这怎么能像在变量总是被重用的过程语言中一样好呢?
Does the GC know in the recursive call, within
eps (b: xs)
that heada
of the list is no longer in scope and then it is collected?
正确。
If this is the case, then at each iteration, would the GHC always create and then destroy a location in memory (variable)?
对于这个例子,几乎可以肯定是的。在某些情况下,列表融合可以将基于列表的算法变成紧密的、非分配的循环;如果您仅使用内置函数来生成和使用列表,则最有可能发生这种情况。
how can this perform as well as in a procedural language where the variable is always reused?
分配器和 GC 已针对进行大量分配和收集进行了调整。通常分配只是碰撞一个指针。偶尔你会遇到 GC,但只有一个 Float
需要从第一代复制到第二代(或者只需要一个 Float
和一些闭包或其他什么——你明白了,大部分不需要触及数据,因为它无法访问),这同样非常便宜。显然会有一些开销,但通常您所做的计算非常复杂,需要花费大部分 运行 时间。