design - tener - que es la estructura de una pagina web

¿Cómo se escriben las estructuras de datos que son tan eficientes como sea posible en GHC? (2)

Así que a veces necesito escribir una estructura de datos que no puedo encontrar en Hackage, o lo que encuentro que no está probado o no es lo suficientemente confiable como para que pueda confiar, o simplemente es algo que no quiero que sea una dependencia. Estoy leyendo el libro de Okasaki en este momento, y es bastante bueno para explicar cómo diseñar estructuras de datos asintóticamente rápidas.

Sin embargo, estoy trabajando específicamente con GHC. Los factores constantes son un gran problema para mis aplicaciones. El uso de la memoria también es un gran problema para mí. Entonces tengo preguntas específicamente sobre GHC.

En particular

Cómo maximizar el intercambio de nodos
Cómo reducir la huella de memoria
Cómo evitar fugas de espacio debido a la rigidez / pereza inadecuadas
Cómo hacer que GHC produzca bucles internos ajustados para secciones importantes del código

He buscado en varios sitios de la web y tengo una vaga idea de cómo trabajar con GHC, por ejemplo, mirando la salida del núcleo, utilizando pragmas UNPACK , y cosas por el estilo. Pero no estoy seguro de entenderlo.

Así que abrí mi biblioteca de estructuras de datos favorita, contenedores, y miré el módulo Data.Sequence. No puedo decir que entiendo mucho de lo que están haciendo para hacer que Seq sea rápido.

Lo primero que me llama la atención es la definición de FingerTree a . Supongo que es solo que yo no estoy familiarizado con los árboles de los dedos. Lo segundo que me llama la atención son todos los pragmas SPECIALIZE . No tengo idea de qué está pasando aquí, y estoy muy curioso, ya que están llenos de todo el código.

Muchas funciones también tienen un pragma INLINE asociado a ellas. Puedo adivinar lo que eso significa, pero ¿cómo hago una llamada de juicio sobre cuándo INLINE funciones?

Las cosas se vuelven realmente interesantes alrededor de la línea ~ 475, una sección que se califica como ''Construcción Aplicativa''. Definen un envoltorio de tipo nuevo para representar la mónada de Identidad, escriben su propia copia de la mónada de estado estricta y tienen una función definida llamada árbol applicativeTree que, aparentemente, está especializada en la mónada de Identidad y esto aumenta el intercambio de la salida de la función. No tengo idea de lo que está pasando aquí. ¿Qué hechicería se está usando para aumentar el intercambio?

De todos modos, no estoy seguro de que haya mucho que aprender de Data.Sequence. ¿Hay otros ''programas modelo'' que pueda leer para ganar sabiduría? Realmente me gustaría saber cómo actualizar mis estructuras de datos cuando realmente las necesite para ir más rápido. Una cosa en particular es escribir estructuras de datos que faciliten la fusión y cómo redactar buenas reglas de fusión.

¡Ese es un gran tema! La mayoría ha sido explicada en otro lugar, así que no intentaré escribir un capítulo de un libro aquí mismo. En lugar:

Real World Haskell, cap. 25, " Performance ": trata sobre la creación de perfiles, la especialización simple y el desempaquetado, la lectura de Core y algunas optimizaciones.

Johan Tibell está escribiendo mucho sobre este tema:

Y algunas cosas de aquí:

Y algunas otras cosas:

applicativeTree es bastante elegante, pero principalmente de una manera que tiene que ver con FingerTrees en particular, que son una estructura de datos bastante sofisticada. Tuvimos una discusión sobre las complejidades en cstheory . Tenga en cuenta que applicativeTree está escrito para trabajar sobre cualquier aplicativo. Sucede que cuando está especializado en Id , puede compartir nodos de una manera que de otro modo no podría. Puede trabajar con la especialización usted mismo al subrayar los métodos Id y ver qué sucede. Tenga en cuenta que esta especialización se utiliza en un solo lugar: la función de replicate O (log n). El hecho de que la función más general se especializa claramente en el caso constante es un poco inteligente de reutilización de código, pero eso es todo.

En general, Sequence enseña más sobre el diseño de estructuras de datos persistentes que sobre todos los trucos para obtener rendimiento, creo. Las sugerencias de Dons son por supuesto excelentes. También me gustaría navegar a través de la fuente de las libs realmente canónicas y afinadas: Map , IntMap , Set e IntSet en particular. Junto con ellos, vale la pena echar un vistazo al documento de Milán sobre sus mejoras en los contenedores .