¿Por qué las FingerTrees no se usan lo suficiente para tener una implementación estable?

Question

Hace un tiempo, me encontré con an article on FingerTrees (véase también an accompanying Stack Overflow Question) y archivé la idea. Finalmente encontré una razón para hacer uso de ellos.

Mi problema es que el Data.FingerTree package parece tener un poco de putrefacción en los bordes. Además, Data.Sequence en el paquete de Contenedores que hace uso de la estructura de datos re-implements una (posiblemente mejor) versión, pero no la exporta.

Por teóricamente útil que parezca esta estructura, no parece obtener mucho uso o atención. ¿Han encontrado las personas que FingerTrees no son útiles como una cuestión práctica, o este es un caso no es suficiente atención?

---

más explicaciones:

estoy interesado en la construcción de un texto que sostiene la estructura de datos que tiene buenas propiedades de concatenación. Piensa en construir un documento HTML a partir de fragmentos surtidos. La mayoría de las soluciones preconstruidas usan cadenas de bytes, pero realmente quiero algo que trate adecuadamente el texto Unicode. Mi plan en este momento es copiar fragmentos de Data.Text en un FingerTree.

También me gustaría tomar prestado el truco de Data.Vector de tomar rodajas sin copiar usando la manipulación (desplazamiento, longitud). Data.Text.Text tiene esto incorporado al tipo de datos, pero solo lo usa para desconexiones y operaciones irrelevantes eficientes. En FingerTree esta información podría convertirse fácilmente en v o anotación del árbol.

Answer 1

Para responder a su pregunta sobre árboles de dedo en particular, creo que el problema es que tienen costos constantes relativamente altos en comparación con las matrices, y son más complejas que otras formas de lograr una concatenación eficiente. Un Constructor tiene una interfaz más eficiente para agregar trozos, y generalmente están disponibles (ver los enlaces en la respuesta de @informatikr). Supongamos que Data.Text.Lazy se implementa con una lista vinculada de fragmentos y está creando un Data.Text.Lazy desde un generador. A menos que tenga muchos trozos (probablemente más de 50), o esté accediendo a los datos cerca del final de la lista repetidamente, el alto costo constante de un árbol digital probablemente no valga la pena.

La implementación Data.Sequence está especializada por motivos de rendimiento, y no es tan general como la interfaz completa proporcionada por el paquete fingertree. Es por eso que no se exporta; en realidad no es posible usarlo para nada más que un Sequence.

También sospecho que muchos programadores no saben cómo usar la anotación monoidal, ya que está detrás de una barrera de abstracción bastante significativa. Muchas personas no lo usarían porque no ven cómo puede ser útil en comparación con otros tipos de datos.

yo realmente no lo entiendo hasta que leí el blog de la serie Chung-Chieh Shan en word numbers (part2, part3, part4). Esa es una prueba de que la idea definitivamente puede usarse en el código práctico.

En su caso, si necesita inspeccionar resultados parciales y anexar eficientemente, usar un fingertree puede ser mejor que un constructor. Dependiendo de la implementación del constructor, puede terminar haciendo un montón de trabajo repetido al convertir a Text, agregar más cosas al constructor, convertir a Text nuevamente, etc. Sin embargo, dependerá de su patrón de uso.

Puede que le interese mi paquete splaytree, que proporciona árboles con anotaciones monoidales y varias estructuras diferentes construidas sobre ellos. Además del árbol de distribución, los módulos Set y RangeSet tienen API más o menos completas, el módulo Sequence es principalmente un esqueleto que utilicé para probar. No es una solución de "pilas incluidas" para lo que está buscando (de nuevo, la respuesta de @informatikr proporciona esas), pero si desea experimentar con anotaciones monoidales, puede ser más útil que Data.FingerTree. Tenga en cuenta que un árbol desplegable puede desequilibrarse si recorre todos los elementos en secuencia (o continuamente snoc en el extremo, o similar), pero si los anexos y las búsquedas se entrelazan, el rendimiento puede ser excelente.

Answer 2

Ignorando la pregunta de Finger Tree y solo respondiendo a su explicación adicional: ¿miró en Data.Text.Lazy.Builder o, específicamente para construir HTML, blaze-html?

