performance - 可变的(可能是并行的)Haskell 代码和性能调优

Question

我现在有 implemented another SHA3​​ 候选者，即 GrøSTL。这仍在进行中(非常如此)，但目前 224 位版本通过了所有 KAT。所以现在我想知道性能(再次:->)。这次的不同之处在于，我选择了更接近 (optimized) C implementation 的镜像。 ，即我做了一个从 C 到 Haskell 的端口。优化的 C 版本使用表查找来实现算法。此外，代码很大程度上基于更新包含 64 位字的数组。因此我选择在 Haskell 中使用可变的未装箱向量。

我的 GrøSTL 代码可以在这里找到:https://github.com/hakoja/SHA3/blob/master/Data/Digest/GroestlMutable.hs

算法的简短描述:这是一个 Merkle-Damgård 结构，只要还有 512 位的消息 block ，就会迭代压缩函数(在我的代码中为 f512M )。压缩函数非常简单:它只是运行两个不同的独立 512 位排列 电话 和 问 ( permP 和 permQ 在我的代码中)并结合它们的输出。它的这些排列是由查找表实现的。

Q1) 困扰我的第一件事是可变向量的使用使我的代码看起来非常丑陋。这是我第一次在 Haskell 中编写任何主要的可变代码，所以我真的不知道如何改进它。欢迎任何关于我如何更好地构建一元代码的提示。

Q2) 二是性能。其实还不错，因为目前 Haskell 代码只慢了 3 倍。使用 GHC-7.2.1 并编译如下:

ghc -O2 -Odph -fllvm -optlo-O3 -optlo-loop-reduce -optlo-loop-deletion

Haskell 代码使用 60s。在 ~1GB 的输入上，而 C 版本使用 21-22s。但有些地方我觉得很奇怪:

(1) 如果我尝试内联 rnd512QM ，代码需要 4 倍的时间，但如果我内联 rnd512PM 什么都没发生!为什么会这样？这两个功能几乎相同!

(2) 这可能更困难。我一直在尝试并行执行这两个排列。但目前无济于事。这是我尝试过的一个例子:

f512 h m = V.force outP `par` (V.force outQ `pseq` (V.zipWith3 xor3 h outP outQ))
   where xor3 x1 x2 x3 = x1 `xor` x2 `xor` x3
         inP = V.zipWith xor h m
         outP = permP inP
         outQ = permQ m

在检查运行时统计信息并使用 ThreadScope 时，我注意到创建了正确数量的 SPARKS，但实际上几乎没有一个转换为有用的并行工作。因此，我在加速方面一无所获。然后我的问题变成:

P 和 Q 函数是否太小以至于运行时无法并行运行？

如果没有，我使用的是 标准杆 和 pseq (可能还有 Vector.Unboxed.force)错了？

我会通过转换策略获得什么吗？我该怎么做呢？

非常感谢您的参与。

编辑:

很抱歉没有提供任何真正的基准测试。 repo 中的测试代码仅供我自己使用。对于那些想要测试代码的人，您需要编译 main.hs ，然后将其运行为:

./main "algorithm" "testvariant" "byte aligned"

例如:

./main groestl short224 False

或者

./main groestl e False

( e 代表“Extreme”。这是 NIST KATS 提供的非常长的信息)。

Answer 1

我查看了 repo，但没有简单的基准可以运行和使用，所以我的想法只是来自观察代码。编号与您的问题无关。

1) 我很确定force不会做你想做的事——它实际上强制复制底层向量。

2) 我认为 unsafeThaw 和 unsafeFreeze 的使用有点奇怪。我只是将 f512M 放在 ST monad 中并完成它。然后像这样运行它:

otherwise = \msg -> truncate G224 . outputTransformation . runST $ foldM f512M h0_224 (parseMessage dataBitLen 512 msg)

3) V.foldM'有点傻——你可以在一个列表上使用一个普通的(严格的) foldM ——在第二个参数中折叠向量似乎没有买任何东西。

4) 我对 columnM 中的刘海持怀疑态度对于 unsafeReads。

还...

a) 我怀疑异或未装箱向量的实现可能低于 zipWith ，利用 Data.Vector 内部。

b) 但是，最好不要这样做，因为它可能会干扰向量融合。

c) 经检查， extractByte看起来效率有点低？与其使用 fromIntegral 截断，不如使用 mod或 quot然后单个 fromIntegral 将您直接带到 Int。