Rob*_*lan 18 performance functional-programming memory-management zipper data-structures
我觉得拉链是一个很棒的主意; 它优雅地提供了一种方法来遍历列表或树,并以功能的方式显示本地更新.
渐渐地,成本似乎是合理的.但遍历数据结构需要在每次迭代时进行内存分配,其中正常的列表或树遍历只是指针追逐.这看起来很昂贵(如果我错了,请纠正我).
费用是否令人望而却步？在什么情况下使用拉链是否合理？
Nor*_*sey 27
我可以提供一个可靠的数据点:John Dias和我在2005 ML研讨会上有一篇论文,我们将使用拉链表示控制流图的成本与使用Objective Caml中的可变记录字段的成本进行了比较.我们非常惊喜地发现,使用基于拉链的控制流图的编译器的性能实际上略好于使用传统数据结构的性能,该传统数据结构具有通过指针链接的可变记录.我们找不到严谨的分析工具来告诉我们为什么拉链更快,但我怀疑原因是维护的不变量较少,因此指针分配相对较少.优化器也足够聪明,可以分摊拉链产生的一些分配成本.在任何情况下,拉链都可以用于优化编译器,实际上有一些性能上的好处.