optimization - ¿Cómo usar correctamente el pragma SPECIALIZE de GHC?(Ejemplo: función puramente especializada de las monádicas usando Identity).

haskell explicit-specialization

Question

Como ejemplo, supongamos que quiero escribir un mapa monádico y no monádico sobre listas. Comenzaré con el monádico:

import Control.Monad
import Control.Monad.Identity
mapM'' :: (Monad m) => (a -> m b) -> ([a] -> m [b])
mapM'' _ [] = return []
mapM'' f (x:xs) = liftM2 (:) (f x) (mapM f xs)

Ahora quiero reutilizar el código para escribir el map puro (en lugar de repetir el código):

map'' :: (a -> b) -> ([a] -> [b])
map'' f = runIdentity . mapM'' (Identity . f)

¿Qué es necesario para hacer que el map'' esté tan optimizado como si estuviera escrito explícitamente como el map ? En particular:

1. Es necesario escribir

   {-# SPECIALIZE mapM'' :: (a -> Identity b) -> ([a] -> Identity [b]) #-}

   ¿o GHC optimiza el map'' sí mismo (descartando por completo la Identity )?

2. ¿Se necesita agregar algo más (más pragmas)?

3. ¿Cómo puedo verificar qué tan bien está optimizado el map'' compilado con el código explícitamente escrito para el map ?

Answer 1

Bueno, preguntémosle al compilador.

Compilando el módulo

module PMap where
import Control.Monad
import Control.Monad.Identity
mapM'' :: (Monad m) => (a -> m b) -> ([a] -> m [b])
mapM'' _ [] = return []
mapM'' f (x:xs) = liftM2 (:) (f x) (mapM f xs)
map'' :: (a -> b) -> ([a] -> [b])
map'' f = runIdentity . mapM'' (Identity . f)

con ghc -O2 -ddump-simpl -ddump-to-file PMap.hs (ghc-7.6.1, 7.4.2 produce lo mismo a excepción de nombres únicos) produce el siguiente núcleo para el map''

PMap.map''
:: forall a_afB b_afC. (a_afB -> b_afC) -> [a_afB] -> [b_afC]
[GblId,
Arity=2,
Caf=NoCafRefs,
Str=DmdType LS,
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
ConLike=True, WorkFree=True, Expandable=True,
Guidance=IF_ARGS [60 30] 160 40}]
PMap.map'' =
/ (@ a_c) (@ b_d) (f_afK :: a_c -> b_d) (eta_B1 :: [a_c]) ->
case eta_B1 of _ {
[] -> GHC.Types.[] @ b_d;
: x_afH xs_afI ->
GHC.Types.:
@ b_d
(f_afK x_afH)
(letrec {
go_ahZ [Occ=LoopBreaker]
:: [a_c] -> Data.Functor.Identity.Identity [b_d]
[LclId, Arity=1, Str=DmdType S]
go_ahZ =
/ (ds_ai0 :: [a_c]) ->
case ds_ai0 of _ {
[] ->
(GHC.Types.[] @ b_d)
`cast` (Sym <(Data.Functor.Identity.NTCo:Identity <[b_d]>)>
:: [b_d] ~# Data.Functor.Identity.Identity [b_d]);
: y_ai5 ys_ai6 ->
(GHC.Types.:
@ b_d
(f_afK y_ai5)
((go_ahZ ys_ai6)
`cast` (<Data.Functor.Identity.NTCo:Identity <[b_d]>>
:: Data.Functor.Identity.Identity [b_d] ~# [b_d])))
`cast` (Sym <(Data.Functor.Identity.NTCo:Identity <[b_d]>)>
:: [b_d] ~# Data.Functor.Identity.Identity [b_d])
}; } in
(go_ahZ xs_afI)
`cast` (<Data.Functor.Identity.NTCo:Identity <[b_d]>>
:: Data.Functor.Identity.Identity [b_d] ~# [b_d]))
}

Sip, solo cast s, sin gastos reales. Obtienes un trabajador local que actúa exactamente como lo hace el map .

En resumen: solo necesita -O2 , y puede verificar qué tan bien optimizado es el código mirando el núcleo ( -ddump-simpl ) o, si puede leerlo, en el ensamblaje producido ( -ddump-asm ) resp LLVM código de bit -ddump-llvm ).

Probablemente sea bueno elaborar un poco. Sobre

Es necesario escribir

{-# SPECIALIZE mapM'' :: (a -> Identity b) -> ([a] -> Identity [b]) #-}

¿o GHC optimiza el map'' sí mismo (descartando por completo la identidad)?

la respuesta es que si utiliza la especialización en el mismo módulo como se define la función general, entonces, en general, no necesita un {-# SPECIALISE #-} pragma, GHC crea la especialización por sí solo si ve algún beneficio en eso. En el módulo anterior, GHC creó la regla de especialización

"SPEC PMap.mapM'' [Data.Functor.Identity.Identity]" [ALWAYS]
forall (@ a_abG)
(@ b_abH)
($dMonad_sdL :: GHC.Base.Monad Data.Functor.Identity.Identity).
PMap.mapM'' @ Data.Functor.Identity.Identity
@ a_abG
@ b_abH
$dMonad_sdL
= PMap.mapM''_$smapM'' @ a_abG @ b_abH

que también beneficia cualquier uso de mapM'' en la mónada de Identity fuera del módulo de definición (si se compila con optimizaciones, y la mónada se reconoce como Identity a tiempo para que la regla se active).

Sin embargo, si GHC no entiende bien el tipo para especializarse, puede que no vea ningún beneficio y no se especialice (no lo sé lo suficiente como para saber si lo intentará de todos modos, hasta ahora he encontrado una especialización). vez que miré).

Si quieres estar seguro, mira el núcleo.

Si necesita la especialización en un módulo diferente, GHC no tiene ninguna razón para especializar la función cuando compila el módulo de definición, por lo que en ese caso es necesario un pragma. En lugar de un {-# SPECIALISE #-} pragma que exige una especialización para algunos tipos elegidos a mano, probablemente sea mejor, a partir de ghc-7, utilizar un pragma {-# INLINABLE #-} , de modo que (ligeramente modificado), el código fuente está disponible en los módulos de importación, lo que permite especializaciones para cualquier tipo requerido allí.

¿Se necesita agregar algo más (más pragmas)?

Por supuesto, diferentes usos pueden requerir diferentes pragmas, pero como regla general, {#- INLINABLE #-} es el que más deseas. Y, por supuesto, {-# RULES #-} puede hacer magia que el compilador no puede hacer solo.

¿Cómo puedo verificar qué tan bien está optimizado el map'' compilado con el código explícitamente escrito para el map ?

• Mire el código de bits producido core, asm o llvm, lo que mejor entienda (el núcleo es relativamente fácil).
• Compare el código producido con una especialización escrita a mano, si no está seguro desde el núcleo, y necesita saber. En última instancia, a menos que obtenga resultados intermedios idénticos en algún momento (core / cmm / asm / llvm), la evaluación comparativa es la única forma de saberlo con certeza.