Ottimizzazione dei loop interni Haskell

Ancora lavorando sulla mia implementazione SHA1 in Haskell. Ora ho un'implementazione di lavoro e questo è il ciclo interno:Ottimizzazione dei loop interni Haskell

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

Il profiler mi dice che questa funzione prende 1/3 del tempo di esecuzione della mia applicazione. Non riesco a pensare ad altro modo di ottimizzarlo ulteriormente se non di inserire le variabili temporanee, ma credo che -O2 lo farà comunque per me.

Qualcuno può vedere un'ottimizzazione significativa che può essere ulteriormente applicata?

FYI le chiamate kef sono riportate di seguito. Sono così semplici che non penso ci sia un modo per ottimizzare questi altri. A meno che il modulo DataBits sia 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

fonte

2011-11-14 Ana

Senza provare, sto indovinando un sacco di questo problema è mantenere i dati del blocco in un elenco (troppo punto/traffico di memoria). Cercherò di passare a un vettore unboxed di 'Word32' e srotolare manualmente il ciclo. In breve, provalo con una struttura rigida/decompressa contenente 'a',' b', 'c',' d' e 'e'; allora avresti solo bisogno di una variabile passata (e avresti la certezza di mettere un modello bang su di esso, giusto?). –

Vorrei anche provare a sostituire tutti i '(<=)' con una ricerca tabella, anche se non sono sicuro che sarà di grande aiuto. –

Un'altra cosa: spesso è una buona idea scrivere funzioni aritmetiche rigide in C e chiamarla usando l'FFI. Se si fa attenzione a non introdurre effetti collaterali, il runtime può utilizzare una chiamata rapida in C che offre buone prestazioni. – fuz

Guardando il core prodotto da ghc-7.2.2, l'inlining funziona bene. Ciò che non funziona così bene è che in ogni iterazione un paio di valori Word32 vengono eliminati per la prima volta, per eseguire il lavoro, e poi reinseriti per l'iterazione successiva. Unboxing e re-boxing possono costare una quantità sorprendentemente ampia di tempo (e allocazione). Probabilmente è possibile evitare questo utilizzando Word anziché Word32. Non è quindi possibile utilizzare rotate da DataBits, ma è necessario implementarlo manualmente (non è difficile) per farlo funzionare anche su sistemi a 64 bit. Per a' dovresti mascherare manualmente i bit alti.

Un altro punto che sembra subottimale è che in ogni iterazione t viene confrontato con 19, 39 e 59 (se è abbastanza grande), in modo che il corpo del loop contenga quattro rami. Sarà probabilmente più veloce se dividi iterateBlock' in quattro loop (0-19, 20-39, 40-59, 60-79) e usi le costanti k1, ..., k4 e le quattro funzioni f1, ..., f4 (senza il parametro t) per evitare diramazioni e avere dimensioni di codice inferiori per ogni ciclo.

E, come ha detto Thomas, l'utilizzo di un elenco per i dati di blocco non è ottimale, probabilmente anche un vettore/vettore di Word unbox.

Con i modelli di scoppio, il nucleo appare molto meglio. Restano due o tre punti in meno rispetto all'ideale.

     (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))

Vedi tutti questi narrow32Word#? Sono economici, ma non gratuiti. È necessario solo il più esterno, potrebbe esserci un po 'per raccogliere manualmente i passaggi e usando Word.

Quindi i confronti di t con 19, ..., vengono visualizzati due volte, una volta per determinare la costante e una volta per la trasformazione f. I paragoni da soli sono economici, ma causano rami e senza di essi, potrebbe essere possibile una ulteriore integrazione. Mi aspetto che si possa guadagnare un po 'anche qui.

E ancora, la lista. Ciò significa che w non può essere annullato, il core potrebbe essere più semplice se w fosse unbox.

fonte

2011-11-14 22:33:44

Ho aggiunto modelli di scoppio a tutti i parametri (!) Di tutte le funzioni (eccetto 'ws'), che ha reso funzionante l'unboxing. – fuz

Buona scoperta. Non hai bisogno di schemi di scoppio sui parametri _all_, però, con la frangia su 'a, b, c, d, e, a'' tutte le rose, kef sono in linea, tutto inboxbox unboxed. –

sì. In genere è una buona idea inserire schemi di botto su argomenti che dovrebbero essere rigorosi. – fuz

Ottimizzazione dei loop interni Haskell

risposta

Problemi correlati