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

GHC tiene muchas optimizaciones que puede realizar, pero no sé cuáles son todas, ni la probabilidad de que se realicen y en qué circunstancias.

Mi pregunta es: ¿qué transformaciones puedo esperar que se aplique cada vez, o casi? Si miro un fragmento de código que se ejecutará (evaluará) con frecuencia y mi primer pensamiento es "hmm, tal vez debería optimizar eso", en cuyo caso mi segundo pensamiento debería ser, "ni siquiera lo pienses, GHC tiene esto "?

Estaba leyendo el documento Stream Fusion: From Lists to Streams to Nothing at All , y la técnica que usaron para reescribir el procesamiento de listas en una forma diferente que las optimizaciones normales de GHC luego optimizarían de manera confiable en bucles simples era novedosa para mí. ¿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 sirve para responder la pregunta.

EDITAR: Estoy empezando una recompensa. Lo que me gustaría es una lista de transformaciones de nivel inferior como lambda / let / mayúsculas y minúsculas, especialización de argumento tipo / constructor / función, análisis de rigidez y unboxing, trabajador / envoltorio, y cualquier otra cosa significativa que haga GHC que haya dejado fuera , junto con explicaciones y ejemplos de código 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 noocurrir. No espero explicaciones novedosas de cada transformación, un par de oraciones y ejemplos de código en línea pueden ser suficientes (o un enlace, si no es a veinte páginas de artículos científicos), siempre que el panorama general sea claro al final de la misma. Quiero poder ver un fragmento de código y adivinar si se compilará en un ciclo cerrado, o por qué no, o qué tendría que cambiar para hacerlo. (No estoy tan interesado aquí en los grandes marcos de optimización como la fusión de flujo (acabo de leer un documento sobre eso); más en el tipo de conocimiento que tienen las personas que escriben estos marcos).

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

Por detalles, lo mejor que puede hacer es ver cómo se compila un programa específico. La mejor manera de ver qué optimizaciones se están realizando es compilar el programa de forma detallada, utilizando la -vbandera. 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_stackOverflow_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 primero *** Simplifier:hasta el último, donde ocurren 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, cuando implementan muchas optimizaciones, simplemente crean reglas de reescritura para propagar los cambios en lugar de tener que hacerlo manualmente. El simplificador abarca una serie de optimizaciones simples, incluidas la integración y la fusión. La principal limitación de esto que sé es que GHC se niega a las funciones recursivas en línea, y que las cosas deben nombrarse 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 sean polimórficas; son específicas de los tipos con los que se llama. También puede decirle al compilador que haga esto con el SPECIALISEpragma. 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 va a utilizar, no puede optimizar esto en absoluto. Sin embargo, si ve que se usa en un Int, ahora puede crear una nueva versión, que solo difiere en el tipo:

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

  Luego, las reglas que se mencionan 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 clases de tipos y variables de tipos.

  La fuente aquí tiene un montón de notas.

• Flotar

  EDITAR: Aparentemente no entendí esto antes. Mi explicación ha cambiado por completo.

  La idea básica de esto es mover los cálculos que no deberían repetirse fuera de las funciones. Por ejemplo, supongamos que tenemos esto:

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

  En el lambda anterior, cada vez que se llama a la función, yse vuelve a calcular. Una mejor función, que flotando produce, 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, se guarda el cálculo repetido.

  La fuente es muy legible en este caso.

  Por el momento, las uniones entre dos lambdas adyacentes no están flotando. 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 floatInwardses flotar en las ramas de un caso, para que no asignemos cosas, las guardemos en la pila y luego 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 se vevalúa como False, entonces asignando x, lo que presumiblemente es algo grande, hemos desperdiciado 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 posteriormente se reemplaza por el simplificador con

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

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

  1. Flotar en flotadores permite entrar en casedeclaraciones, mientras que flotar fuera trata con funciones.
  2. Hay un orden fijo de pases, por lo que no deberían alternarse 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 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 pasa esos argumentos usando llamada por valor, en lugar de llamada por necesidad. Dado que puedes evadir los gastos generales de los thunks, esto suele ser mucho más rápido. Muchos problemas de rendimiento en Haskell surgen de este error de paso o del código simplemente no es lo suficientemente estricto. Un ejemplo sencillo es la diferencia entre usar foldr, foldlyfoldl'para resumir una lista de enteros: el primero causa el desbordamiento de la pila, el segundo causa el desbordamiento del montón y el último funciona bien, debido a la rigidez. Este es probablemente el más fácil de entender y el mejor documentado de todos estos. Creo que el polimorfismo y el código CPS a menudo derrotan esto.

• Trabajador Wrapper se une

  La idea básica de la transformación trabajador / envoltorio es hacer un ciclo cerrado en una estructura simple, convirtiendo hacia y desde 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 Inten 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 se cubre el código 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 trabajador / envoltorio es muy general en lo que puede hacer.

• Subexpresió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 tiene dos expresiones que son iguales, tendrán el mismo valor. Por ejemplo, si fibes una calculadora de número 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 que tienen que ser sintácticamente iguales, no iguales por su valor. Por ejemplo, CSE no se activará en el siguiente código sin un montón de líneas:

  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.

