18 votos

La rigurosidad de la optimización de asignación de memoria y en Haskell

He estado aprendiendo un poco de Haskell mediante la implementación de un algoritmo de selección de características.

Me he metido en el rendimiento a partir de los 20 años en un punto de referencia del conjunto de datos hacia 5s, donde el programa de C maneja el mismo conjunto de datos en 0.5 seg. El conjunto de datos se puede encontrar aquí. Para ejecutar, llamada el binario compilado así: ./Mrmr 10 test_nci9_s3.csv.

El código está aquí, y estoy interesado en la optimización de mutualInfoInnerLoop:

mutualInfoInnerLoop :: Double -> Data.Vector.Unboxed.Vector (Int, Int) -> Double -> (Int, Int, Double) -> Double
mutualInfoInnerLoop n xys !acc (!i, !j, !px_py)
    | n == 0 || px_py == 0 || pxy == 0 = acc
    | otherwise                        = pxy * logBase 2 ( pxy / px_py ) + acc
    where
        pxy = ( fromIntegral . U.foldl' accumEq2 0 $ xys ) / n
        accumEq2 :: Int -> (Int, Int) -> Int
        accumEq2 !acc (!i', !j')
            | i' == i && j' == j = acc + 1
            | otherwise          = acc

El analizador dice:

COST CENTRE                    MODULE               %time %alloc

mutualInfoInnerLoop            Main                  75.0   47.9
mutualInfo                     Main                  14.7   32.1
parseCsv                       Main                   5.9   13.1
CAF                            GHC.Float              1.5    0.0
readInt                        Main                   1.5    1.2
doMrmr                         Main                   1.5    4.0

Que muestra mutualInfoInnerLoop como hacer el 50% de los créditos, con el 75% del tiempo de ejecución en el programa. Las asignaciones son desconcertantes.

También, el Núcleo, para que la función tiene una firma:

mutualInfoInnerLoop_rXG
  :: GHC.Types.Double
     -> Data.Vector.Unboxed.Base.Vector (GHC.Types.Int, GHC.Types.Int)
     -> GHC.Types.Double
     -> (GHC.Types.Int, GHC.Types.Int, GHC.Types.Double)
     -> GHC.Types.Double
[GblId,
 Arity=4,
 Caf=NoCafRefs,
 Str=DmdType U(L)LU(L)U(U(L)U(L)U(L))m]

Mostrando la mayoría de los parámetros como ser Constantemente evaluados y en caja (en contraposición a la estricta y sin caja).

He intentado BangPatterns, he tratado de MagicHash, y me parece que no puede hacer que vaya más rápido.

Alguien tiene alguna sugerencia?

2voto

Dan Burton Puntos 26639

Estoy por el momento ningún experto en esto, pero yo veo una pequeña mejora. En su origen veo esto:

mutualInfo n ... = foldl' (mutualInfoInnerLoop n $ U.zip xs ys) ...

Usted no necesita comprobación n == 0 cada vez que se invoca la función, ya que nunca cambie el n argumento cuando se invoca. El xys argumento no cambia, lo que significa que pxy no cambia a través de las invocaciones, ya que depende únicamente de la xys y n. Vamos a tomar ventaja de estas cosas para asegurarse de que se crea una cerradura que evalúa estas cosas sólo una vez.

mutualInfoInnerLoop n xys
  | n == 0 || pxy == 0 = const
  | otherwise          = go
  where pxy = (fromIntegral . U.foldl' accumEq2 0 $ xys) / n
        accumEq2 :: Int -> (Int, Int) -> Int
        accumEq2 !acc (!i', !j')
              | i' == i && j' == j = acc + 1
              | otherwise          = acc
        go !acc (!i, !j, !px_py)
          | px_py == 0 = acc
          | otherwise  = pxy * logBase 2 ( pxy / px_py ) + acc

No estoy seguro de si GHC es lo suficientemente inteligente para realizar esta optimización en su propia cuenta, ni estoy seguro de que esto te ahorra mucho tiempo/espacio, pero es lo mejor que tengo. Con esos bang patrones salpicadas por todo, me pregunto si este es un caso de demasiado rigor.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X