performance haskell ghc inlining repa

performance - ¿Cómo usar el control de fase de inline en haskell?



ghc inlining (2)

Esencialmente respondiste tu propia pregunta, como otros lo han dicho Pero me imagino que es posible que desee un ejemplo más recortado y concreto de dónde es beneficioso utilizar el control de fase en combinación con RULES / INLINE . * No los ve más allá de bibliotecas altamente optimizadas que a menudo son complejas, por lo que es genial verlas más pequeñas. casos.

Aquí hay un ejemplo que implementé recientemente, usando esquemas de recursión. Ilustraremos esto utilizando el concepto de catamorfismos. No es necesario que conozca en detalle, solo que caracterizan a los operadores de "pliegue". (Realmente, no te centres demasiado en los conceptos abstractos aquí. Este es solo el ejemplo más simple que tengo, donde puedes tener una buena aceleración).

Introducción rápida a los catamorfismos.

Comenzamos con Mu , el tipo de punto de referencia y una definición de Algebra que es solo un sinónimo de fantasía para una función que "deconstruye" un valor de fa para devolver una a .

newtype Mu f = Mu { muF :: f (Mu f) } type Algebra f a = f a -> a

Ahora podemos definir dos operadores, ffold y fbuild , que son versiones altamente genéricas de los tradicionales foldr y foldr para listas:

