Que otimizações o GHC pode executar com confiabilidade?

183

O GHC tem muitas otimizações que pode executar, mas não sei o que são, nem qual a probabilidade de serem executadas e em que circunstâncias.

Minha pergunta é: que transformações posso esperar que seja aplicada toda vez ou quase isso? Se eu olhar para um pedaço de código que será executado (avaliado) com frequência e meu primeiro pensamento for "hmm, talvez eu deva otimizar isso", em quais casos meu segundo pensamento será ", nem pense nisso, GHC conseguiu isso "?

Eu estava lendo o artigo Stream Fusion: De listas a fluxos a nada , e a técnica que eles usaram para reescrever o processamento de listas em uma forma diferente que as otimizações normais do GHC otimizariam de maneira confiável em loops simples eram novas para mim. Como posso saber quando meus próprios programas são elegíveis para esse tipo de otimização?

Há algumas informações no manual do GHC, mas isso apenas parte do caminho para responder à pergunta.

Edição: Estou começando uma recompensa. O que eu gostaria é de uma lista de transformações de nível inferior, como lambda / let / case-floating, especialização de argumento de tipo / construtor / função, análise de rigidez e unboxing, worker / wrapper e qualquer outra coisa significativa que o GHC faça que eu tenha deixado de fora , juntamente com explicações e exemplos de código de entrada e saída e, idealmente, ilustrações de situações em que o efeito total é maior que a soma de suas partes. E, idealmente, alguma menção de quando as transformações nãoacontecer. Não estou esperando explicações completas de todas as transformações, algumas frases e exemplos de código de linha única podem ser suficientes (ou um link, se não for para vinte páginas de artigos científicos), desde que o quadro geral seja claro até o final. Eu quero ser capaz de analisar um pedaço de código e fazer um bom palpite sobre se ele será compilado em um loop apertado, ou por que não, ou o que eu precisaria mudar para fazer isso. (Não estou muito interessado aqui nas grandes estruturas de otimização, como a fusão por fluxo (acabei de ler um artigo sobre isso); mais no tipo de conhecimento que as pessoas que escrevem essas estruturas têm.)

optimization haskell ghc glaebhoerl
fonte

Esta é uma pergunta muito digna. Escrever uma resposta digna é ... complicado.

MathematicsOrchid

Um ponto de partida realmente bom é o seguinte: aosabook.org/en/ghc.html

Gabriel Gonzalez

Em qualquer idioma, se seu primeiro pensamento for "talvez eu deva otimizar isso", seu segundo pensamento será "eu analisarei primeiro".

John L

Embora o tipo de conhecimento que você procura seja útil, e essa ainda seja uma boa pergunta, acho que você está realmente melhor atendido tentando fazer a menor otimização possível. Escreva o que você quer dizer, e só quando se torna evidente que você precisa , em seguida, pensar em fazer o código menos simples por causa do desempenho. Em vez de olhar para o código e pensar "que será executado com frequência, talvez eu deva otimizá-lo", deve ser apenas quando você estiver observando o código executando muito lentamente que você pensa "Eu devo descobrir o que é executado com frequência e otimizar isso" .

Ben

Eu antecipava completamente que parte chamaria as exortações para "dar um perfil!" :). Mas acho que o outro lado da moeda é que, se eu o perfilar e for lento, talvez eu possa reescrevê-lo ou ajustá-lo em uma forma que ainda seja de alto nível, mas o GHC possa otimizar melhor, em vez de otimizá-lo pessoalmente? O que requer o mesmo tipo de conhecimento. E se eu tivesse esse conhecimento em primeiro lugar, poderia me salvar de um ciclo de edição de perfil.

glaebhoerl

Respostas:

110

Esta página do GHC Trac também explica os passes bastante bem. Esta página explica a ordem de otimização, porém, como a maioria do Trac Wiki, está desatualizada.

