在 Haskell 中从 monadic 流中榨取更多性能

Question

最直接的 monadic 'stream' 只是 monadic 动作的列表 Monad m => [m a]。 sequence :: [m a] -> m [a] 函数评估每个单子操作并收集结果。事实证明，sequence 不是很有效，因为它在列表上运行，而且 monad 是实现融合的障碍，除了最简单的情况。

问题是：monadic 流最有效的方法是什么？

为了对此进行调查，我提供了一个玩具问题以及一些提高性能的尝试。源代码可以在 github 上找到。下面给出的单一基准可能会误导更现实的问题，尽管我认为这是最坏的情况，即每次有用计算的最大开销。

玩具问题

是最大长度的 16 位 Linear Feedback Shift Register (LFSR)，在 C 中以一种有点过于复杂的方式实现，在 IO monad 中有一个 Haskell 包装器。 'Over-elaborate' 指的是 struct 及其 malloc 的不必要使用 - 这种复杂化的目的是使其更类似于您所拥有的只是 Haskell 的现实情况使用 OO-ish new、set、get、operate 语义（即非常命令式风格）将 FFI 包装到 C struct。典型的 Haskell 程序如下所示：

import LFSR

main = do
    lfsr <- newLFSR            -- make a LFSR object
    setLFSR lfsr 42            -- initialise it with 42 
    stepLFSR lfsr              -- do one update
    getLFSR lfsr >>= print     -- extract the new value and print

默认任务是计算 LFSR 10'000'000 次迭代的值（双精度值）的平均值。此任务可能是一组测试的一部分，用于分析此 16 位整数流的“随机性”。

0。基线

基线是 n 次迭代的平均值的 C 实现：

double avg(state_t* s, int n) {
    double sum = 0;
    for(int i=0; i<n; i++, sum += step_get_lfsr(s));
    return sum / (double)n;
}

C 实现并不意味着特别好或特别快。它只是提供了一个有意义的计算。

1. Haskell 列出

与 C 基线相比，在此任务上 Haskell 列表速度慢 73 倍。

=== RunAvg =========
Baseline: 1.874e-2
IO:       1.382488
factor:   73.77203842049093

这是实现（RunAvg.hs）：

step1 :: LFSR -> IO Word32
step1 lfsr = stepLFSR lfsr >> getLFSR lfsr

avg :: LFSR -> Int -> IO Double
avg lfsr n = mean <$> replicateM n (step1 lfsr) where
    mean :: [Word32] -> Double
    mean vs = (sum $ fromIntegral <$> vs) / (fromIntegral n)

2。使用 streaming 库

这使我们达到基线的 9 倍以内，

=== RunAvgStreaming ===
Baseline: 1.9391e-2
IO:       0.168126
factor:   8.670310969006241

（请注意，在这么短的执行时间内，基准测试相当不准确。）

这是实现（RunAvgStreaming.hs）：

import qualified Streaming.Prelude as S
avg :: LFSR -> Int -> IO Double
avg lfsr n = do
    let stream = S.replicateM n (fromIntegral <$> step1 lfsr :: IO Double)
    (mySum :> _) <- S.sum stream
    return (mySum / fromIntegral n)

3。使用 Data.Vector.Fusion.Stream.Monadic

这是迄今为止最好的性能，在基线的 3 倍以内，

=== RunVector =========
Baseline: 1.9986e-2
IO:       4.9146e-2
factor:   2.4590213149204443

像往常一样，这里是实现（RunAvgVector.hs）：

