tecnicas tag realizarse que page onpage off example define debe como antes optimization haskell ghc

optimization - tag - ¿Qué optimizaciones se puede esperar que GHC realice de manera confiable?



seo on page que es (3)

GHC tiene muchas optimizaciones que puede realizar, pero no sé qué son, ni qué tan probable es que se realicen ni en qué circunstancias.

Mi pregunta es: ¿qué transformaciones puedo esperar que se apliquen cada vez, o casi? Si miro una parte del código que va a ser ejecutado (evaluado) con frecuencia y mi primer pensamiento es "hmm, tal vez debería optimizar eso", en cuyo caso debería ser mi segundo pensamiento, "ni siquiera lo pienses, GHC tiene esto "?

Estaba leyendo el artículo Stream Fusion: de listas a secuencias a Nothing at All , y la técnica que utilizaron para reescribir el procesamiento de listas en una forma diferente, que las optimizaciones normales de GHC optimizarían de forma segura en bucles simples, me resultaba novedosa. ¿Cómo puedo saber cuándo mis propios programas son elegibles para ese tipo de optimización?

Hay algo de información en el manual de GHC, pero solo hace una parte del camino para responder la pregunta.

EDITAR: Estoy comenzando una recompensa. Lo que me gustaría es una lista de transformaciones de bajo nivel como lambda / let / case-floating, tipo / constructor / función argumento de especialización, análisis de severidad y unboxing, worker / wrapper, y todo lo que GHC significa que he omitido , junto con explicaciones y ejemplos de códigos de entrada y salida, e idealmente ilustraciones de situaciones en las que el efecto total es más que la suma de sus partes. E idealmente, alguna mención de cuándo las transformaciones no sucederán. No espero explicaciones novedosas de cada transformación, un par de oraciones y ejemplos en línea de un solo linaje podrían ser suficientes (o un enlace, si no es para veinte páginas de artículos científicos), siempre y cuando el panorama general sea claro al final de ella. Quiero poder ver un fragmento de código y ser capaz de adivinar si se compilará en un ciclo cerrado, o por qué no, o qué tendría que cambiar para hacerlo. (Aquí no me interesan tanto los grandes marcos de optimización como la fusión de secuencias (acabo de leer un artículo sobre eso), más en el tipo de conocimiento que tienen las personas que escriben estos marcos.)

Si se utiliza un enlace let v = rhs en un solo lugar, puede contar con el compilador para encuadrarlo, incluso si rhs es grande.

La excepción (que casi no es una en el contexto de la pregunta actual) es lambdas arriesgando la duplicación del trabajo. Considerar:

let v = rhs l = /x-> v + x in map l [1..100]

la inclusión de v sería peligroso porque el único uso (sintáctico) se traduciría en 99 evaluaciones adicionales de rhs. Sin embargo, en este caso, es muy poco probable que desee alinearlo manualmente tampoco. Entonces, esencialmente puedes usar la regla:

Si considera incluir un nombre que solo aparece una vez, el compilador lo hará de todos modos.

Como un feliz corolario, usar un encuadernación para simplemente descomponer una declaración larga (con la esperanza de obtener claridad) es esencialmente gratuito.

Esto proviene de community.haskell.org/~simonmar/papers/inline.pdf que incluye mucha más información sobre la inclusión.

Esta página de GHC Trac también explica los pases bastante bien. Esta página explica el orden de optimización, sin embargo, como la mayoría de la Wiki de Trac, está desactualizada.