Para detalhes, a melhor coisa a fazer é provavelmente ver como um programa específico é compilado. A melhor maneira de ver quais otimizações estão sendo executadas é compilar o programa verbalmente, usando o -vsinalizador. Tomando como exemplo o primeiro pedaço de Haskell que encontrei no meu computador:

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

Olhando desde o primeiro *** Simplifier: ao último, onde todas as fases de otimização acontecem, vemos bastante.

Primeiro de tudo, o simplificador funciona entre quase todas as fases. Isso facilita a escrita de muitos passes. Por exemplo, ao implementar muitas otimizações, elas simplesmente criam regras de reescrita para propagar as alterações, em vez de fazê-las manualmente. O simplificador abrange várias otimizações simples, incluindo inlining e fusão. A principal limitação disso que eu sei é que o GHC se recusa a incorporar funções recursivas e que as coisas precisam ser nomeadas corretamente para que a fusão funcione.

Em seguida, vemos uma lista completa de todas as otimizações realizadas:

Especializar-se

A idéia básica da especialização é remover o polimorfismo e a sobrecarga, identificando os locais onde a função é chamada e criando versões da função que não são polimórficas - elas são específicas para os tipos com as quais são chamadas. Você também pode dizer ao compilador para fazer isso com o SPECIALISEpragma. Como exemplo, considere uma função fatorial:
```
fac :: (Num a, Eq a) => a -> a
fac 0 = 1
fac n = n * fac (n - 1)
```
Como o compilador não conhece nenhuma propriedade da multiplicação a ser usada, ele não pode otimizar isso. Se, no entanto, ele for usado em um Int, agora ele poderá criar uma nova versão, diferindo apenas no tipo:
```
fac_Int :: Int -> Int
fac_Int 0 = 1
fac_Int n = n * fac_Int (n - 1)
```
Em seguida, as regras mencionadas abaixo podem ser acionadas e você acaba trabalhando com algo que não está na caixa Int s sem , o que é muito mais rápido que o original. Outra maneira de analisar a especialização é a aplicação parcial em dicionários de classes de tipo e variáveis de tipo.

A fonte aqui tem várias notas.
Flutuar

Edição: Eu aparentemente entendi errado isso antes. Minha explicação mudou completamente.

A idéia básica disso é mover cálculos que não devem ser repetidos fora de funções. Por exemplo, suponha que tenhamos o seguinte:
```
\x -> let y = expensive in x+y
```
No lambda acima, toda vez que a função é chamada, yé recalculada. Uma função melhor, que flutua produz, é
```
let y = expensive in \x -> x+y
```
Para facilitar o processo, outras transformações podem ser aplicadas. Por exemplo, isso acontece:
```
 \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
```
Mais uma vez, o cálculo repetido é salvo.

A fonte é muito legível neste caso.

No momento, as ligações entre duas lambdas adjacentes não são flutuadas. Por exemplo, isso não acontece:
```
\x y -> let t = x+x in ...
```
Indo a
```
 \x -> let t = x+x in \y -> ...
```
Flutuar para dentro

Citando o código fonte,

O principal objetivo de floatInwardsé flutuar nas ramificações de um caso, para não alocarmos as coisas, salvá-las na pilha e descobrir que elas não são necessárias na ramificação escolhida.

Como exemplo, suponha que tenhamos esta expressão:
```
let x = big in
    case v of
        True -> x + 1
        False -> 0
```
Se vavaliamos False, então, alocando x, o que é presumivelmente um grande problema, perdemos tempo e espaço. Flutuar para dentro corrige isso, produzindo o seguinte:
```
case v of
    True -> let x = big in x + 1
    False -> let x = big in 0
```
, que é posteriormente substituído pelo simplificador por
```
case v of
    True -> big + 1
    False -> 0
```
Este artigo , embora cubra outros tópicos, apresenta uma introdução bastante clara. Observe que, apesar de seus nomes, flutuar dentro e fora não entra em um loop infinito por dois motivos:
1. Float in floats permite casedeclarações, enquanto float out lida com funções.
2. Há uma ordem fixa de passes, portanto eles não devem alternar infinitamente.

