优化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内循环

回答

相关问题