Para detalles, lo mejor que se puede hacer es mirar cómo se compila un programa específico. La mejor forma de ver qué optimizaciones se están realizando es compilar el programa de forma detallada, utilizando el indicador -v . Tomando como ejemplo la primera pieza de Haskell que pude encontrar en mi computadora:

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1 Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7 wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43 wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3 wired-in package rts mapped to builtin_rts wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf wired-in package dph-seq not found. wired-in package dph-par not found. Hsc static flags: -static *** Chasing dependencies: Chasing modules from: *SleepSort.hs Stable obj: [Main] Stable BCO: [] Ready for upsweep [NONREC ModSummary { ms_hs_date = Tue Oct 18 22:22:11 CDT 2011 ms_mod = main:Main, ms_textual_imps = [import (implicit) Prelude, import Control.Monad, import Control.Concurrent, import System.Environment] ms_srcimps = [] }] *** Deleting temp files: Deleting: compile: input file SleepSort.hs Created temporary directory: /tmp/ghc4784_0 *** Checking old interface for main:Main: [1 of 1] Compiling Main ( SleepSort.hs, SleepSort.o ) *** Parser: *** Renamer/typechecker: *** Desugar: Result size of Desugar (after optimization) = 79 *** Simplifier: Result size of Simplifier iteration=1 = 87 Result size of Simplifier iteration=2 = 93 Result size of Simplifier iteration=3 = 83 Result size of Simplifier = 83 *** Specialise: Result size of Specialise = 83 *** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}): Result size of Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}) = 95 *** Float inwards: Result size of Float inwards = 95 *** Simplifier: Result size of Simplifier iteration=1 = 253 Result size of Simplifier iteration=2 = 229 Result size of Simplifier = 229 *** Simplifier: Result size of Simplifier iteration=1 = 218 Result size of Simplifier = 218 *** Simplifier: Result size of Simplifier iteration=1 = 283 Result size of Simplifier iteration=2 = 226 Result size of Simplifier iteration=3 = 202 Result size of Simplifier = 202 *** Demand analysis: Result size of Demand analysis = 202 *** Worker Wrapper binds: Result size of Worker Wrapper binds = 202 *** Simplifier: Result size of Simplifier = 202 *** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}): Result size of Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}) = 210 *** Common sub-expression: Result size of Common sub-expression = 210 *** Float inwards: Result size of Float inwards = 210 *** Liberate case: Result size of Liberate case = 210 *** Simplifier: Result size of Simplifier iteration=1 = 206 Result size of Simplifier = 206 *** SpecConstr: Result size of SpecConstr = 206 *** Simplifier: Result size of Simplifier = 206 *** Tidy Core: Result size of Tidy Core = 206 writeBinIface: 4 Names writeBinIface: 28 dict entries *** CorePrep: Result size of CorePrep = 224 *** Stg2Stg: *** CodeGen: *** CodeOutput: *** Assembler: ''/usr/bin/gcc'' ''-fno-stack-protector'' ''-Wl,--hash-size=31'' ''-Wl,--reduce-memory-overheads'' ''-I.'' ''-c'' ''/tmp/ghc4784_0/ghc4784_0.s'' ''-o'' ''SleepSort.o'' Upsweep completely successful. *** Deleting temp files: Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c link: linkables are ... LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main [DotO SleepSort.o] Linking SleepSort ... *** C Compiler: ''/usr/bin/gcc'' ''-fno-stack-protector'' ''-Wl,--hash-size=31'' ''-Wl,--reduce-memory-overheads'' ''-c'' ''/tmp/ghc4784_0/ghc4784_0.c'' ''-o'' ''/tmp/ghc4784_0/ghc4784_0.o'' ''-DTABLES_NEXT_TO_CODE'' ''-I/usr/lib/ghc-7.4.2/include'' *** C Compiler: ''/usr/bin/gcc'' ''-fno-stack-protector'' ''-Wl,--hash-size=31'' ''-Wl,--reduce-memory-overheads'' ''-c'' ''/tmp/ghc4784_0/ghc4784_0.s'' ''-o'' ''/tmp/ghc4784_0/ghc4784_1.o'' ''-DTABLES_NEXT_TO_CODE'' ''-I/usr/lib/ghc-7.4.2/include'' *** Linker: ''/usr/bin/gcc'' ''-fno-stack-protector'' ''-Wl,--hash-size=31'' ''-Wl,--reduce-memory-overheads'' ''-o'' ''SleepSort'' ''SleepSort.o'' ''-L/usr/lib/ghc-7.4.2/base-4.5.1.0'' ''-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0'' ''-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0'' ''-L/usr/lib/ghc-7.4.2'' ''/tmp/ghc4784_0/ghc4784_0.o'' ''/tmp/ghc4784_0/ghc4784_1.o'' ''-lHSbase-4.5.1.0'' ''-lHSinteger-gmp-0.4.0.0'' ''-lgmp'' ''-lHSghc-prim-0.2.0.0'' ''-lHSrts'' ''-lm'' ''-lrt'' ''-ldl'' ''-u'' ''ghczmprim_GHCziTypes_Izh_static_info'' ''-u'' ''ghczmprim_GHCziTypes_Czh_static_info'' ''-u'' ''ghczmprim_GHCziTypes_Fzh_static_info'' ''-u'' ''ghczmprim_GHCziTypes_Dzh_static_info'' ''-u'' ''base_GHCziPtr_Ptr_static_info'' ''-u'' ''base_GHCziWord_Wzh_static_info'' ''-u'' ''base_GHCziInt_I8zh_static_info'' ''-u'' ''base_GHCziInt_I16zh_static_info'' ''-u'' ''base_GHCziInt_I32zh_static_info'' ''-u'' ''base_GHCziInt_I64zh_static_info'' ''-u'' ''base_GHCziWord_W8zh_static_info'' ''-u'' ''base_GHCziWord_W16zh_static_info'' ''-u'' ''base_GHCziWord_W32zh_static_info'' ''-u'' ''base_GHCziWord_W64zh_static_info'' ''-u'' ''base_GHCziStable_StablePtr_static_info'' ''-u'' ''ghczmprim_GHCziTypes_Izh_con_info'' ''-u'' ''ghczmprim_GHCziTypes_Czh_con_info'' ''-u'' ''ghczmprim_GHCziTypes_Fzh_con_info'' ''-u'' ''ghczmprim_GHCziTypes_Dzh_con_info'' ''-u'' ''base_GHCziPtr_Ptr_con_info'' ''-u'' ''base_GHCziPtr_FunPtr_con_info'' ''-u'' ''base_GHCziStable_StablePtr_con_info'' ''-u'' ''ghczmprim_GHCziTypes_False_closure'' ''-u'' ''ghczmprim_GHCziTypes_True_closure'' ''-u'' ''base_GHCziPack_unpackCString_closure'' ''-u'' ''base_GHCziIOziException__closure'' ''-u'' ''base_GHCziIOziException_heapOverflow_closure'' ''-u'' ''base_ControlziExceptionziBase_nonTermination_closure'' ''-u'' ''base_GHCziIOziException_blockedIndefinitelyOnMVar_closure'' ''-u'' ''base_GHCziIOziException_blockedIndefinitelyOnSTM_closure'' ''-u'' ''base_ControlziExceptionziBase_nestedAtomically_closure'' ''-u'' ''base_GHCziWeak_runFinalizzerBatch_closure'' ''-u'' ''base_GHCziTopHandler_flushStdHandles_closure'' ''-u'' ''base_GHCziTopHandler_runIO_closure'' ''-u'' ''base_GHCziTopHandler_runNonIO_closure'' ''-u'' ''base_GHCziConcziIO_ensureIOManagerIsRunning_closure'' ''-u'' ''base_GHCziConcziSync_runSparks_closure'' ''-u'' ''base_GHCziConcziSignal_runHandlers_closure'' link: done *** Deleting temp files: Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c *** Deleting temp dirs: Deleting: /tmp/ghc4784_0

