How well do zippers perform in practice, and when should they be used?

Question

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?

Enchondroma

An aside: thanks for posting the link to the paper, looks like a good read. At first I thought this was db related, given the redgate icon on the performance tag. Someone should get YKK on the phone and let them know of the available adspace for the zipper tag. – Painless

Ah. I was wondering what that logo was. I thought Ricky Gervais. – Enchondroma

Answer 1

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.

Gebler

Is your code available? Note that OCaml has an unusually inefficient write barrier that penalizes pointer writes in imperative code. – Feinleib