LFSR 实现中的高效位调整

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

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

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

Basically it tests whether the LSFR defined in tap :: [[Int]] for any given bit-length is of maximum-length. (More precisely, it just checks whether the LSFR reaches the initial state (zero) after 2ⁿ iterations.)

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

到目前为止我尝试过的：

• use Data.Array：由于没有foldl/r而放弃尝试
• use 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 的输入）
• 随着重写@托马斯·M·杜布森，仍然使用默认的GHC后端，执行时间下降到5.2s
• With the rewrite of @Thomas M. DuBuisson, now using the LLVM backend (GHC option -O2 -fllvm), the execution time goes down to 1.7s
  • 使用 GHC 选项-O2 -fllvm -optlc -mcpu=native使其达到 0.73 秒
• 更换iterate with iterate'当使用 Thomas 的代码时（均使用默认的“本机”后端和 LLVM），@cirdec 的值没有任何区别。然而，它does使用基线代码时会有所不同。

所以，我们的速度从 100 倍到 8 倍再到 1.09 倍，即只比 C 慢 9%！

NoteGHC 8.0.2 的 LLVM 后端需要 LLVM 3.7。在 Mac OS X 上，这意味着安装此版本brew然后进行符号链接opt and llc. See 7.10。 GHC 后端.

预先事项

首先，我在 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

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

问题 1：狡猾的代码

我发现代码有几个奇怪的地方。首先是使用shift在高性能代码中。 Shift 支持左移和右移，为此需要一个分支。让我们用更具可读性的 2 的幂来杀死它（shift 1 x ~> 2^x and 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：位列表？整数运算拯救了一切！

一项变化，一个数量级。耶。还有什么？好吧，你有一个正在点击的令人尴尬的位位置列表，它看起来像是在乞求低效率和/或依赖于脆弱的优化。此时，我会注意到，对该列表中的任何一项选择进行硬编码都会带来非常好的性能（例如testBit lsfr 24 `xor` testBit lsfr 21）但我们想要一个更通用的快速解决方案。

我建议我们计算掩码all然后，点击位置执行单指令弹出计数。为此，我们只需要一个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 语言相匹配。最后，在部署的代码中，具有 C 绑定的 Haskell 包实际上很常见，但这通常是一个教育练习，所以我希望您玩得开心。

编辑：现在可用的 C++ 代码需要我的系统 0.10 (g++ -O3）和 0.12（clang++ -O3 -march=native) 秒，看来我们已经远远超过了我们的目标。