基准测试时出人意料的低时间 Data.Vector

Question

我正在对 Haskell 的数组库（array 和 vector 包）进行基准测试，以便为我的用例提出存储大数据的最佳方法。我正在使用 criterion 作为基准测试工具。

长话短说： 我的代码只是分配一个向量，然后用简单的结构（分别为 1M、10M 和 100M 元素）填充它。当我将 Haskell 基准测试时间与我用 C 编写的简单参考实现进行比较时，Haskell 快了几倍，我发现它很可疑：C 代码是一个简单的循环，用于填充数组中的结构.

问题： Haskell 的 vector 库是否有可能在性能方面击败 C？或者这是否意味着我的基准是 flawed/something 实际上不是 evaluated/there 的一些 'gotcha'？

另一个问题如何确保 Haskell 向量被实际计算？

更长的解释：手头的任务是用大量结构填充向量。他们有 Storable 个实例，使用的向量是 Data.Vector.Storable.

数据类型如下：

data Foo = Foo Int Int deriving (Show, Eq, Generic, NFData)

Storable 个实例如下所示：

chunkSize :: Int
chunkSize = sizeOf (undefined :: Int)
{-# INLINE chunkSize #-}

instance Storable Foo where
    sizeOf    _ = 2 * chunkSize ; {-# INLINE sizeOf    #-}
    alignment _ = chunkSize     ; {-# INLINE alignment #-}
    peek ptr = Foo
        <$> peekByteOff ptr 0
        <*> peekByteOff ptr chunkSize
    {-# INLINE peek #-}
    poke ptr (Foo a b) = do
        pokeByteOff ptr 0 a
        pokeByteOff ptr chunkSize b
    {-# INLINE poke #-}

序列化本身似乎工作正常。然后分配向量：

mkFooVec :: Int -> IO (Vector Foo)
mkFooVec !i = unsafeFreeze =<< new (i + 1)

并填充结构：

populateFooVec :: Int -> Vector Foo -> IO (Vector Foo)
populateFooVec !i !v = do
    v' <- unsafeThaw v
    let go 0 = return ()
        go j = unsafeWrite v' j (Foo j $ j + 1) >> go (j - 1)
    go i
    unsafeFreeze v'

Benchmark是标准准则之一：

    defaultMain [
      bgroup "Storable vector (mutable)"
        $ (\(i :: Int) -> env (mkFooVec (10 ^ i))
        $ \v -> bench ("10e" <> show i)
        $ nfIO (populateFooVec (10 ^ i) v))  <$> [6..8]
    ]

gist 包含其他基准，试图以不同的方式强制评估。

可以找到大致相同的参考 C 代码 here (gist)。主要逻辑如下：

Foo *allocFoos(long n) {
    return (Foo *) malloc(n * sizeof(Foo));
}

// populate the array with structs:
void createFoos(Foo *v, long n) {
    for (long i = 0; i < n; ++i) {
        v[i].name = i;
        v[i].id = i + 1;
    }
}

以及用于运行它的命令：gcc -O2 -o bench benchmark.c && ./bench

现在，当我运行基准测试时，C 代码大约需要 50 毫秒，而 Criterion 报告结果大约需要 800 皮秒 (!)。这让我想知道：也许我对结果的解释有误？也许矢量实际上并未被评估（尽管如果您查看 Haskell 要点，我会尝试以不同的方式强制评估）。我究竟做错了什么？如果没有 - vector 如何击败 C 中的简单 for 循环（GCC 进一步展开，顺便说一句）？

请原谅我的问题太长了，我试图给出整个上下文 ;)

Answer 1

虽然我不信任基准测试代码，但我也无法重现该问题。我修改了 Haskell 要点（只是删除了第二个两个基准）和 C 基准（让它执行操作 1000 次然后将时间除以 1000）。

编辑：我不信任代码，因为：

您正在使用不安全*调用，这些调用具有您违反的隐式约定。
该代码甚至无法编译 - 您有错字和缺少语言扩展。这通常是其他恶作剧的迹象。

我的结果

结果如何？没错，这里没有异常。

% gcc bench.c -O3 && ./a.out
Starting the benchmark
[[ Malloced-array-[10000000] ]]Time taken: 11.904249 ms (cpu) 11.904249 ms (wall)
Done
./a.out  11.78s user 0.14s system 98% cpu 12.131 total

即11ms 对于 C 在 10^7 个元素。

和

% ghc -O2 bench.hs && ./bench
benchmarking Storable vector (FAKE mutable)/10e6
time                 2.362 ms   (2.236 ms .. 2.561 ms)
                     0.953 R²   (0.909 R² .. 0.989 R²)
mean                 2.344 ms   (2.268 ms .. 2.482 ms)
std dev              305.0 μs   (169.1 μs .. 477.1 μs)
variance introduced by outliers: 79% (severely inflated)

benchmarking Storable vector (FAKE mutable)/10e7
time                 23.37 ms   (22.13 ms .. 24.73 ms)
                     0.989 R²   (0.979 R² .. 0.996 R²)
mean                 23.19 ms   (22.63 ms .. 23.76 ms)
std dev              1.287 ms   (1.015 ms .. 1.713 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking Storable vector (FAKE mutable)/10e8
time                 232.2 ms   (215.1 ms .. 247.3 ms)
                     0.994 R²   (0.974 R² .. 1.000 R²)
mean                 223.5 ms   (215.9 ms .. 231.5 ms)
std dev              10.41 ms   (7.887 ms .. 13.06 ms)
variance introduced by outliers: 14% (moderately inflated)

即23ms 对于 Haskell 在 10^7 结果。

这是在带有 GHC 8.2 的较新的 macbook 上。

基准测试时出人意料的低时间 Data.Vector

Surprisingly low times when benchmarking Data.Vector

c

arrays

benchmarking

haskell

vector