如何让我的Haskell程序更快？与C的比较

Question

我正在研究一个SHA3候选者JH的实现.我正处于算法通过NIST提供的所有KAT(已知答案测试)的地步,并且还使其成为Crypto-API的实例.因此,我开始研究它的表现.但我对Haskell很新,并且在分析时并不知道该寻找什么.

目前我的代码总是慢于用C语言编写的参考实现,所有输入长度都是10倍(C代码在这里找到:http://www3.ntu.edu.sg/home/wuhj/research/jh /jh_bitslice_ref64.h).

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

现在我不希望你浏览我的所有代码,而只是想要一些关于几个函数的技巧.我已经运行了一些性能测试,这是GHC生成的性能文件(的一部分):

Tue Oct 25 19:01 2011 Time and Allocation Profiling Report  (Final)

   main +RTS -sstderr -p -hc -RTS jh e False

total time  =        6.56 secs   (328 ticks @ 20 ms)
total alloc = 4,086,951,472 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

roundFunction                  Data.Digest.JHInternal  28.4   37.4
word128Shift                   Data.BigWord.Word128  14.9   19.7
blockMap                       Data.Digest.JHInternal  11.9   12.9
getBytes                       Data.Serialize.Get     6.7    2.4
unGet                          Data.Serialize.Get     5.5    1.3
sbox                           Data.Digest.JHInternal   4.0    7.4
getWord64be                    Data.Serialize.Get     3.7    1.6
e8                             Data.Digest.JHInternal   3.7    0.0
swap4                          Data.Digest.JHInternal   3.0    0.7
swap16                         Data.Digest.JHInternal   3.0    0.7
swap8                          Data.Digest.JHInternal   1.8    0.7
swap32                         Data.Digest.JHInternal   1.8    0.7
parseBlock                     Data.Digest.JHInternal   1.8    1.2
swap2                          Data.Digest.JHInternal   1.5    0.7
swap1                          Data.Digest.JHInternal   1.5    0.7
linearTransform                Data.Digest.JHInternal   1.5    8.6
shiftl_w64                     Data.Serialize.Get     1.2    1.1

Detailed breakdown omitted ...

现在快速了解JH算法:

它是一种散列算法,由压缩函数F8组成,只要存在输入块(长度为512位),它就会重复.这就是SHA功能的运作方式.F8功能由E8功能组成,该功能可应用42次圆形功能.round函数本身由三部分组成:sbox,线性转换和置换(在我的代码中称为swap).

因此,大多数时间花在圆函数上是合理的.我仍然想知道如何改进这些部件.例如:blockMap函数只是一个实用函数,将函数映射到4元组中的元素.那为什么表现如此糟糕？任何建议都是受欢迎的,而不仅仅是单一功能,即为了提高性能,您是否会进行结构性改变？

我已经尝试过查看Core输出,但不幸的是,这已经超出了我的想象.

我在最后附加了一些堆配置文件,以防可能感兴趣.

编辑:

我忘了提及我的设置和构建.我在x86_64 Arch Linux机器上运行它,GHC 7.0.3-2(我认为),带有编译选项:

ghc --make -O2 -funbox-strict-fields

不幸的是,当通过C或LLVM进行编译时,Linux平台上似乎存在一个错误,给我一个错误:

错误:XXXX的.size表达式未计算为常量

所以我无法看到它的影响.

Answer 1

• 切换到未装箱的矢量(来自数组,用于常量)
• 使用unsafeIndex而不是从安全索引(即!)中产生边界检查和数据依赖性
• Block1024像你一样打开包装Block512(或至少使用UnboxedTuples)
• 使用unsafeShift{R,L}这样你就不会检查换班值(进入GHC 7.4)
• 展开roundFunction你所以你有一个相当丑陋和冗长的e8功能.这在pureMD5中很有意义(滚动版本比展开版本更漂亮但速度更慢).您可以使用TH来执行此操作并使代码保持较小.如果你这样做,那么你就没有必要,constants因为这些值在代码中是显式的,并产生更多缓存友好的二进制文件.
• 打开你的Word128价值观.
• 定义您自己的添加Word128,不要提升Integer.请参阅LargeWord以获取如何完成此操作的示例.
• rem 不 mod
• 用optimization(-O2)编译并尝试llvm(-fllvm)

编辑:并将您的git repo与基准测试结合起来,以便我们可以帮助您更轻松;-).包括crypto-api实例的好工作.

Answer 2

下图显示列表占用了大量内存.除非潜伏在其他模块中,否则它们只会来自e8.也许你必须咬紧牙关并使它成为一个循环而不是折叠,但对于初学者来说,既然Block1024是一对,foldl'那么动态的评估就不多了(除非严格分析器变得明显更好).尝试制作更严格的,data Block1024 = B1024 !Block512 !Block512也许它也需要{-# UNPACK #-}pragma.在roundFunction,使用rem而不是mod(这只会产生轻微的影响,但它会更快)并使let绑定严格.在swapN函数中,您可以获得更好的性能,在表单中给出常量W x y而不是128位十六进制数.我不能保证这些改变会有所帮助,但这看起来很有希望在短暂的一瞥之后.