Análise de demanda

A análise de demanda ou análise de rigidez é menos uma transformação e mais, como o nome sugere, um passe de coleta de informações. O compilador encontra funções que sempre avaliam seus argumentos (ou pelo menos alguns deles) e passa esses argumentos usando chamada por valor, em vez de chamada por necessidade. Como você evita as sobrecargas dos thunks, isso geralmente é muito mais rápido. Muitos problemas de desempenho no Haskell surgem da falha dessa passagem ou do código simplesmente não sendo suficientemente rigoroso. Um exemplo simples é a diferença entre usarfoldr , foldlefoldl'para somar uma lista de números inteiros - a primeira causa o estouro da pilha, a segunda causa o estouro da pilha e a última é executada corretamente, devido ao rigor. Este é provavelmente o mais fácil de entender e melhor documentado de todos eles. Eu acredito que o polimorfismo e o código CPS frequentemente derrotam isso.
Vinculações de Wrapper do Trabalhador

A idéia básica da transformação de trabalhador / invólucro é fazer um loop apertado em uma estrutura simples, convertendo para e a partir dessa estrutura nas extremidades. Por exemplo, considere esta função, que calcula o fatorial de um número.
```
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
```
Usando a definição de Intno GHC, temos
```
factorial :: Int -> Int
factorial (I# 0#) = I# 1#
factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
    I# down# -> down#)
```
Observe como o código é coberto em I#s? Podemos removê-los fazendo o seguinte:
```
factorial :: Int -> Int
factorial (I# n#) = I# (factorial# n#)

factorial# :: Int# -> Int#
factorial# 0# = 1#
factorial# n# = n# *# factorial# (n# -# 1#)
```
Embora esse exemplo específico também possa ter sido feito pelo SpecConstr, a transformação de trabalhador / wrapper é muito geral nas coisas que ele pode fazer.
Subexpressão comum

Essa é outra otimização realmente simples que é muito eficaz, como a análise de rigidez. A idéia básica é que, se você tiver duas expressões iguais, elas terão o mesmo valor. Por exemplo, se fibfor uma calculadora de número de Fibonacci, o CSE transformará
```
fib x + fib x
```
para dentro
```
let fib_x = fib x in fib_x + fib_x
```
que corta o cálculo pela metade. Infelizmente, isso pode ocasionalmente atrapalhar outras otimizações. Outro problema é que as duas expressões devem estar no mesmo lugar e que devem ser sintaticamente iguais, não iguais em valor. Por exemplo, o CSE não será acionado no seguinte código sem muita inlining:
```
x = (1 + (2 + 3)) + ((1 + 2) + 3)
y = f x
z = g (f x) y
```
No entanto, se você compilar via llvm, poderá obter parte disso combinado, devido ao seu passe de numeração de valor global.
Liberar caso

Essa parece ser uma transformação terrivelmente documentada, além do fato de poder causar explosão de código. Aqui está uma versão reformatada (e um pouco reescrita) da pequena documentação que encontrei:

Este módulo passa por cima Coree procura por casevariáveis livres. O critério é: se houver uma casevariável livre na rota para a chamada recursiva, a chamada recursiva será substituída por um desdobramento. Por exemplo, em
```
f = \ t -> case v of V a b -> a : f t
```
o interior fé substituído. fazer
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t
```
Observe a necessidade de sombreamento. Simplificando, temos
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)
```
Este é um código melhor, porque aé livre dentro do interior letrec, em vez de precisar de projeção v. Observe que isso lida com variáveis livres , ao contrário de SpecConstr, que lida com argumentos de forma conhecida.

