Optimización de Haskell Inner Loops

Todavía estoy trabajando en mi implementación de SHA1 en Haskell. ahora tengo una implementación funcional y este es el bucle interno:Optimización de Haskell Inner Loops

iterateBlock' :: Int -> [Word32] -> Word32 -> Word32 -> Word32 -> Word32 -> Word32 -> [Word32] 
iterateBlock' 80 ws a b c d e = [a, b, c, d, e] 
iterateBlock' t (w:ws) a b c d e = iterateBlock' (t+1) ws a' b' c' d' e' 
    where 
    a' = rotate a 5 + f t b c d + e + w + k t 
    b' = a 
    c' = rotate b 30 
    d' = c 
    e' = d

El perfilador me dice que esta función toma un tercio del tiempo de ejecución de mi aplicación. No puedo pensar en otra forma de optimizarlo más allá de tal vez incluir las variables temporales, pero creo que O2 hará eso por mí de todos modos.

¿Alguien puede ver una optimización significativa que se puede aplicar aún más?

FYI las llamadas k y f están a continuación. Son tan simples que no creo que haya una forma de optimizar estos otros. A menos que el módulo Data.Bits sea lento

f :: Int -> Word32 -> Word32 -> Word32 -> Word32 
f t b c d 
    | t <= 19 = (b .&. c) .|. ((complement b) .&. d) 
    | t <= 39 = b `xor` c `xor` d 
    | t <= 59 = (b .&. c) .|. (b .&. d) .|. (c .&. d) 
    | otherwise = b `xor` c `xor` d 

k :: Int -> Word32 
k t 
    | t <= 19 = 0x5A827999 
    | t <= 39 = 0x6ED9EBA1 
    | t <= 59 = 0x8F1BBCDC 
    | otherwise = 0xCA62C1D6

Fuente

2011-11-14 Ana

Sin intentarlo, supongo que gran parte del problema es mantener sus datos de bloque en una lista (demasiado tráfico de punto/memoria). Intentaría moverme a un vector no empaquetado de 'Word32' y desenrollar manualmente el ciclo. A falta de eso, pruébelo con una estructura estricta/sin empaquetar que contenga 'a',' b', 'c',' d', y 'e'; entonces solo tendrías que pasar una variable (y estarías seguro de ponerle un patrón de explosión, ¿no?). –

También trataría de reemplazar todo el '(<=)' con una tabla de búsqueda, aunque no estoy seguro de que sea de mucha ayuda. –

Otra cosa: a menudo es una buena idea escribir funciones aritméticas ajustadas en C y llamarlas usando el FFI. Si tiene cuidado de no presentar efectos secundarios, el tiempo de ejecución puede usar una llamada rápida a C que le da un buen rendimiento. – fuz

En cuanto al núcleo producido por ghc-7.2.2, la alineación funciona bien. Lo que no funciona tan bien es que en cada iteración un par de valores de Word32 se desempaquetan primero, para realizar el trabajo, y luego se vuelven a empaquetar para la siguiente iteración. Unboxing y re-boxing pueden costar una cantidad sorprendentemente grande de tiempo (y asignación). Probablemente pueda evitar eso usando Word en lugar de Word32. No pudo usar rotate desde Data.Bits, pero tendría que implementarlo usted mismo (no es difícil) para que funcione también en sistemas de 64 bits. Para a', debería enmascarar manualmente los bits altos.

Otro punto que parece no ser óptimo es que en cada iteración t se compara con 19, 39 y 59 (si es lo suficientemente grande), por lo que el cuerpo del bucle contiene cuatro ramas. Probablemente sea más rápido si divide iterateBlock' en cuatro bucles (0-19, 20-39, 40-59, 60-79) y usa constantes k1, ..., k4 y cuatro funciones f1, ..., f4 (sin el parámetro t) para evitar ramas y tener un tamaño de código más pequeño para cada ciclo.

Y, como dijo Thomas, el uso de una lista para los datos del bloque no es óptimo, una matriz/vector de Word unboxed probablemente también sea útil.

Con los patrones de explosión, el núcleo se ve mucho mejor. Quedan dos o tres puntos menos que ideales.

     (GHC.Prim.narrow32Word# 
         (GHC.Prim.plusWord# 
          (GHC.Prim.narrow32Word# 
           (GHC.Prim.plusWord# 
            (GHC.Prim.narrow32Word# 
            (GHC.Prim.plusWord# 
             (GHC.Prim.narrow32Word# 
              (GHC.Prim.plusWord# 
               (GHC.Prim.narrow32Word# 
               (GHC.Prim.or# 
                (GHC.Prim.uncheckedShiftL# sc2_sEn 5) 
                (GHC.Prim.uncheckedShiftRL# sc2_sEn 27))) 
               y#_aBw)) 
             sc6_sEr)) 
            y#1_XCZ)) 
          y#2_XD6))

Ver todos estos narrow32Word#? Son baratos, pero no gratuitos. Solo se necesita lo más externo, puede haber un poco para cosechar codificando manualmente los pasos y usando Word.

Luego las comparaciones de t con 19, ..., aparecen dos veces, una para determinar la constante k, y una para la transformación f. Las comparaciones por sí solas son baratas, pero causan ramas y sin ellas, puede ser posible una mayor inclusión. Espero que también se pueda ganar un poco aquí.

Y aún así, la lista. Eso significa que w no se puede desempaquetar, el núcleo podría ser más simple si w no estuvieran disponibles.

Fuente

2011-11-14 22:33:44

Agregué patrones de explosión a todos los parámetros (!) De todas las funciones (excepto 'ws'), que hicieron funcionar el unboxing. – fuz

Buen descubrimiento. Sin embargo, no necesitas patrones de explosión en _todos_ parámetros, con flequillos en 'a, b, c, d, e, a'', todas las rosas, k y f están en línea, todo unboxable sin caja. –

sí. En general, es una buena idea colocar bang-patterns en argumentos que se supone que son estrictos. – fuz

Optimización de Haskell Inner Loops

Respuesta

Cuestiones relacionadas