haskell - La reescritura como una técnica de optimización práctica en GHC: ¿Es realmente necesaria?

optimization compiler-optimization (3)

Algo en esa dirección se investigó en una tesis de licenciatura de Johannes Bader, un estudiante mío: Cómo encontrar ecuaciones en programas funcionales ( archivo PDF ).

Hasta cierto punto es ciertamente posible, pero

es bastante complicado Encontrar tales ecuaciones es tan difícil como encontrar pruebas en un probador de teoremas, y
a menudo no es muy útil, ya que tiende a encontrar ecuaciones que el programador raramente escribiría directamente.

Sin embargo, es útil limpiar después de otras transformaciones, como la alineación y diversas formas de fusión.

Estaba leyendo el artículo escrito por Simon Peyton Jones, et al. llamado "Jugar según las reglas: reescritura como una técnica de optimización práctica en GHC" . En la segunda sección, a saber, "La idea básica" escriben:

Considere la función de map familiar, que aplica una función a cada elemento de una lista. Escrito en Haskell, el map ve así:

map f [] = [] map f (x:xs) = f x : map f xs

Ahora suponga que el compilador encuentra la siguiente llamada de map :

map f (map g xs)

Sabemos que esta expresión es equivalente a

map (f . g) xs

(donde "." es la composición de la función), y sabemos que la última expresión es más eficiente que la anterior porque no hay una lista intermedia. Pero el compilador no tiene tal conocimiento.
Una posible respuesta es que el compilador debería ser más inteligente, pero el programador siempre sabrá cosas que el compilador no puede entender. Otra sugerencia es esta: permitir que el programador comunique tal conocimiento directamente al compilador. Esa es la dirección que exploramos aquí.

Mi pregunta es, ¿por qué no podemos hacer que el compilador sea más inteligente? Los autores dicen que "pero el programador siempre sabrá cosas que el compilador no puede entender". Sin embargo, esa no es una respuesta válida porque el compilador puede descifrar que el map f (map g xs) es equivalente a map (f . g) xs , y aquí es cómo:

map f (map g xs)

map g xs unifica con map f [] = [] .
Por lo tanto, el map g [] = [] .
map f (map g []) = map f [] .
map f [] unifica con map f [] = [] .
Por lo tanto, el map f (map g []) = [] .
map g xs unifica con map f (x:xs) = fx : map f xs .
Por lo tanto, el map g (x:xs) = gx : map g xs .
map f (map g (x:xs)) = map f (gx : map g xs) .
map f (gx : map g xs) unifica con map f (x:xs) = fx : map f xs .
Por lo tanto, el map f (map g (x:xs)) = f (gx) : map f (map g xs) .

Por eso ahora tenemos las reglas:

map f (map g []) = [] map f (map g (x:xs)) = f (g x) : map f (map g xs)

Como puede ver, f (gx) es solo (f . g) y el map f (map g xs) se llama de forma recursiva. Esta es exactamente la definición de map (f . g) xs . El algoritmo para esta conversión automática parece ser bastante simple. Entonces, ¿por qué no implementar esto en lugar de reescribir las reglas?

Esto podría verse como un equilibrio entre equilibrar las expectativas en el caso específico y equilibrarlas en el caso general. Este equilibrio puede generar situaciones divertidas en las que puedes saber cómo hacer algo más rápido, pero si no lo haces, es mejor para el idioma en general.

En el caso específico de los mapas en la estructura que usted da, la computadora podría encontrar optimizaciones. Sin embargo, ¿qué pasa con las estructuras relacionadas? ¿Qué pasa si la función no es un mapa? ¿Qué sucede si hay una capa adicional de direccionamiento indirecto, como una función que devuelve el mapa? En esos casos, el compilador no puede optimizar fácilmente. Este es el problema general del caso.

Cómo si optimiza el caso especial, se produce uno de dos resultados

Nadie confía en ello, porque no están seguros de si está allí o no. En este caso, se escriben artículos como el que usted cita.
La gente empieza a confiar en él, y ahora todos los desarrolladores se ven obligados a recordar que "los mapas realizados en esta configuración se convierten automáticamente en la versión rápida para mí, pero si lo hago en esta configuración no lo hago". ¡Esto comienza a manipular la forma en que la gente usa el lenguaje y puede reducir la legibilidad!

Dada la necesidad de que los desarrolladores piensen en tales optimizaciones en el caso general, esperamos que los desarrolladores realicen estas optimizaciones en el caso simple, ¡lo que reduce la necesidad de optimización en primer lugar!

Ahora, si resulta que el caso particular en el que está interesado representa algo masivo como el 2% del código base mundial en Haskell, habría un argumento mucho más sólido para aplicar la optimización de su caso especial.

La incorporación agresiva puede derivar muchas de las ecualidades que las reglas de reescritura son cortas. La diferencia es que la inscripción es "ciega", por lo que no se sabe de antemano si el resultado será mejor o peor, o incluso si terminará.

Sin embargo, las reglas de reescritura pueden hacer cosas completamente obvias, basadas en datos de un nivel mucho más alto sobre el programa. Piense en las reglas de reescritura como si se agregaran nuevos axiomas al optimizador. Al agregar estos, tiene un conjunto de reglas más rico para aplicar, lo que hace que las optimizaciones complicadas sean más fáciles de aplicar.

La fusión de flujos , por ejemplo, cambia la representación del tipo de datos. Esto no puede expresarse a través de inline, ya que implica un cambio de tipo de representación (replanteamos el problema de optimización en términos de Stream ADT). Fácil de establecer en las reglas de reescritura, imposible con la alineación solo.