Haskell内部ループの最適化

Question

まだHaskellでのSHA1の実装に取り​​組んでいます。私は今働いて実装を持っているし、これは内部ループです：

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を取ることを私に伝えます。私は一時変数をインライン展開する以外の方法をそれ以上最適化する方法はないと思うが、私はとにかくそれを行うだろうと私は信じている。

今後さらに適用できる重要な最適化を誰も見ることができますか？

FYIの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 

Answer 1

ghc-7.2.2で生成されたコアを見ると、インライン展開がうまく機能します。あまりうまくいかないのは、それぞれの反復で2つのWord32の値が最初にアンボックスされ、作業を実行してから、次の反復のために再ボックス化されるということです。アンボクシングと再ボクシングは、驚くほど長い時間（そして割り当て）を要します。 おそらくWord32の代わりにWordを使用することで回避できます。その後、Data.Bitsのrotateを使用することはできませんでしたが、64ビットシステムでも動作させるには、それを自分で実装する必要があります。 a'の場合は、手動で上位ビットをマスクする必要があります。

次善策と思われるもう1つの点は、ループ本体に4つのブランチが含まれるように、各反復では012,3064,が19,39、および59と比較されることです（十分な大きさの場合）。 iterateBlock'を4つのループ（0-19,20-39,40-59,60-79）に分割し、定数k1、...、k4と4つの関数f1、...、f4を使用すると、おそらく速くなります（tパラメータなし）、分岐を避け、各ループのコードサイズが小さくなります。

トーマス氏によると、ブロックデータのリストを使用するのは最適ではないため、ボックス化されていないワード配列/ベクトルがおそらく役に立ちます。

バンパターンでは、コアがはるかによく見えます。理想的でないポイントが2つまたは3つ残っています。

     (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定数を決定するために1回、f変換のために1回、2回表示されます。比較だけでも安価ですが、分岐が発生し、それがなければさらなるインライン化が可能です。私は少しもここでも得られると思う。

それでも、リスト。これは、wがアンボックス化できないことを意味します。wがアンボックス可能だった場合、コアは簡単になります。