优化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.除了可能内联临时变量之外,我认为没有办法进一步优化它,但我相信-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

Answer 1

看看ghc-7.2.2生成的核心,内联效果很好.不能很好地工作的是,在每次迭代Word32中,首先取消装箱几个值,执行工作,然后重新装箱以进行下一次迭代.拆箱和重新装箱可能花费大量的时间(和分配).您可以通过使用Word而不是使用来避免这种情况Word32.你无法使用rotateData.Bits,但是必须自己实现它(并不难)让它在64位系统上运行.因为a'你必须手动屏蔽高位.

另一个看起来不理想的点是,在每次迭代中将t其与19,39和59(如果它足够大)进行比较,以便循环体包含四个分支.如果你分成iterateBlock'四个循环(0-19,20-39,40-59,60-79)并使用常数k1,...,k4和四个函数f1,...,f4,它可能会更快(没有t参数)以避免分支并且每个循环具有更小的代码大小.

而且,正如Thomas所说,使用块数据列表并不是最佳的,未装箱的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.

然后比较t19,......,它们出现两次,一次确定k常数,一次用于f变换.仅比较便宜,但它们会导致分支而没有分支,可能会进一步内联.我希望在这里也能获得一点点.

而且,清单.这意味着w无法取消装箱,如果无法拆箱,核心可能更简单w.