ffold :: Functor f => Algebra f a -> Mu f -> a ffold h = go h where go g = g . fmap (go g) . muF {-# INLINE ffold #-} fbuild :: Functor f => (forall b. Algebra f b -> b) -> Mu f fbuild g = g Mu {-# INLINE fbuild #-}

En términos generales, el ffold destruye una estructura definida por un Algebra fa y produce un a . fbuild cambio crea una estructura definida por su Algebra fa y produce un valor Mu . Ese valor de Mu corresponde a cualquier tipo de datos recursivos de los que esté hablando. Al igual que foldr y build regulares: deconstruimos una lista usando sus contras, y construimos una lista usando sus contras, también. La idea es que acabamos de generalizar estos operadores clásicos, para que puedan trabajar con cualquier tipo de datos recursivos (como listas o árboles).

Finalmente, hay una ley que acompaña a estos dos operadores, que guiará nuestra RULE general:

forall f g. ffold f (build g) = g f

Esta regla esencialmente generaliza la optimización de la deforestación / fusión - la eliminación de la estructura intermedia. (Supongo que la prueba de la corrección de dicha ley se deja como un ejercicio para el lector. Debería ser bastante fácil a través del razonamiento ecuacional).

Ahora podemos usar estos dos combinadores, junto con Mu , para representar tipos de datos recursivos como una lista. Y podemos escribir operaciones sobre esa lista.

data ListF a f = Nil | Cons a f deriving (Eq, Show, Functor) type List a = Mu (ListF a) instance Eq a => Eq (List a) where (Mu f) == (Mu g) = f == g lengthL :: List a -> Int lengthL = ffold g where g Nil = 0 g (Cons _ f) = 1 + f {-# INLINE lengthL #-}

Y podemos definir una función de map también:

mapL :: (a -> b) -> List a -> List b mapL f = ffold g where g Nil = Mu Nil g (Cons a x) = Mu (Cons (f a) x) {-# INLINE mapL #-}

En línea FTW

Ahora tenemos un medio para escribir términos sobre estos tipos recursivos que definimos. Sin embargo, si tuviéramos que escribir un término como

lengthL . mapL (+1) $ xs

Luego, si expandimos las definiciones, esencialmente obtenemos la composición de dos operadores de ffold :

ffold g1 . ffold g2 $ ...

Y eso significa que en realidad estamos destruyendo la estructura, luego la estamos reconstruyendo y destruyendo de nuevo . Eso es realmente un desperdicio. Además, podemos redefinir mapL en términos de fbuild , por lo que esperamos que se fusione con otras funciones.

Bueno, ya tenemos nuestra ley, así que una RULE está en orden. Vamos a codificar eso:

{-# RULES -- Builder rule for catamorphisms "ffold/fbuild" forall f (g :: forall b. Algebra f b -> b). ffold f (fbuild g) = g f -}

A continuación, redefiniremos mapL en términos de fbuild para fines de fusión:

mapL2 :: (a -> b) -> List a -> List b mapL2 f xs = fbuild (/h -> ffold (h . g) xs) where g Nil = Nil g (Cons a x) = Cons (f a) x {-# INLINE mapL2 #-}

Aaaaaand hemos terminado, ¿verdad? ¡Incorrecto!

Fases para la diversión y el beneficio.

El problema es que no hay restricciones en cuanto a cuándo se produce la inscripción, lo que desordenará completamente esto. Consideremos el caso anterior que queríamos optimizar:

lengthL . mapL2 (+1) $ xs

Nos gustaría que las definiciones de lengthL y mapL2 estén en línea, de modo que la regla ffold/fbuild pueda disparar afterwords, sobre el cuerpo. Así que queremos ir a:

ffold f1 . fbuild g1 ...

Viajando, y después de eso vaya a:

g1 f1

a través de nuestra RULE .

Bueno, eso no está garantizado. Esencialmente, en una fase del simplificador, es posible que GHC no solo lengthL las definiciones de lengthL y mapL , sino que también ffold las definiciones de ffold y fbuild en sus sitios de uso. Esto significa que la REGLA nunca tendrá la oportunidad de disparar, ya que la fase ''engulló'' todos los identificadores relevantes y los convirtió en nada.

La observación es que nos gustaría en línea ffold y fbuild más tarde posible . Por lo tanto, trataremos de exponer tantas oportunidades posibles como sea posible para que nuestra REGLA se dispare. Y si no lo hace, entonces el cuerpo se pondrá en línea y el GHC seguirá dando lo mejor de sí. Pero en última instancia, queremos que se alinee tarde; La RULE nos ahorrará más eficiencia que cualquier optimización de compilador inteligente.

Así que la solución aquí es anotar ffold y fbuild y especificar que solo deben disparar en la fase 1:

ffold g = ... {-# INLINE[1] ffold #-} fbuild g = ... {-# INLINE[1] fbuild #-}

Ahora, mapL y sus amigos estarán en línea muy temprano, pero estos llegarán muy tarde. GHC comienza a partir de un número de fase N y los números de fase disminuyen a cero. La fase 1 es la última fase. También sería posible en línea fbuild/ffold antes de la Fase 1, pero esto esencialmente significaría que necesita comenzar a aumentar el número de fases para compensarlo, o asegurarse de que la REGLA siempre se dispare en algunas etapas anteriores.

Conclusión

Puede encontrar todo esto y mucho más en mi esencia **, con todas las definiciones y los ejemplos mencionados aquí. También viene con un criterio de referencia de nuestro ejemplo: con nuestras anotaciones de fase, GHC puede reducir el tiempo de ejecución de lengthL . mapL2 lengthL . mapL2 a la mitad en comparación con lengthL . mapL1 lengthL . mapL1 , cuando la lengthL . mapL1 dispara.

Si desea ver esto usted mismo, puede compilar el código con -ddump-simpl-stats , y ver que la regla ffold/fbuild durante el proceso de compilación.

Finalmente, la mayoría de los mismos principios se aplican a bibliotecas como vector o bytestring. El truco es que puedes tener múltiples niveles de alineación aquí, y muchas más reglas. Esto se debe a que las técnicas como la fusión de flujos / matrices tienden a fusionar efectivamente los bucles y reutilizar las matrices, a diferencia de aquí, donde solo hacemos la deforestación clásica, al eliminar una estructura de datos intermedia. Dependiendo del ''patrón'' tradicional de código generado (por ejemplo, debido a una comprensión de lista paralela vectorizada) puede valer la pena intercalar o específicamente las optimizaciones de fase de una manera en que las deficiencias obvias se eliminan antes. O bien, optimice para los casos en que una RULE en combinación con un INLINE dará lugar a más RULE (por lo tanto, las fases escalonadas que ve a veces, esto básicamente intercala una fase de la alineación). Por estas razones, también puede controlar las fases en las que una RULE dispara.

Entonces, si bien las RULE con fases pueden ahorrarnos mucho tiempo de ejecución, también pueden tomar mucho tiempo para hacerlo bien. Esta es la razón por la que a menudo los ve solo en las bibliotecas altamente optimizadas y de "alto rendimiento".

Notas

  • * Su pregunta original fue "qué tipo de funciones se benefician del control de fase", lo que para mí es como preguntar "qué funciones se benefician de la eliminación constante de subexpresiones". ¡No estoy seguro de cómo contestar esto con precisión, si es posible! Esto es más una cuestión de ámbito de compilación, que cualquier resultado teórico sobre cómo se comportan las funciones o los programas, incluso con las leyes matemáticas, no todas las ''optimizaciones'' tienen los resultados que espera. Como resultado, la respuesta es efectivamente "probablemente lo sabrás cuando lo escribas y lo hagas referencia".

  • ** Puedes ignorar con seguridad muchas otras cosas en el archivo; era sobre todo un patio de recreo, pero también puede ser interesante para usted. Hay otros ejemplos como los árboles naturales y binarios allí. Puede que valga la pena intentar explotar otras oportunidades de fusión, usándolas.

La documentación says ,

A veces desea controlar exactamente cuando en la tubería de GHC el pragma INLINE está encendido.

¿Por qué debería querer esto? (Excepto cuando también utilizo las REGLAS de pragma, en este caso es posible que desee posponer la incorporación de la función para permitir que se activen las reglas asociadas). ¿Qué tipo de funciones son mejores para integrarse solo en una etapa particular del proceso de simplificación?

Primero, debo señalar que el comportamiento predeterminado de GHC está diseñado para ser mayormente óptimo en la mayoría de las situaciones. A menos que tenga un problema, probablemente sea mejor dejar que las personas muy inteligentes que piensan en haskell todo el día sean las más adecuadas (PD: no soy una de esas personas), pero usted preguntó ...

A mi entender hay dos razones para usar esto.

  1. Hacer que el programa converja a su mejor forma más rápido:

    Haskell intentará cada paso de las reglas repetidamente siempre que lo que salga del otro extremo sea estrictamente mejor que el principio. Siempre convergerá, pero no hay nada que diga que lo hará antes de la muerte térmica del universo. En el caso común, no se necesita más que una mano llena de pases, pero hay algunos casos de esquina que se pueden hacer patológicamente malos. Esto le permitirá trabajar manualmente alrededor de esos casos de borde si ocurren.

  2. Evite converger a un mínimo local.

    Hay algunos casos en los que la aplicación de la Regla A impedirá la aplicación de una mejor Regla B Entonces es importante que B venga antes de A Las reglas de optimización predeterminadas están bien diseñadas para evitar este problema, pero como la documentación dice que también son muy conservadoras. A medida que agregue más reglas, inevitablemente comenzará a romper otras posibles optimizaciones. Entonces necesitarás encontrar un lugar en la cadena de reglas donde esto no suceda. Que yo sepa, la única forma de saberlo es mediante prueba y error.