Mirando desde el primer *** Simplifier: hasta el último, donde pasan todas las fases de optimización, vemos bastante.

En primer lugar, el Simplificador se ejecuta entre casi todas las fases. Esto hace que escribir muchos pases sea mucho más fácil. Por ejemplo, al implementar muchas optimizaciones, simplemente crean reglas de reescritura para propagar los cambios en lugar de tener que hacerlo manualmente. El simplificador abarca una cantidad de optimizaciones simples, que incluyen alineación y fusión. La principal limitación de esto que yo sé es que GHC se niega a las funciones recursivas en línea, y que las cosas tienen que ser nombradas correctamente para que la fusión funcione.

A continuación, vemos una lista completa de todas las optimizaciones realizadas:

  • Especializarse

    La idea básica de la especialización es eliminar el polimorfismo y la sobrecarga identificando los lugares donde se llama a la función y creando versiones de la función que no son polimórficas: son específicas de los tipos con los que se invocan. También puede decirle al compilador que haga esto con el pragma SPECIALISE . Como ejemplo, tome una función factorial:

    fac :: (Num a, Eq a) => a -> a fac 0 = 1 fac n = n * fac (n - 1)

    Como el compilador no conoce ninguna propiedad de la multiplicación que se utilizará, no puede optimizarla en absoluto. Sin embargo, si ve que se usa en un Int , ahora puede crear una nueva versión, que difiere solo en el tipo:

    fac_Int :: Int -> Int fac_Int 0 = 1 fac_Int n = n * fac_Int (n - 1)

    A continuación, las reglas mencionadas a continuación pueden activarse, y terminas con algo que funciona en Ints sin caja, que es mucho más rápido que el original. Otra forma de ver la especialización es la aplicación parcial en diccionarios de clase de tipo y variables de tipo.

    La source aquí tiene una carga de notas.

  • Flotar

    EDITAR: aparentemente no entendí esto antes. Mi explicación ha cambiado completamente.

    La idea básica de esto es mover los cálculos que no se deben repetir fuera de las funciones. Por ejemplo, supongamos que tenemos esto:

    /x -> let y = expensive in x+y

    En la lambda anterior, cada vez que se llama a la función, y se vuelve a calcular. Una mejor función, que produce flotar, es

    let y = expensive in /x -> x+y

    Para facilitar el proceso, se pueden aplicar otras transformaciones. Por ejemplo, esto sucede:

    /x -> x + f 2 /x -> x + let f_2 = f 2 in f_2 /x -> let f_2 = f 2 in x + f_2 let f_2 = f 2 in /x -> x + f_2

    De nuevo, el cálculo repetido se guarda.

    La source es muy legible en este caso.

    En este momento, las uniones entre dos lambdas adyacentes no flotan. Por ejemplo, esto no sucede:

    /x y -> let t = x+x in ...

    caminante a

    /x -> let t = x+x in /y -> ...

  • Flotar hacia adentro

    Citando el código fuente,

    El objetivo principal de floatInwards es flotar en las ramas de un caso, de modo que no asignemos cosas, las guardemos en la pila y descubramos que no son necesarias en la rama elegida.

    Como ejemplo, supongamos que tenemos esta expresión:

    let x = big in case v of True -> x + 1 False -> 0

    Si v evalúa como False , entonces asignando x , que es probablemente un gran thunk, hemos perdido tiempo y espacio. Flotar hacia adentro corrige esto, produciendo esto:

    case v of True -> let x = big in x + 1 False -> let x = big in 0

    , que luego es reemplazado por el simplificador con

    case v of True -> big + 1 False -> 0

    Este documento , aunque cubre otros temas, da una introducción bastante clara. Tenga en cuenta que a pesar de sus nombres, flotar y flotar hacia afuera no entra en un ciclo infinito por dos razones:

    1. Flotar en flotantes permite declaraciones de case , mientras que flotar trata de funciones.
    2. Hay un orden fijo de pases, por lo que no deberían estar alternando infinitamente.

  • Análisis de demanda

    El análisis de la demanda o el análisis de rigor es menos una transformación y más, como su nombre lo indica, de un pase de recopilación de información. El compilador encuentra funciones que siempre evalúan sus argumentos (o al menos algunos de ellos), y los pasa usando call-by-value, en lugar de call-by-need. Ya que puedes evadir los gastos generales de los thunk, esto es a menudo mucho más rápido. Muchos problemas de rendimiento en Haskell surgen de la falla de este pase o de que el código simplemente no es lo suficientemente estricto. Un ejemplo simple es la diferencia entre usar foldr , foldl y foldl'' para sumar una lista de enteros: el primero causa el desbordamiento de pila, el segundo causa el desbordamiento del montón y el último funciona bien, debido a la rigurosidad. Este es probablemente el más fácil de entender y mejor documentado de todos estos. Creo que el polimorfismo y el código CPS suelen vencer esto.

  • Trabajador Wrapper se une

    La idea básica de la transformación worker / wrapper es hacer un ciclo cerrado en una estructura simple, convirtiéndose desde y hacia esa estructura en los extremos. Por ejemplo, tome esta función, que calcula el factorial de un número.

    factorial :: Int -> Int factorial 0 = 1 factorial n = n * factorial (n - 1)

    Usando la definición de Int en GHC, tenemos

    factorial :: Int -> Int factorial (I# 0#) = I# 1# factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of I# down# -> down#)

    Observe cómo el código está cubierto en I# s? Podemos eliminarlos haciendo esto:

    factorial :: Int -> Int factorial (I# n#) = I# (factorial# n#) factorial# :: Int# -> Int# factorial# 0# = 1# factorial# n# = n# *# factorial# (n# -# 1#)

    Aunque este ejemplo específico también podría haberlo hecho SpecConstr, la transformación worker / wrapper es muy general en lo que puede hacer.

  • Sub-expresión común

    Esta es otra optimización realmente simple que es muy efectiva, como el análisis de rigor. La idea básica es que si tienes dos expresiones que son iguales, tendrán el mismo valor. Por ejemplo, si fib es una calculadora de números de Fibonacci, CSE transformará

    fib x + fib x

    dentro

    let fib_x = fib x in fib_x + fib_x

    que corta el cálculo a la mitad. Desafortunadamente, esto ocasionalmente puede interferir con otras optimizaciones. Otro problema es que las dos expresiones tienen que estar en el mismo lugar y deben ser sintácticamente iguales, no iguales en valor. Por ejemplo, CSE no abrirá en el siguiente código sin un montón de alineación:

    x = (1 + (2 + 3)) + ((1 + 2) + 3) y = f x z = g (f x) y

    Sin embargo, si compila a través de llvm, puede obtener algo de esto combinado, debido a su pase de Numeración de valor global.

  • Liberar el caso

    Esta parece ser una transformación terriblemente documentada, además del hecho de que puede causar la explosión del código. Aquí hay una versión reformateada (y ligeramente reescrita) de la poca documentación que encontré:

    Este módulo pasa por encima de Core y busca case en variables libres. El criterio es: si hay un case en una variable libre en la ruta a la llamada recursiva, entonces la llamada recursiva se reemplaza con un despliegue. Por ejemplo, en

    f = / t -> case v of V a b -> a : f t

    el f interno es reemplazado. para hacer

    f = / t -> case v of V a b -> a : (letrec f = / t -> case v of V a b -> a : f t in f) t

    Tenga en cuenta la necesidad de sombreado. Simplificando, obtenemos

    f = / t -> case v of V a b -> a : (letrec f = / t -> a : f t in f t)

    Este es un mejor código, porque a es gratis dentro del letrec interno, en lugar de necesitar proyección de v . Tenga en cuenta que esto trata de variables libres , a diferencia de SpecConstr, que trata con argumentos que son de forma conocida.

    Consulte a continuación para obtener más información acerca de SpecConstr.

  • SpecConstr: esto transforma programas como

    f (Left x) y = somthingComplicated1 f (Right x) y = somethingComplicated2

    dentro

    f_Left x y = somethingComplicated1 f_Right x y = somethingComplicated2 {-# INLINE f #-} f (Left x) = f_Left x f (Right x) = f_Right x

    Como un ejemplo extendido, tome esta definición de last :

    last [] = error "last: empty list" last (x:[]) = x last (x:x2:xs) = last (x2:xs)

    Primero lo transformamos en

    last_nil = error "last: empty list" last_cons x [] = x last_cons x (x2:xs) = last (x2:xs) {-# INLINE last #-} last [] = last_nil last (x : xs) = last_cons x xs

    A continuación, se ejecuta el simplificador, y tenemos

    last_nil = error "last: empty list" last_cons x [] = x last_cons x (x2:xs) = last_cons x2 xs {-# INLINE last #-} last [] = last_nil last (x : xs) = last_cons x xs

    Tenga en cuenta que el programa ahora es más rápido, ya que no estamos boxeando ni desempacando el frente de la lista. También tenga en cuenta que la entrada en línea es crucial, ya que permite utilizar las definiciones nuevas y más eficientes, así como mejorar las definiciones recursivas.

    SpecConstr está controlado por una serie de heurísticas. Los que se mencionan en el documento son como tales:

    1. Las lambdas son explícitas y la arity es a .
    2. El lado derecho es "suficientemente pequeño", algo controlado por una bandera.
    3. La función es recursiva, y la llamada especializable se usa en el lado derecho.
    4. Todos los argumentos a la función están presentes.
    5. Al menos uno de los argumentos es una aplicación de constructor.
    6. Ese argumento es analizado en algún caso en la función.

    Sin embargo, las heurísticas casi con seguridad han cambiado. De hecho, el documento menciona una sexta heurística alternativa:

    Especialícese en un argumento x solo si x solo es examinado por un case , y no se pasa a una función ordinaria, o se devuelve como parte del resultado.

Este era un archivo muy pequeño (12 líneas) y posiblemente no desencadenó tantas optimizaciones (aunque creo que las hizo todas). Esto tampoco le dice por qué eligió esos pases y por qué los puso en ese orden.

pereza

No es una "optimización del compilador", pero es algo garantizado por la especificación del lenguaje, por lo que siempre puede contar con que ocurra. Básicamente, esto significa que el trabajo no se realiza hasta que "haces algo" con el resultado. (A menos que haga una de varias cosas para desactivar deliberadamente la pereza).

Esto, obviamente, es un tema completo en sí mismo, y SO tiene muchas preguntas y respuestas sobre esto ya.

En mi experiencia limitada, hacer que tu código sea demasiado vago o demasiado estricto tiene multas de rendimiento mucho mayores (en tiempo y espacio) que cualquiera de las otras cosas de las que estoy a punto de hablar ...

Análisis de estricción

La pereza se trata de evitar el trabajo a menos que sea necesario. Si el compilador puede determinar que un resultado dado será "siempre" necesario, entonces no molestará almacenar el cálculo y realizarlo más tarde; simplemente lo realizará directamente, porque eso es más eficiente. Este es el llamado "análisis de rigor".

La cuestión, obviamente, es que el compilador no siempre puede detectar cuándo se puede hacer algo estricto. A veces necesitas darle al compilador algunas pistas. (No conozco ninguna forma fácil de determinar si el análisis de rigurosidad ha hecho lo que usted cree que tiene, aparte de vadear la salida del Núcleo).

En línea

Si llama a una función, y el compilador puede decir a qué función está llamando, puede tratar de "alinear" esa función, es decir, reemplazar la llamada de función con una copia de la función en sí misma. La sobrecarga de una llamada a la función suele ser bastante pequeña, pero la inclusión a menudo permite otras optimizaciones que, de otro modo, no hubieran sucedido, por lo que la inversión puede ser una gran ganancia.

Las funciones solo están en línea si son "lo suficientemente pequeñas" (o si agrega un pragma específicamente para enmendar). Además, las funciones solo pueden incluirse si el compilador puede decir qué función está llamando. Hay dos formas principales que el compilador podría ser incapaz de decir:

  • Si la función que está llamando se transfiere desde otro lugar. Por ejemplo, cuando se compila la función de filter , no puede alinear el predicado de filtro, porque es un argumento proporcionado por el usuario.

  • Si la función que está llamando es un método de clase y el compilador no sabe qué tipo está involucrado. Por ejemplo, cuando se compila la función sum , el compilador no puede alinear la función + , porque la sum funciona con varios tipos de números diferentes, cada uno de los cuales tiene una función + diferente.

En este último caso, puede usar el {-# SPECIALIZE #-} pragma para generar versiones de una función que están codificadas de forma rígida para un tipo particular. Por ejemplo, {-# SPECIALIZE sum :: [Int] -> Int #-} compilaría una versión de sum codificada para el tipo Int , lo que significa que + puede incluirse en esta versión.

Sin embargo, tenga en cuenta que nuestra nueva función de sum especial solo se ejecutará cuando el compilador sepa que estamos trabajando con Int . De lo contrario, se llama a la sum polimórfica original. De nuevo, la sobrecarga de llamada a la función real es bastante pequeña. Son las optimizaciones adicionales que la línea interna puede habilitar las que son beneficiosas.

Eliminación común de subexpresiones

Si un determinado bloque de código calcula el mismo valor dos veces, el compilador puede reemplazarlo con una sola instancia del mismo cálculo. Por ejemplo, si lo haces

(sum xs + 1) / (sum xs + 2)

entonces el compilador podría optimizar esto para

let s = sum xs in (s+1)/(s+2)

Es de esperar que el compilador siempre haga esto. Sin embargo, aparentemente en algunas situaciones esto puede provocar un peor rendimiento, no mejor, por lo que GHC no siempre hace esto. Francamente, realmente no entiendo los detalles detrás de este. Pero la conclusión es que si esta transformación es importante para usted, no es difícil hacerlo manualmente. (Y si no es importante, ¿por qué te preocupas?)

Expresiones de casos

Considera lo siguiente:

foo (0:_ ) = "zero" foo (1:_ ) = "one" foo (_:xs) = foo xs foo ( []) = "end"

Las primeras tres ecuaciones comprueban si la lista no está vacía (entre otras cosas). Pero comprobar lo mismo tres veces es un desperdicio. Afortunadamente, es muy fácil para el compilador optimizar esto en varias expresiones de casos anidados. En este caso, algo así como

foo xs = case xs of y:ys -> case y of 0 -> "zero" 1 -> "one" _ -> foo ys [] -> "end"

Esto es bastante menos intuitivo, pero más eficiente. Debido a que el compilador puede hacer fácilmente esta transformación, no tiene que preocuparse por ello. Simplemente escriba su coincidencia de patrón de la manera más intuitiva posible; el compilador es muy bueno en reordenar y reorganizar esto para hacerlo lo más rápido posible.

Fusión

La expresión idiomática estándar de Haskell para el procesamiento de listas es encadenar funciones que toman una lista y producen una lista nueva. El ejemplo canónico es

map g . map f

Desafortunadamente, aunque la pereza garantiza saltarse el trabajo innecesario, todas las asignaciones y desasignaciones para la lista intermedia reducen el rendimiento. "Fusión" o "deforestación" es donde el compilador intenta eliminar estos pasos intermedios.

El problema es que la mayoría de estas funciones son recursivas. Sin la recursión, sería un ejercicio elemental en la creación de líneas para aplastar todas las funciones en un gran bloque de código, ejecutar el simplificador sobre él y producir código realmente óptimo sin listas intermedias. Pero debido a la recursión, eso no funcionará.

Puedes usar {-# RULE #-} pragmas para arreglar algo de esto. Por ejemplo,

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

Ahora, cada vez que GHC ve el map aplicado al map , lo divide en una sola pasada sobre la lista, eliminando la lista intermedia.

El problema es que esto solo funciona para el map seguido del map . Hay muchas otras posibilidades: map seguido de filter , filter seguido de map , etc. En lugar de codificar manualmente una solución para cada uno de ellos, se inventó la llamada "fusión de flujo". Este es un truco más complicado, que no describiré aquí.

Lo largo y lo corto de esto es: todos estos son trucos especiales de optimización escritos por el programador . GHC en sí no sabe nada sobre la fusión; todo está en la lista de bibliotecas y otras bibliotecas de contenedores. Entonces, qué optimizaciones suceden depende de cómo se escriban las bibliotecas de sus contenedores (o, de manera más realista, qué bibliotecas eliges usar).

Por ejemplo, si trabajas con matrices Haskell ''98, no esperes ninguna fusión de ningún tipo. Pero entiendo que la biblioteca de vector tiene amplias capacidades de fusión. Se trata de las bibliotecas; el compilador solo proporciona el pragma RULES . (Por cierto, que es extremadamente poderoso. Como autor de la biblioteca, ¡puede usarlo para reescribir el código del cliente!)

Meta:

  • Estoy de acuerdo con la gente que dice "codificar primero, segundo perfil, optimizar tercero".

  • También estoy de acuerdo con la gente que dice "es útil tener un modelo mental de cuánto cuesta una determinada decisión de diseño".

Equilibrio en todas las cosas, y todo eso ...