haskell - LFSR 实现中的高效位摆弄

Question

虽然我有一个很好的 LSFR C 实现，但我想我会在 Haskell 中尝试同样的方法——只是为了看看它是如何进行的。到目前为止，我想出的比 C 实现慢两个数量级，这就引出了一个问题:如何提高性能？ 显然，位摆弄操作是瓶颈，分析器证实了这一点。

这是使用列表和 Data.Bits 的基线 Haskell 代码:

import           Control.Monad      (when)
import           Data.Bits          (Bits, shift, testBit, xor, (.&.), (.|.))
import           System.Environment (getArgs)
import           System.Exit        (exitFailure, exitSuccess)

tap :: [[Int]]
tap = [
    [],            [],            [],            [3, 2],
    [4, 3],        [5, 3],        [6, 5],        [7, 6],
    [8, 6, 5, 4],  [9, 5],        [10, 7],       [11, 9],
    [12, 6, 4, 1], [13, 4, 3, 1], [14, 5, 3, 1], [15, 14],
    [16,15,13,4],  [17, 14],      [18, 11],      [19, 6, 2, 1],
    [20, 17],      [21, 19],      [22, 21],      [23, 18],
    [24,23,22,17], [25, 22],      [26, 6, 2, 1], [27, 5, 2, 1],
    [28, 25],      [29, 27],      [30, 6, 4, 1], [31, 28],
    [32,22,2,1],   [33,20],       [34,27,2,1],   [35,33],
    [36,25],       [37,5,4,3,2,1],[38,6,5,1],    [39,35],
    [40,38,21,19], [41,38],       [42,41,20,19], [43,42,38,37],
    [44,43,18,17], [45,44,42,41], [46,45,26,25], [47,42],
    [48,47,21,20], [49,40],       [50,49,24,23], [51,50,36,35],
    [52,49],       [53,52,38,37], [54,53,18,17], [55,31],
    [56,55,35,34], [57,50],       [58,39],       [59,58,38,37],
    [60,59],       [61,60,46,45], [62,61,6,5],   [63,62]        ]

xor' :: [Bool] -> Bool
xor' = foldr xor False

mask ::  (Num a, Bits a) => Int -> a
mask len = shift 1 len - 1

advance :: Int -> [Int] -> Int -> Int
advance len tap lfsr
    | d0        = shifted
    | otherwise = shifted .|. 1
    where
        shifted = shift lfsr 1 .&. mask len
        d0 = xor' $ map (testBit lfsr) tap'
        tap' = map (subtract 1) tap

main :: IO ()
main = do
    args <- getArgs
    when (null args) $ fail "Usage: lsfr <number-of-bits>"
    let len = read $ head args
    when (len < 8) $ fail "No need for LFSR"
    let out = last $ take (shift 1 len) $ iterate (advance len (tap!!len)) 0
    if out == 0 then do
        putStr "OK\n"
        exitSuccess
    else do
        putStr "FAIL\n"
        exitFailure

基本上它测试是否 LSFR定义于 tap :: [[Int]]对于任何给定的位长度都是最大长度。 (更准确地说，它只是检查 LSFR 在 2n 次迭代后是否达到初始状态(零)。)

根据分析器，最昂贵的线路是反馈位 d0 = xor' $ map (testBit lfsr) tap' .

到目前为止我已经尝试过:

使用 Data.Array : 尝试放弃，因为没有 foldl/r

使用 Data.Vector : 比基线略快

我使用的编译器选项是: -O2 , LTS Haskell 8.12 (GHC-8.0.2) .

引用 C++ 程序可以在 gist.github.com 上找到。 .

不能指望 Haskell 代码(？)运行得和 C 代码一样快，但是两个数量级太多了，必须有更好的方法来做位摆弄。

更新:应用答案中建议的优化的结果

输入 28 的引用 C++ 程序，使用 LLVM 8.0.0 编译，在我的机器上运行 0.67 秒(与 clang 3.7 相同，稍慢，0.68 秒)

基线 Haskell 代码运行速度慢了大约 100 倍(由于空间效率低下，请勿尝试输入大于 25 的输入)