Veja abaixo mais informações sobre o SpecConstr.
SpecConstr - isso transforma programas como
```
f (Left x) y = somthingComplicated1
f (Right x) y = somethingComplicated2
```
para 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 um exemplo estendido, considere esta definição de last:
```
last [] = error "last: empty list"
last (x:[]) = x
last (x:x2:xs) = last (x2:xs)
```
Nós o transformamos primeiro em
```
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
```
Em seguida, o simplificador é executado e temos
```
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
```
Observe que o programa agora está mais rápido, pois não estamos repetidamente encaixotando e descompactando a frente da lista. Observe também que o inlining é crucial, pois permite que as novas definições mais eficientes sejam realmente usadas, além de melhorar as definições recursivas.

SpecConstr é controlado por várias heurísticas. Os mencionados no artigo são os seguintes:
1. As lambdas são explícitas e a aridade é a.
2. O lado direito é "suficientemente pequeno", algo controlado por uma bandeira.
3. A função é recursiva e a chamada especializada é usada no lado direito.
4. Todos os argumentos para a função estão presentes.
5. Pelo menos um dos argumentos é um aplicativo construtor.
6. Esse argumento é analisado por caso em algum lugar da função.
No entanto, as heurísticas quase certamente mudaram. De fato, o artigo menciona uma sexta heurística alternativa:

Especialize-se em um argumento xapenas se xfor examinado apenas por a casee não for passado para uma função comum ou retornado como parte do resultado.

Este era um arquivo muito pequeno (12 linhas) e, portanto, possivelmente não desencadeou tantas otimizações (embora eu ache que tenha feito todas elas). Isso também não diz por que ele escolheu esses passes e por que os colocou nessa ordem.

gereeter
fonte

Agora estamos chegando a algum lugar! Comentários: Você parece ter uma frase de corte na parte sobre Specialize. Não vejo o ponto de flutuação: para que serve? Como ele decide se entra ou sai da boia (por que não entra em loop)? Tive a impressão de algum lugar que GHC não fez CSE em tudo , mas, aparentemente, que estava enganado. Sinto que estou me perdendo em detalhes, em vez de ver uma imagem grande ... o tópico é ainda mais complicado do que eu pensava. Talvez minha pergunta seja impossível e não há como ganhar essa intuição, exceto uma tonelada de experiência ou trabalhando no GHC?

glaebhoerl

Bem, eu não sei, mas nunca trabalhei no GHC, então você deve ter alguma intuição.

Gereeter # 04/11

Corrigi os problemas que você mencionou.

Gereeter 04/11/12

Além disso, sobre o cenário geral, é minha opinião que realmente não há um. Quando quero adivinhar quais otimizações serão executadas, desço uma lista de verificação. Então eu faço novamente, para ver como cada passe vai mudar as coisas. E de novo. Essencialmente, eu jogo o compilador. O único esquema de otimização que conheço que realmente tem uma "imagem grande" é a supercompilação.

Gereeter 4/11/12

O que você quer dizer com "as coisas precisam ser nomeadas corretamente para que a fusão funcione" exatamente?

Vincent Beffara

Preguiça

Não é uma "otimização de compilador", mas é algo garantido pela especificação da linguagem, para que você possa sempre contar com isso. Essencialmente, isso significa que o trabalho não é realizado até que você "faça algo" com o resultado. (A menos que você faça uma de várias coisas para deliberadamente desativar a preguiça.)

Obviamente, esse é um tópico inteiro e, portanto, o SO já tem muitas perguntas e respostas.

Na minha experiência limitada, tornar seu código muito preguiçoso ou muito rigoroso tem penalidades de desempenho muito maiores (no tempo e no espaço) do que qualquer outra coisa sobre a qual estou prestes a falar ...

Análise de rigidez

Preguiça é evitar o trabalho, a menos que seja necessário. Se o compilador puder determinar que um determinado resultado será "sempre" necessário, não será necessário armazenar o cálculo e executá-lo posteriormente; apenas executará diretamente, porque é mais eficiente. Isso é chamado de "análise de rigidez".

O problema, obviamente, é que o compilador nem sempre pode detectar quando algo pode ser feito estrito. Às vezes, você precisa dar pequenas dicas ao compilador. (Não conheço nenhuma maneira fácil de determinar se a análise de rigidez fez o que você pensa que tem, além de analisar a saída do Core.)

