performance - 拉链在实践中的表现如何，应该在什么时候使用？

Question

我认为拉链是个好主意；它优雅地提供了一种遍历列表或树的方法，并以一种功能性的方式进行本地更新。

渐近地，成本似乎是合理的。但是遍历数据结构需要在每次迭代时分配内存，而普通的列表或树遍历只是指针追逐。这似乎很昂贵（如果我错了，请纠正我）。

成本是否高得令人望而却步？什么情况下使用拉链是合理的？

Answer 1

我可以提供一个可靠的数据点：John Dias 和我在 2005 年 ML 研讨会上发表了一篇论文，我们在其中比较了使用拉链来表示控制流图的成本与在 Objective Caml 中使用可变记录字段的成本。我们非常惊喜地发现，使用基于 zipper 的控制流图的编译器的性能实际上略好于使用带有指针链接的可变记录的传统数据结构的性能。我们找不到严肃的分析工具来告诉我们确切的原因拉链更快，但我怀疑原因是要维护的不变量较少，因此指针分配相对较少。优化器也有可能足够聪明，可以分摊拉链产生的一些分配成本。在任何情况下，zipper 都可以在优化编译器中使用，并且实际上有一点性能优势。