拉链在实践中表现如何，何时应用？ [英] How well do zippers perform in practice, and when should they be used?

问题描述

我认为拉链是一个美丽的主意;它优雅地提供了一种行走列表或树的方法，并以一种有效的方式使看起来成为本地更新。

I think that the zipper is a beautiful idea; it elegantly provides a way to walk a list or tree and make what appear to be local updates in a functional way.

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

Asymptotically, the costs appear to be reasonable. But traversing the data structure requires memory allocation at each iteration, where a normal list or tree traversal is just pointer chasing. This seems expensive (please correct me if I am wrong).

成本是否高昂？而在什么情况下，使用拉链是什么呢？

Are the costs prohibitive? And what under what circumstances would it be reasonable to use a zipper?

推荐答案

我可以提供一个坚实的数据点：John Dias和我在2005年的ML Workshop中有一个论文，我们比较了使用拉链代表控制流图的成本与在Objective Caml中使用可变记录字段的成本。我们非常惊喜地发现，使用基于拉链的控制流程图，我们的编译器的性能实际上稍微优于使用传统数据结构的性能，并通过指针链接可变记录。我们找不到严重的分析工具来确切地告诉我们，为什么拉链速度更快，但是我怀疑原因是维护不太多，指针分配相对较少。优化器也可能足够聪明，以摊销拉链所产生的一些分配成本。在任何情况下，拉链可用于优化编译器，实际上具有轻微的性能优势。

I can provide one solid data point: John Dias and I had a paper in the 2005 ML Workshop where we compared the cost of using a zipper to represent control-flow graphs with the cost of using mutable record fields in Objective Caml. We were very pleasantly surprised to find that the performance of our compiler with the zipper-based control-flow graphs was actually slightly better than the performance using a traditional data structure with mutable records linked by pointers. We couldn't find serious analysis tools to tell us exactly why the zipper was faster, but I suspect the reason was that there were fewer invariants to maintain and so relatively fewer pointer assignments. It's also possible that the optimizer was smart enough to amortize some of the allocation costs incurred by the zipper. In any case, the zipper can be used in an optimizing compiler, and there is actually a slight performance benefit.

这篇关于拉链在实践中表现如何，何时应用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！