Inlining

Se você chamar uma função e o compilador puder dizer para qual função você está chamando, ele poderá tentar "incorporar" essa função - ou seja, substituir a chamada de função por uma cópia da própria função. A sobrecarga de uma chamada de função geralmente é muito pequena, mas o inlining geralmente permite que outras otimizações ocorram, o que não teria acontecido de outra forma, portanto o inlining pode ser uma grande vitória.

As funções são incorporadas apenas se forem "suficientemente pequenas" (ou se você adicionar um pragma especificamente solicitando inlining). Além disso, as funções só podem ser incorporadas se o compilador puder dizer qual função você está chamando. Há duas maneiras principais que o compilador pode não conseguir dizer:

Se a função que você está chamando for passada de outro lugar. Por exemplo, quando ofilter função é compilada, você não pode incorporar o predicado de filtro, porque é um argumento fornecido pelo usuário.
Se a função que você está chamando é um método de classe e o compilador não sabe que tipo está envolvido. Por exemplo, quando a sumfunção é compilada, o compilador não pode incorporar a +função, porque sumfunciona com vários tipos de números diferentes, cada um com um+ função .

No último caso, você pode usar o {-# SPECIALIZE #-}pragma para gerar versões de uma função codificada para um tipo específico. Por exemplo, {-# SPECIALIZE sum :: [Int] -> Int #-}compilaria uma versão dosum código embutido para o Inttipo, o que significa que +pode ser incorporado nesta versão.

Note, no entanto, que nossa nova sumfunção especial só será chamada quando o compilador puder dizer que estamos trabalhando Int. Caso contrário, o original, polimórficosum é chamado. Novamente, a sobrecarga real da chamada de função é bastante pequena. São as otimizações adicionais que o inlining pode permitir que são benéficas.

Eliminação de subexpressão comum

Se um determinado bloco de código calcular o mesmo valor duas vezes, o compilador poderá substituí-lo por uma única instância da mesma computação. Por exemplo, se você fizer

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

o compilador pode otimizar isso para

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

Você pode esperar que o compilador sempre faça isso. No entanto, aparentemente, em algumas situações, isso pode resultar em pior desempenho, nem melhor, portanto o GHC nem sempre faz isso. Francamente, eu realmente não entendo os detalhes por trás deste. Mas o ponto principal é que, se essa transformação é importante para você, não é difícil fazer isso manualmente. (E se não é importante, por que você está se preocupando com isso?)

Expressões de caso

Considere o seguinte:

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

Todas as três primeiras equações verificam se a lista está vazia (entre outras coisas). Mas verificar a mesma coisa três vezes é um desperdício. Felizmente, é muito fácil para o compilador otimizar isso em várias expressões de caso aninhadas. Nesse caso, algo como

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

Isso é bem menos intuitivo, mas mais eficiente. Como o compilador pode facilmente fazer essa transformação, você não precisa se preocupar com isso. Basta escrever sua correspondência de padrões da maneira mais intuitiva possível; o compilador é muito bom em reordenar e reorganizar isso para torná-lo o mais rápido possível.

Fusão

O idioma padrão Haskell para o processamento de listas é encadear funções que levam uma lista e produzem uma nova lista. O exemplo canônico sendo

map g . map f

Infelizmente, embora a preguiça garanta pular o trabalho desnecessário, todas as alocações e desalocações para o desempenho intermediário da lista diminuem. "Fusão" ou "desmatamento" é onde o compilador tenta eliminar essas etapas intermediárias.

O problema é que a maioria dessas funções é recursiva. Sem a recursão, seria um exercício elementar inline alinhar todas as funções em um grande bloco de código, executar o simplificador sobre ele e produzir um código realmente ótimo sem listas intermediárias. Mas por causa da recursão, isso não vai funcionar.

Você pode usar {-# RULE #-}pragmas para corrigir um pouco disso. Por exemplo,

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

Agora, toda vez que o GHC vê o mappedido map, ele o esmaga em uma única passagem pela lista, eliminando a lista intermediária.

O problema é que isso funciona apenas para mapseguido de map. Existem muitas outras possibilidades - mapseguidas por filter, filterseguidas por mapetc. Em vez de codificar manualmente uma solução para cada uma delas, a chamada "fusão de fluxo" foi inventada. Esse é um truque mais complicado, que não descreverei aqui.

O mais longo e mais curto é: Estes são todos os truques especiais de otimização escritos pelo programador . O próprio GHC não sabe nada sobre fusão; está tudo nas bibliotecas de listas e outras bibliotecas de contêineres. Portanto, quais otimizações acontecem depende de como as bibliotecas de contêiner são gravadas (ou, mais realista, quais bibliotecas você escolhe usar).

Por exemplo, se você trabalha com matrizes Haskell '98, não espere qualquer tipo de fusão. Mas entendo que a vectorbiblioteca possui amplos recursos de fusão. É tudo sobre as bibliotecas; o compilador apenas fornece o RULESpragma. (A propósito, o que é extremamente poderoso. Como autor de uma biblioteca, você pode usá-lo para reescrever o código do cliente!)

Meta:

Concordo com as pessoas que dizem "codifique primeiro, perfil segundo, otimize terceiro".
Também concordo com as pessoas que dizem "é útil ter um modelo mental para quanto custa uma determinada decisão de projeto".

Equilíbrio em todas as coisas, e tudo o que ...

MathematicsOrchid
fonte

it's something guaranteed by the language specification ... work is not performed until you "do something" with the result.

- não exatamente. A especificação da linguagem promete semântica não estrita ; não promete nada sobre se o trabalho supérfluo será ou não executado.

Dan Burton

@DanBurton Sure. Mas isso não é fácil de explicar em algumas frases. Além disso, como o GHC é quase a única implementação existente do Haskell, o fato de o GHC ser preguiçoso é bom o suficiente para a maioria das pessoas.

MatemáticoOrchid #

@ MathematicsOrchid: avaliações especulativas são um contra-exemplo interessante, embora eu concorde que provavelmente seja demais para um iniciante.

quer

Sobre a CSE: Minha impressão é que isso é feito quase nunca, porque pode introduzir compartilhamento indesejado e, portanto, spaceleaks.

Joachim Breitner

Desculpe por (a) não responder antes e (b) por não aceitar sua resposta. O que é longo e impressionante, mas não cobre o território que eu queria. O que eu gostaria é uma lista de transformações de nível inferior, como lambda / let / case-floating, especialização de argumento de tipo / construtor / função, análise de rigidez e unboxing (que você mencionou), worker / wrapper e qualquer outra coisa que o GHC faça, junto com explicações e exemplos de código de entrada e saída e, idealmente, exemplos de seus efeitos combinados e aqueles em que as transformações não acontecem. Eu acho que eu deveria fazer uma recompensa?

glaebhoerl

Se uma ligação let v = rhs for usada em apenas um lugar, você poderá contar com o compilador para incorporá-lo, mesmo se rhs for grande.

A exceção (que quase não é uma no contexto da pergunta atual) são as lambdas que correm o risco de duplicar o trabalho. Considerar:

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

lá inlining v seria perigoso porque o uso (sintático) seria traduzido em 99 avaliações extras de rhs. No entanto, nesse caso, é improvável que você deseje incorporá-lo manualmente. Então, basicamente você pode usar a regra:

Se você considerar incluir um nome que apareça apenas uma vez, o compilador fará isso de qualquer maneira.

Como um corolário feliz, usar uma ligação let simplesmente para decompor uma declaração longa (com esperança de ganhar clareza) é essencialmente gratuito.

Isso vem de community.haskell.org/~simonmar/papers/inline.pdf, que inclui muito mais informações sobre inlining.

Daniel
fonte