optimization - ¿Realmente GHC nunca puede alinear mapas, escaneos, plegadores, etc.?

haskell inline

Question

Me di cuenta de que el manual de GHC dice que "para una función de recitación automática, el interruptor de lazo solo puede ser la función en sí misma, por lo que un pragma EN LÍNEA siempre se ignora".

¿No dice esto que todas las aplicaciones de construcciones funcionales recursivas comunes como map , zip , scan* , fold* , sum , etc. no se pueden insertar?

Siempre podría reescribir todas estas funciones cuando las emplee, agregue las etiquetas de rigurosidad adecuadas o tal vez emplee técnicas sofisticadas como la "fusión de secuencias" que se recomienda here .

Sin embargo, ¿no todo esto limita drásticamente nuestra capacidad para escribir código que sea simultáneamente rápido y elegante?

Answer 1

para una función recursiva, el interruptor de lazo solo puede ser la función en sí misma, por lo que un pragma INLINE siempre se ignora.

Si algo es recursivo, para alinearlo, debería saber cuántas veces se ejecuta en tiempo de compilación. Teniendo en cuenta que será una entrada de longitud variable, eso no es posible.

Sin embargo, ¿no todo esto limita drásticamente nuestra capacidad para escribir código que sea simultáneamente rápido y elegante?

Sin embargo, existen ciertas técnicas que pueden hacer llamadas recursivas mucho, mucho más rápido que en su situación normal. Por ejemplo, optimización de la cola de llamada SO Wiki

Answer 2

De hecho, GHC no puede en este momento en línea funciones recursivas. Sin embargo:

• GHC todavía se especializará en funciones recursivas. Por ejemplo, dado

  fac :: (Eq a, Num a) => a -> a
  fac 0 = 1
  fac n = n * fac (n-1)
  f :: Int -> Int
  f x = 1 + fac x

  GHC detectará que fac se usa en el tipo Int -> Int y generará una versión especializada de fac para ese tipo, que utiliza la aritmética de enteros rápidos.

  Esta especialización ocurre automáticamente dentro de un módulo (por ejemplo, si fac y f están definidos en el mismo módulo). Para la especialización de módulos cruzados (por ejemplo, si f y fac se definen en diferentes módulos), marque la función que se va a especializar con un pragma ININTERNO :

  {-# INLINABLE fac #-}
  fac :: (Eq a, Num a) => a -> a
  ...

• Hay transformaciones manuales que hacen que las funciones no sean recursivas. La técnica de menor potencia es la transformación de argumento estático , que se aplica a las funciones recursivas con argumentos que no cambian en las llamadas recursivas (por ejemplo, muchas funciones de orden superior como map , filter , fold* ). Esta transformación gira

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

  dentro

  map f xs0 = go xs0
  where
  go [] = []
  go (x:xs) = f x : go xs

  para que una llamada como

   g :: [Int] -> [Int]
  g xs = map (2*) xs

  tendrá un map línea y se convertirá

   g [] = []
  g (x:xs) = 2*x : g xs

  Esta transformación se ha aplicado a funciones de Preludio como foldr y foldl .

• Las técnicas de fusión también hacen que muchas funciones no sean recursivas, y son más poderosas que la transformación de argumento estático. El enfoque principal para las listas, que está integrado en el Preludio, es la fusión de acceso directo . El enfoque básico es escribir tantas funciones como sea posible como funciones no recursivas que utilizan foldr y / o build ; luego, toda la recursión se captura en foldr , y existen REGLAS especiales para lidiar con foldr .

  Aprovechar esta fusión es, en principio, fácil: evite la recursión manual, prefiera las funciones de la biblioteca como foldr , map , filter y cualquier función en esta lista . En particular, escribir código en este estilo produce un código que es "simultáneamente rápido y elegante".

• Las bibliotecas modernas, como el text y el vector usan la fusión de secuencias detrás de escena. Don Stewart escribió un par de publicaciones en el blog ( 1 , 2 ) que demuestran esto en acción en el uvector biblioteca, ahora obsoleto, pero los mismos principios se aplican al texto y al vector.

  Al igual que con la fusión de atajos, aprovechar la fusión de flujo en texto y vector es, en principio, fácil: evite la recursión manual, prefiriendo funciones de biblioteca que han sido marcadas como "sujetas a fusión".

• Se está trabajando en la mejora de GHC para apoyar la creación de funciones recursivas. Esto cae bajo el título general de supercompilation , y el trabajo reciente sobre este parece haber sido dirigido por Max Bolingbroke y Neil Mitchell .

Answer 3

En resumen, no tan a menudo como pensarías. La razón es que las "técnicas sofisticadas" como la fusión de secuencias se emplean cuando se implementan las bibliotecas, y los usuarios de la biblioteca no tienen que preocuparse por ellas.

Considere Data.List.map . El paquete base define el map como

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

Este map es recursivo por sí mismo, por lo que GHC no lo alineará.

Sin embargo, base también define las siguientes reglas de reescritura:

{-# RULES
"map" [~1] forall f xs. map f xs = build (/c n -> foldr (mapFB c f) n xs)
"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
#-}

Esto reemplaza los usos del map través de la fusión foldr / build , luego, si la función no se puede fusionar, la reemplaza con el map original. Debido a que la fusión ocurre automáticamente, no depende de que el usuario lo sepa.

Como prueba de que todo esto funciona, puede examinar lo que GHC produce para entradas específicas. Para esta función:

proc1 = sum . take 10 . map (+1) . map (*2)
eval1 = proc1 [1..5]
eval2 = proc1 [1..]

cuando se compila con -O2, GHC fusiona todo proc1 en una única forma recursiva (como se ve en la salida del núcleo con -ddump-simpl ).

Por supuesto, hay límites a lo que estas técnicas pueden lograr. Por ejemplo, la función media ingenua, mean xs = sum xs / length xs se transforma fácilmente manualmente en un solo pliegue, y existen marcos que pueden hacerlo automáticamente , sin embargo, actualmente no hay forma conocida de traducir automáticamente entre funciones estándar y la fusión marco de referencia. Entonces, en este caso, el usuario debe ser consciente de las limitaciones del código producido por el compilador.

Por lo tanto, en muchos casos, los compiladores están lo suficientemente avanzados para crear un código rápido y elegante. Sabiendo cuándo lo harán, y cuándo es probable que el compilador se caiga, en mi humilde opinión, una gran parte de aprender a escribir un código Haskell eficiente.