performance - ¿Qué tan bien se desempeñan las cremalleras en la práctica y cuándo deben usarse?

data-structures functional-programming

Question

Creo que la zipper es una hermosa idea; Con elegancia, proporciona una forma de recorrer una lista o árbol y hacer que las actualizaciones locales parezcan funcionales.

Asintóticamente, los costos parecen ser razonables. Pero atravesar la estructura de datos requiere una asignación de memoria en cada iteración, donde una lista normal o un recorrido de árbol es solo la búsqueda de punteros. Esto parece caro (corríjame si me equivoco).

¿Son los costos prohibitivos? ¿Y bajo qué circunstancias sería razonable usar una cremallera?

Answer 1

Puedo proporcionar un punto de datos sólido: John Dias y yo tuvimos un artículo en el Taller de ML 2005 en el que comparamos el costo de usar una cremallera para representar gráficos de flujo de control con el costo de usar campos de registro mutables en Objective Caml. Nos sorprendió gratamente descubrir que el rendimiento de nuestro compilador con los gráficos de flujo de control basados ​​en cremalleras fue ligeramente mejor que el rendimiento al usar una estructura de datos tradicional con registros mutables vinculados por punteros. No pudimos encontrar herramientas de análisis serias para decirnos exactamente por qué la cremallera era más rápida, pero sospecho que la razón era que había menos invariantes que mantener y, por lo tanto, relativamente menos asignaciones de punteros. También es posible que el optimizador fuera lo suficientemente inteligente como para amortizar algunos de los costos de asignación incurridos por la cremallera. En cualquier caso, la cremallera se puede utilizar en un compilador de optimización, y en realidad hay un ligero beneficio en el rendimiento.