optimization - tag - title seo length

¿Por qué GHC considera el LHS*sintácticamente*cuando se inscribe?

Question

Según los docs GHC:

... GHC solo alineará la función si se aplica completamente, donde "totalmente aplicado" significa aplicado a tantos argumentos como aparecen (sintácticamente) en el LHS de la definición de la función.

Donde el ejemplo dado es dos definiciones semánticamente equivalentes:

comp1 :: (b -> c) -> (a -> b) -> a -> c
{-# INLINE comp1 #-}
comp1 f g = /x -> f (g x)

comp2 :: (b -> c) -> (a -> b) -> a -> c
{-# INLINE comp2 #-}
comp2 f g x = f (g x)

Mis preguntas:

1. ¿Es solo en presencia de los pragmas INLINE que obtenemos este comportamiento estricto (es decir, una visión sintáctica estricta de LHS, RHS en línea sin optimizaciones)?

2. cuando no se dan pragmas INLINE, ¿transforma GHC alguna vez una función como comp2 en comp1 ?

3. si no, porque En general, ¿es demasiado difícil para el compilador observar la semántica de la función y decidir cuánto y dónde aplicar parcialmente y EN LÍNEA?

4. ¿Qué pasaría si GHC transformara todas las funciones en una cascada de let... in expresiones con lambdas y sin enlaces en el LHS?

Answer 1

¿Qué pasa si, en este ejemplo, c es en sí un tipo de función? No tengo claro cómo funcionaría tu propuesta en ese escenario.

En cualquier caso, definitivamente hay casos en los que no desea que todos los argumentos de una función se "tiren al frente". Por ejemplo, podría tener algún código como este:

foo :: [Int] -> Int -> Int -> Int
foo list = let
  -- expensive precomputation here
  bar x y = ...
  in / x y -> bar x y

Usted quiere que foo se aplique parcialmente, y luego para que múltiples aplicaciones de la función resultante compartan el costoso trabajo de precomputación. Si, por el contrario, lo hicieras avanzar como si foo list xy , no podrías compartir esa precomputación costosa. (He encontrado este caso en aplicaciones serias.)

Answer 2

Bueno, mejor tarde que nunca, supongo.

comp1 y comp2 no solo son semánticamente equivalentes, sino también sintácticamente.

Escribir argumentos en el LHS de un signo igual de una definición es solo azúcar sintáctica, por lo que estas dos funciones son equivalentes:

id1 x = x
id2 = /x -> x

Edit: Me di cuenta de que realmente no respondía a tus preguntas, así que aquí estás:

1. Hay una diferencia para GHC cuando se anotan con pragmas INLINE , ya que GHC almacena en su representación Core el despliegue de una función y para qué arity se puede desplegar (Esa es la Guidance=ALWAYS_IF(arity=1,...) parte ), por lo que realmente puede importar en la práctica.

2. No creo que lo haga, ya que comp1 y comp2 no se pueden distinguir después de desugaring a Core, en el que operan todas las optimizaciones. Entonces, cuando GHC quiera crear un nuevo despliegue, probablemente lo hará por aridad manifiesta (por ejemplo, el número de lambdas principales).

3. La mayor parte de la inclinación no es beneficiosa para los enlaces insaturados, ver más abajo. Lo mismo sucede con el ejemplo comp1 : la razón por la que queremos que esto suceda no es que nos preocupe la eliminación de una llamada de función. Más bien queremos que comp1 se especialice en los parámetros f y g , independientemente de a qué concreto x apliquemos la especialización. En realidad, hay un pase de optimización que debería hacer este tipo de trabajo, llamado especialización del constructor (más sobre esto más adelante). INLINE es incluso bastante inadecuado para usar aquí: Esto aún no especializa una llamada como comp1 (const 5) , donde es "obvio" que esto se reduzca a const 5 .

4. En consecuencia, esto no cambiará mucho, siempre y cuando no se rocíe todo lo que se limita a unir con pragmas INLINE . Incluso entonces es cuestionable si eso trae algún beneficio: el punto es que simplemente no tiene sentido alinear llamadas insaturadas sin ningún motivo adicional (por ejemplo, la especialización de una función a un argumento concreto) y aparte de eso solo hará explotar el tamaño del código en algún punto, por lo que probablemente incluso haga las cosas más lentas.

Edición final

Una razón por la que creo que el motivo por el cual las llamadas no saturadas a enlaces no están en línea es que, en su mayoría, no brindan nuevas oportunidades de optimización.

f = /x y -> 1 + (x * y)
g = /x y -> (1 + x) * y

Alinear f 16 produce /y -> 1 + (16*y) , lo cual no es mucho más simple que f 16 . Por el contrario, el tamaño del código aumentó considerablemente (que es el mayor inconveniente de la alineación).

Ahora, si hubiera una llamada como g 16 esto produciría /y -> (1 + 16) * y que se optimizaría para /y -> 17 * y . Pero este tipo de oportunidades son detectadas por otro paso de optimización, constructor o especialización de patrón de llamada . La idea aquí es que 1 + x se puede simplificar si conocemos el valor de x . Como llamamos g con un literal (por ejemplo, un valor), es beneficioso especializar g para ese sitio de llamada en particular, por ejemplo, g16 = /y -> 17 *y . No hay necesidad de incluir g línea, también otros sitios de llamadas pueden compartir el código generado para g16 .

Este es solo un ejemplo de cómo no es necesario hacer la alineación mientras se tiene un código eficiente. Hay muchas otras optimizaciones que, en interacción con el inliner, logran lo que usted desea. Eta-expansion, por ejemplo, se asegurará de que las llamadas estén lo más saturadas posible:

main = print (f 2)

f = g 1 
g x y = x + y

Dado que f siempre se llama con 1 argumento, podemos eta-expandirlo:

f eta = g 1 eta

Ahora la llamada a g está saturada y puede estar en línea. Dito para f , así que eventualmente esto se reduce a

main = print 3

f eta = 1 + eta
g x y = x + y

Módulo de eliminación de código muerto.

Answer 3

Esta es una buena pregunta. Leí los secretos del periódico Inliner del compilador Haskell de Glasgow en busca de algunas pistas, pero no encontré mucho.

Aquí hay una explicación de mano ondulada. En realidad, a veces GHC toma comp1 a comp2 , lo que se denomina "expansión eta". Vea este hilo para algunos detalles: http://www.haskell.org/pipermail/glasgow-haskell-users/2011-October/020979.html

También hay (o hubo) un problema donde esta expansión eta puede cambiar sutilmente la rigurosidad. Vea este compromiso con los documentos (que no parece estar en los actuales, por lo que o bien no se han reconstruido o se ha solucionado, no estoy seguro de cuál): http://permalink.gmane.org/gmane.comp.lang.haskell.cvs.ghc/57721

En cualquier caso, el hilo anterior tiene SPJ que explica por qué normalmente queremos ir en esa dirección siempre que sea posible. Así que ir deliberadamente en la otra dirección para mejorar la alineación parece un poco tonto. Como lo explica el documento sobre los secretos, la inclusión de promiscuamente no es la mejor idea: hacer que el pragma sea más bien un martillo sin filo, por lo que las funciones quedaron integradas, ya sea que tenga sentido o no, probablemente duela más que la ayuda en general, por no mencionar el aumento código inflado, ya que los módulos tendrían que mantener los diferentes niveles de funciones eta-shifted alrededor de todos a la vez.

De todos modos, como alguien que no es un desarrollador central de GHC, eso es lo que me parece más probable.