随着 @Thomas M. DuBuisson 的重写，仍然使用默认的 GHC 后端，执行时间下降到 5.2s

随着 @Thomas M. DuBuisson 的重写，现在使用 LLVM 后端(GHC 选项 -O2 -fllvm )，执行时间下降到 1.7s

使用 GHC 选项 -O2 -fllvm -optlc -mcpu=native将此时间缩短至 0.73 秒

更换iterate与 iterate'当使用 Thomas 的代码(使用默认的“ native ”后端和 LLVM)时，@cirdec 的代码没有任何区别。但是，使用基线代码时确实会有所不同。

所以，我们已经从 100 倍到 8 倍到 1.09 倍，即只比 C 慢 9%!

备注
GHC 8.0.2 的 LLVM 后端需要 LLVM 3.7。在 Mac OS X 上，这意味着使用 brew 安装此版本然后符号链接(symbolic link) opt和 llc .见 7.10. GHC Backends .

Answer 1

前期事项

对于初学者，我在 Intel I5 ~2.5GHz、linux x86-64 上使用 GHC 8.0.1。

初稿:哦不!减速!

带有参数 25 的起始代码运行:

% ghc -O2 orig.hs && time ./orig 25
[1 of 1] Compiling Main             ( orig.hs, orig.o )
Linking orig ...
OK
./orig 25  7.25s user 0.50s system 99% cpu 7.748 total

所以击败的时间是 77 毫秒 - 比这个 Haskell 代码好两个数量级。让我们潜入。

问题1:狡猾的代码

我在代码中发现了一些奇怪的地方。首先是使用 shift在高性能代码中。 Shift 支持左移和右移，为此它需要一个分支。让我们用 2 等更具可读性的幂来杀死它( shift 1 x ~> 2^x 和 shift x 1 ~> 2*x ):

% ghc -O2 noShift.hs && time ./noShift 25
[1 of 1] Compiling Main             ( noShift.hs, noShift.o )
Linking noShift ...
OK
./noShift 25  0.64s user 0.00s system 99% cpu 0.637 total

(正如您在评论中指出的那样:是的，这值得调查。可能是先前代码的一些奇怪阻止了重写规则的触发，结果导致代码更糟糕)

问题 2:位列表？ int 操作节省了一天!

一个变化，一个数量级。耶。还有什么？好吧，你有这个尴尬的比特位置列表，你正在挖掘它，这似乎是在乞求效率低下和/或依赖于脆弱的优化。在这一点上，我会注意到对该列表中的任何一个选择进行硬编码会产生非常好的性能(例如 testBit lsfr 24 `xor` testBit lsfr 21 )，但我们需要更通用的快速解决方案。

我建议我们计算所有点击位置的掩码，然后进行单指令弹出计数。为此，我们只需要一个 Int传递给 advance而不是整个列表。 popcount 指令需要良好的汇编生成，这需要 llvm 和可能 -optlc-mcpu=native或另一个非悲观的指令集选择。

这一步给了我们 pc以下。我已经放弃了 advance 的防护移除评论中提到:

let tp = sum $ map ((2^) . subtract 1) (tap !! len)
    pc lfsr = fromEnum (even (popCount (lfsr .&. tp)))
    mask = 2^len - 1
    advance' :: Int -> Int
    advance' lfsr = (2*lfsr .&. mask) .|. pc lfsr 
    out :: Int
    out = last $ take (2^len) $ iterate advance' 0

我们的结果是:

% ghc -O2 so.hs -fforce-recomp -fllvm -optlc-mcpu=native && time ./so 25      
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
OK
./so 25  0.06s user 0.00s system 96% cpu 0.067 total

从开始到结束，这超过了两个数量级，所以希望它与您的 C 相匹配。最后，在部署的代码中，实际上很常见 Haskell 包与 C 绑定(bind)，但这通常是一个教育练习，所以我希望你玩得开心。

编辑:现在可用的 C++ 代码需要我的系统 0.10 ( g++ -O3 ) 和 0.12 ( clang++ -O3 -march=native ) 秒，所以看起来我们已经超越了我们的标记。