Ambos permiten la concatenación rápida. Para cortar, si eso es importante para resolver su problema, es posible que no tengan un rendimiento ideal.

Answer 3

Además de la respuesta de John Lato, voy a agregar algunos detalles específicos sobre el rendimiento de los árboles de dedo, ya que pasé un tiempo mirando eso en el pasado.

El resumen amplio es:

• Data.Sequence tiene grandes factores constantes y asintótica: es casi tan rápido como [] cuando se accede a la parte delantera de la lista (en la que ambas estructuras de datos tienen O (1) asintótica) , y mucho más rápido en otras partes de la lista (donde las asintóticas logarítmicas de Data.Sequence superan las asintóticas lineales de []).

• Data.FingerTree tiene las mismas características asintóticas que Data.Sequence, pero tiene un orden de magnitud más lento.

Al igual que las listas, árboles dedos tienen altos gastos indirectos de memoria por elemento, por lo que debe combinarse con fragmentación para un mejor uso de la memoria y la memoria caché. De hecho, algunos paquetes hacen esto (yi, trifecta, rope). Si Data.FingerTree podría acercarse a Data.Sequence en el rendimiento, esperaría ver un tipo Data.Text.Sequence, que implementó un árbol de dedo de valores Data.Text. Tal tipo perdería el comportamiento de transmisión de Data.Text.Lazy, pero se beneficiaría de un mejor acceso aleatorio y rendimiento de concatenación. (Del mismo modo, me gustaría ver Data.ByteString.Sequence y Data.Vector.Sequence.)

El obstáculo para la implementación de estos ahora es que hay eficiente y genérica ejecución de los árboles de los dedos existe (ver más abajo donde discutir más a fondo). Para producir implementaciones eficientes de Data.Text.Sequence, uno tendría que volver a implementar completamente los árboles de los dedos, especializados en Text, al igual que Data.Text.Lazy listas de completa reimplementación, especializadas en Text. Desafortunadamente, los árboles de dedo son mucho más complejos que las listas (especialmente concatenation!), Por lo que esta es una cantidad considerable de trabajo.

Así como yo lo veo, la respuesta es:

• árboles especializados dedos son grandes, pero mucho trabajo para poner en práctica
• fragmentada árboles de los dedos (por ejemplo Data.Text.Sequence) habría grande, pero al presente el bajo rendimiento de Data.FingerTree significa que no son una alternativa viable a las listas fragmentadas en el caso común
• constructores y listas fragmentadas logran muchos de los beneficios de los árboles fragmentados, por lo que son suficientes para el caso común
• en el caso poco común donde los constructores y las listas fragmentadas no son suficientes, rechinan los dientes y soportan los pobres factores constantes de los árboles fragmentados (p. Ej. en yi y trifecta).

Obstáculos a un árbol dedo eficiente y genérica

Gran parte de la diferencia de rendimiento entre Data.Sequence y Data.FingerTree se debe a dos optimizaciones en Data.Sequence:

• El tipo de medida está especializado para Int, así que las manipulaciones de la medida se compilarán hasta la aritmética entera eficiente en lugar de

• The measure type is unpacked into the Deep constructor, que guarda las referencias de punteros en los bucles internos de las operaciones de árbol.

Es posible aplicar estas optimizaciones en el caso general de Data.FingerTree utilizando data families for generic unpacking y explotando revestimiento interior y specialiser de GHC - ver mi fingertree-unboxed package, que ofrece un rendimiento de árbol dedo genérica casi hasta la de Data.Sequence. Por desgracia, estas técnicas tienen algunos problemas importantes:

• data families for generic unpacking is unpleasant for the user, porque tienen que definir una gran cantidad de casos. No hay una solución clara para este problema.

• árboles de dedo utilizan recurrencia polimórfica, que el especialista de GHC no maneja bien (1, 2). Esto significa que, para obtener suficiente especialización en el tipo de medida, necesitamos muchos INLINE pragmas, lo que hace que GHC genere grandes cantidades de código.

Debido a estos problemas, nunca lancé el paquete en Hackage.