import qualified Data.Vector.Fusion.Stream.Monadic as V
avg :: LFSR -> Int -> IO Double
avg lfsr n = do
   let stream = V.replicateM n (step1' lfsr)
   V.foldl (+) 0.0 stream

没想到在Data.Vector下找到了很好的monadic stream实现。除了提供 fromVector 和 concatVectors 之外，Data.Vector.Fusion.Stream.Monadic 与 Data.Vector.

中的 Vector 几乎没有关系

分析报告显示 Data.Vector.Fusion.Stream.Monadic 有相当大的 space 泄漏，但这听起来不对。

4.列表不一定很慢

对于非常简单的操作，列表一点都不可怕：

=== RunRepeat =======
Baseline: 1.8078e-2
IO:       3.6253e-2
factor:   2.0053656377917912

这里，for循环是在Haskell中完成的，而不是下推到C(RunRepeat.hs):

do
   setLFSR lfsr 42
   replicateM_ nIter (stepLFSR lfsr)
   getLFSR lfsr

这只是对 stepLFSR 的重复调用，没有将结果传回 Haskell 层。它指示调用包装器和 FFI 的开销有什么影响。

分析

上面的 repeat 示例表明大部分（但不是全部（？））性能损失来自调用包装器 and/or FFI 的开销。但我不确定现在在哪里寻找调整。也许这与 monadic 流一样好，事实上这都是关于减少 FFI，现在...

旁注

LFSR 被选为玩具问题这一事实并不意味着 Haskell 无法有效地解决这些问题 - 请参阅 SO 问题 “Efficient bit-fiddling in a LFSR执行 ".
将 16 位 LFSR 迭代 10M 次是一件相当愚蠢的事情。最多需要 2^16-1 次迭代才能再次到达起始状态。在最大长度的 LFSR 中，它将需要 exactly 2^16-1 次迭代。

更新 1

尝试删除 withForeignPtr 调用可以通过引入 Storable 然后使用 alloca :: Storable a => (Ptr a -> IO b) -> IO b

repeatSteps :: Word32 -> Int -> IO Word32
repeatSteps start n = alloca rep where
    rep :: Ptr LFSRStruct' -> IO Word32
    rep p = do
        setLFSR2 p start
        (sequence_ . (replicate n)) (stepLFSR2 p)
        getLFSR2 p

其中 LFSRStruct' 是

data LFSRStruct' = LFSRStruct' CUInt

包装器是

foreign import ccall unsafe "lfsr.h set_lfsr"
    setLFSR2 :: Ptr LFSRStruct' -> Word32 -> IO ()

-- likewise for setLFSR2, stepLFSR2, ...

参见 RunRepeatAlloca.hs and src/LFSR.hs。在性能方面这没有区别（在时间差异内）。

=== RunRepeatAlloca =======
Baseline: 0.19811199999999998
IO:       0.33433
factor:   1.6875807623970283

Answer 1

在为 RunRepeat.hs 解读 GHC 的汇编产品后，我得出了这个结论：GHC 不会内联对 C 函数的调用 step_lfsr(state_t*)，而 C 编译器会，这使得这个玩具问题的所有差异。

我可以通过禁止内联 __attribute__ ((noinline)) 杂注来证明这一点。总的来说，C 可执行文件变慢了，因此 Haskell 和 C 之间的差距缩小了。

结果如下：

=== RunRepeat =======
#iter:    100000000
Baseline: 0.334414
IO:       0.325433
factor:   0.9731440669349967
=== RunRepeatAlloca =======
#iter:    100000000
Baseline: 0.330629
IO:       0.333735
factor:   1.0093942152684732
=== RunRepeatLoop =====
#iter:    100000000
Baseline: 0.33195399999999997
IO:       0.33791
factor:   1.0179422450098508

即FFI 调用 lfsr_step 不再受到惩罚。

=== RunAvg =========
#iter:    10000000
Baseline: 3.4072e-2
IO:       1.3602589999999999
factor:   39.92307466541442
=== RunAvgStreaming ===
#iter:    50000000
Baseline: 0.191264
IO:       0.666438
factor:   3.484388070938598

好的旧列表不会融合，因此性能受到巨大影响，而且 streaming 库也不是最佳的。但是 Data.Vector.Fusion.Stream.Monadic 得到 C 性能的 20% 以内：

=== RunVector =========
#iter:    200000000
Baseline: 0.705265
IO:       0.843916
factor:   1.196594188000255

已经观察到 GHC 不会内联 FFI 调用："How to force GHC to inline FFI calls?" .

对于内联的优势如此之大的情况，即每个 FFI 调用的工作量如此之低，可能值得研究 inline-c。

在 Haskell 中从 monadic 流中榨取更多性能

Squeezing more performance out of monadic streams in Haskell

monads

performance

haskell

stream

ffi