在Haskell中压缩出更多来自monadic流的性能

Question

最直接的monadic'stream'只是一系列monadic动作Monad m => [m a].该sequence :: [m a] -> m [a]函数评估每个monadic动作并收集结果.事实证明,sequence并不是非常有效,因为它在列表上运行,并且monad是在除了最简单的情况之外的任何事情中实现融合的障碍.

问题是:对于monadic流来说,最有效的方法是什么？

为了解决这个问题,我提出了一个玩具问题以及一些提高性能的尝试.源代码可以在github上找到.下面提出的单一基准可能会误导更现实的问题,尽管我认为这是最糟糕的情况,即每次有用计算的最大开销.

玩具问题

是一个最大长度的16位大号 inear ˚F eedback 小号 HIFT ř egister(LFSR),在C以稍微过精心方式实施,在一个Haskell包装IO单子."过度复杂的"是指不必要使用的struct和它malloc-这种并发症的目的是使其更类似于所有你必须是围绕一个FFI Haskell的包装到一个C现实情况struct与OO十岁上下new,set,get,operate语义(即非常多的命令式).典型的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

这是implementation(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

(请注意,在这些较短的执行时间内,基准测试相当不准确.)

这是implementation(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

像往常一样,这里是implementation(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

我没想到会在下面找到一个好的monadic流实现Data.Vector.除了提供fromVector和concatVectors,Data.Vector.Fusion.Stream.Monadic已经很少做Vector的Data.Vector.

看一下分析报告显示Data.Vector.Fusion.Stream.Monadic有相当大的空间泄漏,但这听起来不对.

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上面的例子表明,大多数但不是全部(？)的性能损失来自调用包装器和/或FFI的开销.但我现在不确定在哪里寻找调整.也许这就像monadic溪流一样好,事实上这就是削减FFI,现在......

图片的标题说明

1. 选择LFSR作为玩具问题的事实并不意味着Haskell无法有效地执行这些操作 - 请参阅SO问题"LFSR实现中的高效比特".
2. 迭代16位LFSR 10M次是一件相当愚蠢的事情.这将需要最多 2 ^ 16-1迭代,以再次达到初始状态.在最大长度LFSR中,它将精确地进行 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和SRC/LFSR.hs.在性能方面,这没有区别(在时间差异内).

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

Answer 1

在破译 GHC 的汇编产品之后，RunRepeat.hs我得出这样的结论：GHC 不会内联对 C 函数的调用，而 C 编译器会内联，这使得这个玩具问题step_lfsr(state_t*)变得不同。

我可以通过禁止使用__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 调用：“如何强制 GHC 内联 FFI 调用？” 。

对于内联的好处如此之高的情况，即每个 FFI 调用的工作负载如此之低，可能值得研究一下inline-c。