47

在纯函数式语言中，数据是不可变的。使用引用计数，创建引用循环需要更改已创建的数据。似乎纯函数式语言可以使用引用计数而不必担心循环的可能性。是对的吗？如果是这样，他们为什么不呢？

我知道在许多情况下引用计数比 GC 慢，但至少它减少了暂停时间。在暂停时间不好的情况下，可以选择使用引用计数。

4

6 回答 6

30

相对于 Java 和 C# 等其他托管语言，纯函数式语言的分配非常疯狂。它们还分配不同大小的对象。已知最快的分配策略是从连续的空闲空间（有时称为“托儿所”）进行分配，并保留一个硬件寄存器以指向下一个可用的空闲空间。从堆分配变得与从堆栈分配一样快。

引用计数与这种分配策略根本不兼容。引用计数将对象放在空闲列表中，然后再次将它们删除。引用计数还需要在创建新对象时更新引用计数所需的大量开销（如上所述，纯函数式语言确实如此疯狂）。

在以下情况下，引用计数往往会做得很好：

  • 几乎所有堆内存都用于保存活动对象。
  • 相对于其他操作而言，分配和指针分配并不常见。
  • 引用可以在另一个处理器或计算机上进行管理。

要了解当今最好的高性能引用计数系统是如何工作的，请查看David Bacon和Erez Petrank的工作。

于 2009-04-27T02:08:01.570 回答
19

您的问题是基于错误的假设。完全有可能拥有循环引用和不可变数据。考虑以下使用不可变数据创建循环引用的 C# 示例。

class Node { 
  public readonly Node other;
  public Node() { 
    other = new Node(this);
  }
  public Node(Node node) {
    other = node;
  }
}

这种类型的技巧可以在许多函数式语言中完成，因此任何收集机制都必须处理循环引用的可能性。我并不是说循环引用不可能使用引用计数机制，只是必须处理它。

由ehemient编辑

作为对评论的回应......这在Haskell中是微不足道的

data Node a = Node { other :: Node a }
recursiveNode = Node { other = recursiveNode }

在 SML 上几乎没有任何努力。

datatype 'a node = NODE of unit -> 'a node
val recursiveNode : unit node =
    let fun mkRecursiveNode () = NODE mkRecursiveNode
    in mkRecursiveNode () end

不需要突变。

于 2009-04-26T19:28:44.183 回答
11

我认为有几件事。

  • 有循环：许多语言中的“let rec”确实允许创建“循环”结构。除此之外，不变性通常并不意味着没有循环，但这违反了规则。
  • 引用计数在列表中很糟糕：我不知道引用计数集合适用于您经常在 FP 中找到的长单链表结构（例如，速度慢，需要确保尾递归，...）
  • 其他策略有好处：正如您所提到的，其他 GC 策略通常仍然更适合内存局部性

（曾几何时，我想我可能真的“知道”这一点，但现在我试图记住/推测，所以不要把它当作任何权威。）

于 2009-04-26T19:30:54.333 回答
9

是对的吗？

不完全的。您可以使用纯函数式编程简单地通过同时定义相互递归的值来创建循环数据结构。例如，在 OCaml 中：

let rec xs = 0::ys and ys = 1::xs

但是，可以定义语言，使其无法通过设计创建循环结构。结果被称为单向堆，其主要优点是垃圾收集可以像引用计数一样简单。

如果是这样，他们为什么不呢？

有些语言确实禁止循环并使用引用计数。Erlang 和 Mathematica 就是例子。

例如，在 Mathematica 中，当您引用一个值时，您会对其进行深层复制，因此改变原始值不会改变副本：

In[1] := xs = {1, 2, 3}
Out[1] = {1, 2, 3}

In[2] := ys = xs
Out[2] = {1, 2, 3}

In[3] := xs[[1]] = 5
Out[3] = 5

In[4] := xs
Out[4] = {5, 2, 3}

In[5] := ys
Out[5] = {1, 2, 3}
于 2010-12-22T21:49:06.470 回答
8

想想这个关于Lisp 机器的发明者David Moon的寓言：

有一天，一位学生来找 Moon 说：“我知道如何做一个更好的垃圾收集器。我们必须保留每个 cons 指针的引用计数。”

穆恩耐心地给学生讲了以下故事：

“有一天，一个学生来到月球说：‘我知道如何做一个更好的垃圾收集器......

于 2009-05-25T04:23:59.780 回答
-6

引用计数比 GC 慢得多，因为它对 CPU 不利。并且 GC 大部分时间可以等待空闲时间，并且 GC 可以并发（在另一个线程上）。所以这就是问题所在 - GC 是最不邪恶的，并且许多尝试表明了这一点。

于 2009-04-26T19:28:12.687 回答