optimization - 优化 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 .你不能使用 rotate然后来自 Data.Bits，但必须自己实现它(不难)才能让它在 64 位系统上也能工作。对于 a'您将不得不手动屏蔽高位。

看起来不太理想的另一点是，在每次迭代中 t与 19、39 和 59(如果足够大)进行比较，因此循环体包含四个分支。如果拆分 iterateBlock' 可能会更快分成四个循环(0-19、20-39、40-59、60-79)并使用常量 k1、.​​..、k4 和四个函数 f1、...、f4(不带 t 参数)避免分支并为每个循环具有更小的代码大小。

而且，正如 Thomas 所说，对 block 数据使用列表并不是最佳选择，未装箱的 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，核心可能会更简单无法装箱。