为什么纯粹的函数式语言不使用引用计数?
在纯function语言中,数据是不可变的。 通过引用计数,创build参考周期需要更改已经创build的数据。 似乎纯粹的function语言可以使用引用计数,而不用担心循环的可能性。 我是对的? 如果是这样,他们为什么不呢?
我知道引用计数在许多情况下比GC慢,但至less减less了停顿时间。 在暂停时间不好的情况下,可以select使用参考计数。
你的问题是基于错误的假设。 具有循环引用和不可变数据是完全可能的。 考虑下面使用不可变数据创build循环引用的C#示例。
class Node { public readonly Node other; public Node() { other = new Node(this); } public Node(Node node) { other = node; } }
这种技巧可以用许多function语言来完成,因此任何收集机制都必须处理循环引用的可能性。 我并不是说一个循环参考不可能有一个参考计数机制,只是必须要处理。
编辑ephemient
回应评论…这在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
不需要突变。
相对于Java和C#等其他pipe理语言, 纯function性语言的分配如同疯狂 。 他们还分配不同大小的对象。 已知最快的分配策略是从连续的空闲空间(有时称为“托儿所”)进行分配,并预留硬件寄存器以指向下一个可用的空闲空间。 从堆中分配的速度与从堆中分配一样快。
引用计数与此分配策略基本上是不相容的。 参考计数将对象放在空闲列表中,并将其重新取出。 在创build新对象时,Ref count也会有更新ref count所需的大量开销(如上所述,这是纯粹的函数式语言确实非常疯狂)。
引用计数在这样的情况下往往会performance得很好:
- 几乎所有的堆内存都用来存放活动对象。
- 与其他操作相比,分配和指针分配并不常见。
- 可以在其他处理器或计算机上pipe理参考。
为了理解今天最好的高性能计数系统如何工作,请查阅David Bacon和Erez Petrank的工作 。
我想有几件事情。
- 有循环 :许多语言中的“let rec”确实允许创build“循环”结构。 除此之外,不可变性通常意味着没有循环,但是这违反了规则。
- 引用计数在列表中是不好的 :我不知道引用计数的集合对于你在FP中经常发现的长单链表结构(例如缓慢,需要确保尾recursion等)
- 其他策略有好处 :正如你所暗示的,其他的GC策略通常对记忆的局部性通常更好
(曾几何时,我想我可能真的“知道”了这一点,但是现在我想要记住/推测,所以不要把它当作任何权威。)
我是对的?
不完全的。 您可以使用纯函数式编程创build循环数据结构,只需同时定义相互recursion的值即可。 例如,在OCaml中:
let rec xs = 0::ys and ys = 1::xs
但是,可以定义使得不可能通过devise来创build循环结构的语言。 结果被称为单向堆 ,其主要优点是垃圾回收可以像引用计数一样简单。
如果是这样,他们为什么不呢?
一些语言禁止循环并使用引用计数。 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}
想想这个寓言告诉David Lisp Machine的发明者David Moon :
有一天,一个学生来到月亮说:“我明白如何做一个更好的垃圾收集器,我们必须保持对每个缺点指针的引用计数。
月亮耐心地告诉学生以下故事:
“有一天,一个学生来到月亮说:”我明白如何做一个更好的垃圾收集器…
引用计数比GC慢很多,因为它不适合CPU。 GC大部分时间都可以等待空闲时间,GC也可以并发(在另一个线程上)。 所以这就是问题 – GC是最不可靠的,很多尝试都表明这一点。