優化Haskell內循環

仍在Haskell的SHA1實現中工作。現在我有一個工作的實施，這是內部循環：優化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

探查告訴我，這個函數需要我的實現的運行時間的1/3。我可以想象沒有辦法進一步優化它，除了可能內聯臨時變量，但我相信-O2無論如何會爲我做到這一點。

任何人都可以看到可以進一步應用的重要優化？

僅供參考k和f調用低於。他們非常簡單，我認爲沒有辦法優化這些。除非Data.Bits模塊很慢？

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

來源

2011-11-14 Ana

沒有嘗試，我猜很多問題是保持您的塊數據列表（太多點/內存流量）。我會努力轉移到「Word32」的一個未裝箱的向量，並手動展開循環。除此之外，請用一個嚴格/不包裝的結構來保存'a'，'b'，'c'，'d'和'e';那麼你只有一個需要通過的變量（並且你一定會在上面放置一個爆炸模式，對吧？）。 –

我也會嘗試用表格查找替換所有'（<=）'，但我不確定它會有多大幫助。 –

另一件事：在C中編寫嚴格的算術函數並使用FFI調用它通常是一個好主意。如果您小心地引入無副作用，運行時可以使用快速調用C語言來提供良好的性能。 – fuz

查看由ghc-7.2.2生成的核心，內聯運行良好。什麼不能很好地工作是，在每次迭代中，一些Word32值首先被拆箱，執行工作，然後重新裝箱以用於下一次迭代。拆箱和重新裝箱會花費驚人的大量時間（和分配）。您可以通過使用Word而不是Word32來避免這種情況。您無法使用Data.Bits中的rotate，但必須自己實現（不難）才能使其在64位系統上也能正常工作。對於a'，您必須手動屏蔽掉高位。

看起來不理想的另一點是，在每次迭代中，t與19,39和59（如果足夠大）進行比較，以便循環體包含四個分支。如果將iterateBlock'分成四個循環（0-19,20-39,40-59,60-79）並使用常數k1，...，k4和四個函數f1，...，f4 （不包含t參數）以避免分支並且每個循環的代碼量都較小。

而且，正如托馬斯所說，使用塊數據的列表並不是最優的，未裝箱的Word數組/矢量也可能會有所幫助。

隨着爆炸模式，核心看起來好多了。剩下兩個或三個不太理想的點。

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

查看所有這些narrow32Word#？他們很便宜，但不是免費的。只需要最外面的部分，手動編碼步驟和使用Word可能有點收穫。

然後比較t與19，...，它們出現兩次，一次確定k常量，並且一次爲f變換。單單比較便宜，但它們會導致分支，如果沒有它們，則可能會進一步內聯。我希望在這裏也能獲得一點點。

而且還是，列表。這意味着w不能拆箱，如果w不可拆卸，則核心可能更簡單。

來源

2011-11-14 22:33:44

我將所有功能（除'ws'）的所有（！）參數的爆炸模式添加到了，使拆箱工作。 – fuz

好找。你不需要在_all_參數上使用爆炸模式，但是，在a，b，c，d，e，a'的爆炸聲中，一切都是玫瑰，k和f都是內聯的，所有內容都是unboxable unboxable。 –

是的。對於那些被認爲是嚴格的論點來說，放置模式通常是一個好主意。 – fuz

優化Haskell內循環

回答

相關問題