online - haskell pagina oficial

Especialización con restricciones

Question

Tengo problemas para que GHC especialice una función con una restricción de clase. Tengo un ejemplo mínimo de mi problema aquí: Foo.hs y Main.hs Los dos archivos se compilan (GHC 7.6.2, ghc -O3 Main ) y se ejecutan.

NOTA: Foo.hs está realmente despojado. Si desea ver por qué es necesaria la restricción, puede ver un poco más de código here . Si coloco el código en un solo archivo o hago muchos otros cambios menores, GHC simplemente agrega la llamada a plusFastCyc . Esto no sucederá en el código real porque plusFastCyc es demasiado grande para que GHC se plusFastCyc , incluso cuando está marcado INLINE . El punto es especializar la llamada a plusFastCyc , no en línea. plusFastCyc se llama en muchos lugares en el código real, por lo que duplicar una función tan grande no sería deseable, incluso si pudiera forzar a GHC a hacerlo.

El código de interés es el plusFastCyc en Foo.hs , reproducido aquí:

{-# INLINEABLE plusFastCyc #-}
{-# SPECIALIZE plusFastCyc :: 
         forall m . (Factored m Int) => 
              (FastCyc (VT U.Vector m) Int) -> 
                   (FastCyc (VT U.Vector m) Int) -> 
                        (FastCyc (VT U.Vector m) Int) #-}

-- Although the next specialization makes `fcTest` fast,
-- it isn''t useful to me in my real program because the phantom type M is reified
-- {-# SPECIALIZE plusFastCyc :: 
--          FastCyc (VT U.Vector M) Int -> 
--               FastCyc (VT U.Vector M) Int -> 
--                    FastCyc (VT U.Vector M) Int #-}

plusFastCyc :: (Num (t r)) => (FastCyc t r) -> (FastCyc t r) -> (FastCyc t r)
plusFastCyc (PowBasis v1) (PowBasis v2) = PowBasis $ v1 + v2

El archivo Main.hs tiene dos controladores: vtTest , que se ejecuta en ~ 3 segundos, y fcTest , que se ejecuta en ~ 83 segundos cuando se compila con -O3 utilizando la especialización forall ''d.

El núcleo muestra que para la prueba vtTest , el código de adición se está especializando a vectores Unboxed sobre Int s, etc., mientras que el código de vector genérico se usa para fcTest . En la línea 10, puede ver que GHC escribe una versión especializada de plusFastCyc , en comparación con la versión genérica en la línea 167. La regla para la especialización está en la línea 225. Creo que esta regla debería main6 en la línea 270. ( main6 llamadas main6 se main6 iterate main8 y , entonces main8 es donde plusFastCyc debería estar especializado.)

Mi objetivo es hacer fcTest tan rápido como vtTest al especializar plusFastCyc . He encontrado dos formas de hacer esto:

1. Llamada de Explicity en inline desde GHC.Exts en fcTest .
2. Elimine la restricción Factored m Int en plusFastCyc .

La opción 1 no es satisfactoria porque en la base de código real más plusFastCyc es una operación de uso frecuente y una función muy grande, por lo que no debe incluirse en cada uso. Más bien, GHC debería llamar a una versión especializada de plusFastCyc . La opción 2 no es realmente una opción porque necesito la restricción en el código real.

He intentado una variedad de opciones usando (y no usando) INLINE , INLINABLE y SPECIALIZE , pero nada parece funcionar. ( EDITAR : Puede haber eliminado demasiado de plusFastCyc para que mi ejemplo sea pequeño, por lo que INLINE podría causar que la función esté en línea. Esto no sucede en mi código real porque plusFastCyc es tan grande). En este ejemplo en particular, No match_co: needs more cases ningún match_co: needs more cases o RULE: LHS too complicated to desugar (y here ) las advertencias, aunque estaba recibiendo muchas advertencias de match_co antes de minimizar el ejemplo. Presumiblemente, el "problema" es la restricción Factored m Int en la regla; si realizo cambios a esa restricción, fcTest ejecuta tan rápido como vtTest .

¿Estoy haciendo algo que a GHC simplemente no le gusta? ¿Por qué GHC no especializará el plusFastCyc y cómo puedo hacerlo?

ACTUALIZAR

El problema persiste en GHC 7.8.2, por lo que esta pregunta sigue siendo relevante.

Answer 1

GHC también ofrece una opción para SPECIALIZE una declaración de instancia de clase de tipo. Intenté esto con el código (ampliado) de Foo.hs , poniendo lo siguiente:

instance (Num r, V.Vector v r, Factored m r) => Num (VT v m r) where 
    {-# SPECIALIZE instance ( Factored m Int => Num (VT U.Vector m Int)) #-}
    VT x + VT y = VT $ V.zipWith (+) x y

Este cambio, sin embargo, no logró la aceleración deseada. Lo que logró esa mejora en el rendimiento fue agregar manualmente una instancia especializada para el tipo VT U.Vector m Int con las mismas definiciones de funciones, de la siguiente manera:

instance (Factored m Int) => Num (VT U.Vector m Int) where 
    VT x + VT y = VT $ V.zipWith (+) x y

Esto requiere agregar OverlappingInstances FlexibleInstances en LANGUAGE .

Curiosamente, en el programa de ejemplo, la aceleración obtenida con la instancia superpuesta permanece incluso si elimina todos los INLINABLE SPECIALIZE e INLINABLE .