• Liberate case

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

  Este módulo se acerca Corey busca casevariables libres. El criterio es: si hay una casevariable libre en la ruta a la llamada recursiva, entonces la llamada recursiva se reemplaza por un despliegue. Por ejemplo, en

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

  fSe reemplaza el interior . 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 sombrear. Simplificando, obtenemos

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

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

  Consulte a continuación para obtener más información sobre 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 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 a

  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 encasillando y desarmando repetidamente el frente de la lista. También tenga en cuenta que la alineación es crucial, ya que permite que se utilicen las definiciones nuevas y más eficientes, así como mejorar las definiciones recursivas.

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

  1. Las lambdas son explícitas y la aridad 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 de la función están presentes.
  5. Al menos uno de los argumentos es una aplicación de constructor.
  6. Ese argumento se analiza en mayúsculas y minúsculas en algún lugar de la función.

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

  Se especializan en un argumento xsólo si xse sólo se escrutó por una case, y no se pasa a una función ordinaria, o devuelto como parte del resultado.

Este era un archivo muy pequeño (12 líneas) y posiblemente no activó tantas optimizaciones (aunque creo que las hizo todas). Esto tampoco te 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 suceda. Esencialmente, esto significa que el trabajo no se realiza hasta que "haga algo" con el resultado. (A menos que haga una de varias cosas para desactivar deliberadamente la pereza).

Esto, obviamente, es un tema completo por derecho propio, y SO ya tiene muchas preguntas y respuestas al respecto.

En mi experiencia limitada, hacer que su código sea demasiado vago o demasiado estricto tiene penalizaciones de rendimiento mucho más grandes (en tiempo y espacio) que cualquiera de las otras cosas de las que voy a hablar ...

Análisis de rigurosidad

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

El problema, obviamente, es que el compilador no siempre puede detectar cuándo algo puede hacerse estricto. A veces necesitas darle al compilador pequeños consejos. (No conozco ninguna forma fácil de determinar si el análisis de rigurosidad ha hecho lo que usted cree que ha hecho, aparte de pasar por la salida de Core).

En línea

Si llama a una función y el compilador puede decir a qué función está llamando, puede intentar "en línea" esa función, es decir, reemplazar la llamada a la función con una copia de la función misma. La sobrecarga de una llamada de función suele ser bastante pequeña, pero la alineación a menudo permite que se realicen otras optimizaciones que de otra manera no hubieran sucedido, por lo que la alineación puede ser una gran victoria.

Las funciones solo están en línea si son "lo suficientemente pequeñas" (o si agrega un pragma que solicita específicamente la inserción). Además, las funciones solo pueden integrarse si el compilador puede decir a qué función está llamando. Hay dos formas principales por las que el compilador podría no saberlo:

• Si la función que está llamando se pasa desde otro lugar. Por ejemplo, cuando filterse compila la función, no puede alinear el predicado del 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 sumse compila la función, el compilador no puede alinear la +función, porque sumfunciona con varios tipos de números diferentes, cada uno de los cuales tiene una +función diferente .

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

Sin embargo, sumtenga en cuenta que nuestra nueva función especial solo se llamará cuando el compilador sepa que estamos trabajando Int. De lo contrario, sumse llama al polimórfico original . Nuevamente, la sobrecarga de la llamada a la función real es bastante pequeña. Son las optimizaciones adicionales que la alineación puede permitir lo que son beneficiosas.

Eliminación de subexpresión común

Si cierto 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 resultar en 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 por eso?)

Expresiones de caso

Considera lo siguiente:

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

Las tres primeras ecuaciones verifican si la lista no está vacía (entre otras cosas). Pero verificar lo mismo tres veces es un desperdicio. Afortunadamente, es muy fácil para el compilador optimizar esto en varias expresiones de caso anidadas. En este caso, algo 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 esta transformación fácilmente, no tiene que preocuparse por ello. Simplemente escriba su coincidencia de patrones de la manera más intuitiva posible; el compilador es muy bueno para reordenar y reorganizar esto para que sea lo más rápido posible.

Fusión

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

map g . map f

Desafortunadamente, aunque la pereza garantiza omitir el trabajo innecesario, todas las asignaciones y desasignaciones para el rendimiento intermedio de la savia de la lista. "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 recursividad, sería un ejercicio elemental en línea para aplastar todas las funciones en un gran bloque de código, ejecutar el simplificador sobre él y producir un código realmente óptimo sin listas intermedias. Pero debido a la recursividad, 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 mapaplicado map, lo divide en un solo paso sobre la lista, eliminando la lista intermedia.

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

En resumen: estos son todos trucos especiales de optimización escritos por el programador . GHC en sí mismo no sabe nada sobre fusión; todo está en la lista de bibliotecas y otras bibliotecas de contenedores. Entonces, qué optimizaciones suceden depende de cómo se escriben las bibliotecas de contenedores (o, de manera más realista, qué bibliotecas elige usar).

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

Meta:

• Estoy de acuerdo con las personas que dicen "codificar primero, perfilar segundo, optimizar tercero".

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

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

Si se utiliza un enlace let v = rhs en un solo lugar, puede contar con el compilador para alinearlo, 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 de trabajo. Considerar:

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

allí, la inclusión de v sería peligrosa porque el 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. Así que esencialmente puedes usar la regla:

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

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

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