Optymalizacja pętli wewnętrznych Haskell

Question

Nadal pracuję nad moją implementacją SHA1 w Haskell. Ja teraz mam wdrożenie pracę i to jest wewnętrzna pętla:

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 

Profiler mi mówi, że funkcja ta zajmuje 1/3 wykonywania mojej realizacji. Nie mogę wymyślić sposobu, aby zoptymalizować go w inny sposób niż może wstawić zmienne tymczasowe, ale wierzę, że -O2 zrobi to za mnie.

Czy ktokolwiek widzi znaczącą optymalizację, którą można zastosować?

FYI Połączenia k i f znajdują się poniżej. Są tak proste, że nie sądzę, że istnieje sposób na zoptymalizowanie tych innych. O ile moduł Data.Bits nie działa wolno?

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 

Answer 1

Patrząc na rdzeń wyprodukowany przez ghc-7.2.2, inline działa dobrze. Nie działa tak dobrze, że w każdej iteracji kilka wartości Word32 jest najpierw rozpakowywanych, aby wykonać pracę, a następnie ponownie zapakowane do następnej iteracji. Unboxing i re-boxing mogą kosztować zaskakująco dużo czasu (i alokacji). Prawdopodobnie można tego uniknąć, używając Word zamiast Word32. Nie można było wtedy użyć rotate z Data.Bits, ale musiałoby ono zostać zaimplementowane samodzielnie (nie jest trudne), aby mogło działać również w systemach 64-bitowych. Dla a' trzeba ręcznie maskować wysokie bity.

Kolejny punkt, który wygląda na suboptymalny, to że w każdej iteracji t jest porównywany z 19, 39 i 59 (jeśli jest wystarczająco duży), tak że korpus pętli zawiera cztery gałęzie. Prawdopodobnie będzie to szybsze, jeśli podzielisz iterateBlock' na cztery pętle (0-19, 20-39, 40-59, 60-79) i użyjesz stałych k1, ..., k4 i czterech funkcji f1, ..., f4 (bez parametru t), aby uniknąć gałęzi i mieć mniejszy rozmiar kodu dla każdej pętli.

I, jak powiedział Thomas, użycie listy dla danych blokowych nie jest optymalne, prawdopodobnie rozpakowałaby się również unboxed Word array/vector.

Z wzorami huku rdzeń wygląda znacznie lepiej. Pozostają dwa lub trzy punkty mniej niż idealne.

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

Zobacz wszystkie te narrow32Word#? Są tanie, ale nie za darmo. Potrzebny jest tylko najbardziej zewnętrzny, może być trochę do zebrania przez ręczne kodowanie kroków i używanie Word.

Następnie porównania t z 19, ..., pojawiają się dwa razy, jeden raz, aby określić stałą k, i raz dla przekształcenia f. Same porównania są tanie, ale powodują rozgałęzienia, a bez nich dalsze umiejscowienie może być możliwe. Spodziewam się, że można tu również trochę zyskać.

I wciąż, lista. Oznacza to, że w nie można rozpakować, rdzeń może być prostszy, jeśli w byłby nieskasowany.