从哈斯克尔的一元流中挤出更多性能

Question

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

问题是：对于一元流，最有效的方法是什么？

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

玩具问题

是一个最大长度 16 位LinearFeedbackShiftRegister (LFSR)，以 C 语言以有点过于复杂的方式实现，在IOmonad 中带有 Haskell 包装器。"过度阐述"是指不必要地使用struct及其malloc- 这种复杂化的目的是使其更类似于现实情况，其中您所拥有的只是一个围绕 FFI 的 Haskell 包装器到具有 OO ishnew、set、get、operate语义(即命令式样式)的 Cstruct。一个典型的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. 哈斯克尔列表

与 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流实现。除了提供fromVector和concatVectors，Data.Vector.Fusion.Stream.Monadic与Data.VectorVector关系不大。

查看分析报告显示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 的开销。但是我现在不确定在哪里寻找调整。也许这在一元流方面也一样好，事实上，这一切都是为了削减 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 函数的调用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 调用："如何强制 GHC 内联 FFI 调用？ .

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