可变,(可能是并行)Haskell代码和性能调优

Question

我现在已经实现了另一个 SHA3​​候选者,即Grøstl.这仍然在进行中(非常如此),但目前224位版本通过了所有KAT.所以现在我想知道性能(再次: - >).这次的不同之处在于,我选择更接近地镜像(优化的)C实现,即我创建了一个从C到Haskell的端口.优化的C版本使用表查找来实现该算法.此外,代码主要基于更新包含64位字的数组.因此,我选择在Haskell中使用可变的无盒载体.

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

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

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

Q2)第二是表现.实际上它并不太糟糕,因为目前Haskell代码只慢了3倍.使用GHC-7.2.1并编译如下:

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

Haskell代码使用60秒.输入约为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,但几乎没有实际转换为有用的并行工作.因此,我在加速方面一无所获.我的问题变成了:

1. P和Q函数是否太小而运行时无法并行运行？
2. 如果没有,我使用par和pseq(可能还有Vector.Unboxed.force)是错误的吗？
3. 转换到策略会获得任何收益吗？那我该怎么做呢？

非常感谢您的参与.

编辑:

很抱歉没有提供任何真正的基准测试.回购中的测试代码仅供我自己使用.对于那些想要测试代码的人,你需要编译main.hs,然后运行它:

./main"algorithm""testvariant""字节对齐"

例如:

./main groestl short224错误

要么

./main groestl e False

(e代表"Extreme".这是NIST KATS提供的非常长的消息).

Answer 1

1. 请务必使用 进行编译-threaded -rtsopts并使用 执行+RTS -N2。如果没有这一点，您将不会有多个操作系统线程来执行计算。

2. 尝试激发其他地方引用的计算，否则它们可能会被收集：

_

f512 h m = outP `par` (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 = V.force $ permP inP
         outQ = V.force $ permQ m

_

3）如果您进行切换以parseBlock接受严格的字节串（或在需要时分块并打包惰性字节串），那么您可以使用Data.Vector.Storable并可能避免一些复制。