performance - Data.Vector.Unboxed.Mutable.MVector 的索引真的这么慢吗？

Question

我有一个应用程序，它花费大约 80% 的时间使用 Kahan summation algorithm 计算高维向量(dim=100)的大列表(10^7)的质心。 .我已尽力优化求和，但它仍然比等效的 C 实现慢 20 倍。分析表明罪魁祸首是 unsafeRead和 unsafeWrite来自 Data.Vector.Unboxed.Mutable 的函数.我的问题是:这些功能真的这么慢还是我误解了分析统计数据？

下面是两个实现。 Haskell 是使用 llvm 后端用 ghc-7.0.3 编译的。 C 是用 llvm-gcc 编译的。

Haskell 中的 Kahan 求和:

{-# LANGUAGE BangPatterns #-}
module Test where

import Control.Monad ( mapM_ )
import Data.Vector.Unboxed ( Vector, Unbox )
import Data.Vector.Unboxed.Mutable ( MVector )
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.Word ( Word )
import Data.Bits ( shiftL, shiftR, xor )

prng :: Word -> Word
prng w = w' where
    !w1 = w  `xor` (w  `shiftL` 13)
    !w2 = w1 `xor` (w1 `shiftR` 7)
    !w' = w2 `xor` (w2 `shiftL` 17)

mkVect :: Word -> Vector Double
mkVect = U.force . U.map fromIntegral . U.fromList . take 100 . iterate prng

foldV :: (Unbox a, Unbox b) 
      => (a -> b -> a) -- componentwise function to fold
      -> Vector a      -- initial accumulator value
      -> [Vector b]    -- data vectors
      -> Vector a      -- final accumulator value
foldV fn accum vs = U.modify (\x -> mapM_ (liftV fn x) vs) accum where
    liftV f acc = fV where
        fV v = go 0 where
            n = min (U.length v) (UM.length acc)
            go i | i < n     = step >> go (i + 1)
                 | otherwise = return ()
                 where
                     step = {-# SCC "fV_step" #-} do
                         a <- {-# SCC "fV_read"  #-} UM.unsafeRead acc i
                         b <- {-# SCC "fV_index" #-} U.unsafeIndexM v i
                         {-# SCC "fV_write" #-} UM.unsafeWrite acc i $! {-# SCC "fV_apply" #-} f a b

kahan :: [Vector Double] -> Vector Double
kahan [] = U.singleton 0.0
kahan (v:vs) = fst . U.unzip $ foldV kahanStep acc vs where
    acc = U.map (\z -> (z, 0.0)) v

kahanStep :: (Double, Double) -> Double -> (Double, Double)
kahanStep (s, c) x = (s', c') where
    !y  = x - c
    !s' = s + y
    !c' = (s' - s) - y
{-# NOINLINE kahanStep #-}

zero :: U.Vector Double
zero = U.replicate 100 0.0

myLoop n = kahan $ map mkVect [1..n]

main = print $ myLoop 100000

使用 llvm 后端使用 ghc-7.0.3 进行编译:

ghc -o Test_hs --make -fforce-recomp -O3 -fllvm -optlo-O3 -msse2 -main-is Test.main Test.hs

time ./Test_hs
real    0m1.948s
user    0m1.936s
sys     0m0.008s

剖析信息:

16,710,594,992 bytes allocated in the heap
      33,047,064 bytes copied during GC
          35,464 bytes maximum residency (1 sample(s))
          23,888 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0: 31907 collections,     0 parallel,  0.28s,  0.27s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time   24.73s  ( 24.74s elapsed)
  GC    time    0.28s  (  0.27s elapsed)
  RP    time    0.00s  (  0.00s elapsed)
  PROF  time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time   25.01s  ( 25.02s elapsed)

  %GC time       1.1%  (1.1% elapsed)

  Alloc rate    675,607,179 bytes per MUT second

  Productivity  98.9% of total user, 98.9% of total elapsed

    Thu Feb 23 02:42 2012 Time and Allocation Profiling Report  (Final)

       Test_hs +RTS -s -p -RTS

    total time  =       24.60 secs   (1230 ticks @ 20 ms)
    total alloc = 8,608,188,392 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

fV_write                       Test                  31.1   26.0
fV_read                        Test                  27.2   23.2
mkVect                         Test                  12.3   27.2
fV_step                        Test                  11.7    0.0
foldV                          Test                   5.9    5.7
fV_index                       Test                   5.2    9.3
kahanStep                      Test                   3.3    6.5
prng                           Test                   2.2    1.8


                                                                                               individual    inherited
COST CENTRE              MODULE                                               no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN                                                   1           0   0.0    0.0   100.0  100.0
 CAF:main1               Test                                                 339           1   0.0    0.0     0.0    0.0
  main                   Test                                                 346           1   0.0    0.0     0.0    0.0
 CAF:main2               Test                                                 338           1   0.0    0.0   100.0  100.0
  main                   Test                                                 347           0   0.0    0.0   100.0  100.0
   myLoop                Test                                                 348           1   0.2    0.2   100.0  100.0
    mkVect               Test                                                 350      400000  12.3   27.2    14.5   29.0
     prng                Test                                                 351     9900000   2.2    1.8     2.2    1.8
    kahan                Test                                                 349         102   0.0    0.0    85.4   70.7
     foldV               Test                                                 359           1   5.9    5.7    85.4   70.7
      fV_step            Test                                                 360     9999900  11.7    0.0    79.5   65.1
       fV_write          Test                                                 367    19999800  31.1   26.0    35.4   32.5
        fV_apply         Test                                                 368     9999900   1.0    0.0     4.3    6.5
         kahanStep       Test                                                 369     9999900   3.3    6.5     3.3    6.5
       fV_index          Test                                                 366     9999900   5.2    9.3     5.2    9.3
       fV_read           Test                                                 361     9999900  27.2   23.2    27.2   23.2
 CAF:lvl19_r3ei          Test                                                 337           1   0.0    0.0     0.0    0.0
  kahan                  Test                                                 358           0   0.0    0.0     0.0    0.0
 CAF:poly_$dPrimMonad3_r3eg Test                                                 336           1   0.0    0.0     0.0    0.0
  kahan                  Test                                                 357           0   0.0    0.0     0.0    0.0
 CAF:$dMVector2_r3ee     Test                                                 335           1   0.0    0.0     0.0    0.0
 CAF:$dVector1_r3ec      Test                                                 334           1   0.0    0.0     0.0    0.0
 CAF:poly_$dMonad_r3ea   Test                                                 333           1   0.0    0.0     0.0    0.0
 CAF:$dMVector1_r3e2     Test                                                 330           1   0.0    0.0     0.0    0.0
 CAF:poly_$dPrimMonad2_r3e0 Test                                                 328           1   0.0    0.0     0.0    0.0
  foldV                  Test                                                 365           0   0.0    0.0     0.0    0.0
 CAF:lvl11_r3dM          Test                                                 322           1   0.0    0.0     0.0    0.0
  kahan                  Test                                                 354           0   0.0    0.0     0.0    0.0
 CAF:lvl10_r3dK          Test                                                 321           1   0.0    0.0     0.0    0.0
  kahan                  Test                                                 355           0   0.0    0.0     0.0    0.0
 CAF:$dMVector_r3dI      Test                                                 320           1   0.0    0.0     0.0    0.0
  kahan                  Test                                                 356           0   0.0    0.0     0.0    0.0
 CAF                     GHC.Float                                            297           1   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Handle.FD                                     256           2   0.0    0.0     0.0    0.0
 CAF                     GHC.IO.Encoding.Iconv                                214           2   0.0    0.0     0.0    0.0
 CAF                     GHC.Conc.Signal                                      211           1   0.0    0.0     0.0    0.0
 CAF                     Data.Vector.Generic                                  182           1   0.0    0.0     0.0    0.0
 CAF                     Data.Vector.Unboxed                                  174           2   0.0    0.0     0.0    0.0

C中的等效实现:

#include <stdint.h>
#include <stdio.h>


#define VDIM    100
#define VNUM    100000



uint64_t prng (uint64_t w) {
    w ^= w << 13;
    w ^= w >> 7;
    w ^= w << 17;
    return w;
};

void kahanStep (double *s, double *c, double x) {
    double y, t;
    y  = x - *c;
    t  = *s + y;
    *c = (t - *s) - y;
    *s = t;
}

void kahan(double s[], double c[]) {
    for (int i = 1; i <= VNUM; i++) {
        uint64_t w = i;
        for (int j = 0; j < VDIM; j++) {
                kahanStep(&s[j], &c[j], w);
                w = prng(w);
        }
    }
};


int main (int argc, char* argv[]) {
    double acc[VDIM], err[VDIM];
    for (int i = 0; i < VDIM; i++) {
        acc[i] = err[i] = 0.0;
    };
    kahan(acc, err);
    printf("[ ");
    for (int i = 0; i < VDIM; i++) {
        printf("%g ", acc[i]);
    };
    printf("]\n");
};

用 llvm-gcc 编译:

>llvm-gcc -o Test_c -O3 -msse2 -std=c99 test.c

>time ./Test_c
real    0m0.096s
user    0m0.088s
sys     0m0.004s

更新 1:我未内联 kahanStep在 C 版本中。它几乎没有影响表演。我希望现在我们都能承认阿姆达尔定律并继续前进。作为
效率低下 kahanStep可能是， unsafeRead和 unsafeWrite慢 9-10 倍。我希望有人能阐明这一事实的可能原因。

另外，我应该说，因为我正在与使用 Data.Vector.Unboxed 的库进行交互。 ，所以在这一点上我有点嫁给了它，离开它会非常痛苦:-)

更新 2:我想我在最初的问题中不够清楚。我不是在寻找加速这个微基准测试的方法。我正在寻找反直觉分析统计数据的解释，因此我可以决定是否针对 vector 提交错误报告.

Answer 1

您的 C 版本是 不是 相当于你的 Haskell 实现。在 C 中，您自己内联了重要的 Kahan 求和步骤，在 Haskell 中，您创建了一个多态高阶函数，该函数执行更多操作并将转换步骤作为参数。搬家 kahanStep到 C 中的单独函数不是重点，它仍然会被编译器内联。即使您将其放入自己的源文件中，单独编译并在没有链接时优化的情况下进行链接，您也只解决了部分差异。

我做了一个更接近 Haskell 版本的 C 版本，

卡汉.h:

typedef struct DPair_st {
    double fst, snd;
    } DPair;

DPair kahanStep(DPair pr, double x);

kahanStep.c:

#include "kahan.h"

DPair kahanStep (DPair pr, double x) {
    double y, t;
    y  = x - pr.snd;
    t  = pr.fst + y;
    pr.snd = (t - pr.fst) - y;
    pr.fst = t;
    return pr;
}

主文件:

#include <stdint.h>
#include <stdio.h>
#include "kahan.h"


#define VDIM    100
#define VNUM    100000

uint64_t prng (uint64_t w) {
    w ^= w << 13;
    w ^= w >> 7;
    w ^= w << 17;
    return w;
};

void kahan(double s[], double c[], DPair (*fun)(DPair,double)) {
    for (int i = 1; i <= VNUM; i++) {
        uint64_t w = i;
        for (int j = 0; j < VDIM; j++) {
            DPair pr;
            pr.fst = s[j];
            pr.snd = c[j];
            pr = fun(pr,w);
            s[j] = pr.fst;
            c[j] = pr.snd;
            w = prng(w);
        }
    }
};


int main (int argc, char* argv[]) {
    double acc[VDIM], err[VDIM];
    for (int i = 0; i < VDIM; i++) {
        acc[i] = err[i] = 0.0;
    };
    kahan(acc, err,kahanStep);
    printf("[ ");
    for (int i = 0; i < VDIM; i++) {
        printf("%g ", acc[i]);
    };
    printf("]\n");
};

单独编译并链接，运行速度比这里的第一个 C 版本慢 25%(0.1s 与 0.079s)。

现在您在 C 中有一个更高阶的函数，比原始函数慢得多，但仍然比 Haskell 代码快得多。一个重要的区别是 C 函数采用一对未装箱的 double s 和未装箱的 double作为参数，而 Haskell kahanStep带盒装一对盒装 Double s和盒装 Double并返回一对盒装 Double s，需要昂贵的装箱和拆箱 foldV环形。这可以通过更多的内联来解决。显式内联 foldV , kahanStep , 和 step使用 ghc-7.0.4 将时间从 0.90 秒缩短到 0.74 秒(它对 ghc-7.4.1 的输出影响较小，从 0.99 秒降至 0.90 秒)。

但是装箱和拆箱是差异的较小部分。 foldV比 C 做的更多 kahan ，它需要一个用于修改累加器的向量列表。该向量列表在 C 代码中完全不存在，这产生了很大的不同。所有这 100000 个向量都必须被分配、填充并放入一个列表中(由于懒惰，并不是所有的向量都同时存活，所以没有空间问题，但是它们以及列表单元必须被分配和垃圾收集，这需要相当长的时间)。并且在适当的循环中，而不是具有 Word#传入一个寄存器，从向量中读取预先计算的值。

如果你使用更直接的 C 到 Haskell 的翻译，

{-# LANGUAGE CPP, BangPatterns #-}
module Main (main) where

#define VDIM 100
#define VNUM 100000

import Data.Array.Base
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad.ST
import GHC.Word
import Control.Monad
import Data.Bits

prng :: Word -> Word
prng w = w'
  where
    !w1 = w `xor` (w `shiftL` 13)
    !w2 = w1 `xor` (w1 `shiftR` 7)
    !w' = w2 `xor` (w2 `shiftL` 17)

type Vec s = STUArray s Int Double

kahan :: Vec s -> Vec s -> ST s ()
kahan s c = do
    let inner w j
            | j < VDIM  = do
                !cj <- unsafeRead c j
                !sj <- unsafeRead s j
                let !y = fromIntegral w - cj
                    !t = sj + y
                    !w' = prng w
                unsafeWrite c j ((t-sj)-y)
                unsafeWrite s j t
                inner w' (j+1)
            | otherwise = return ()
    forM_ [1 .. VNUM] $ \i -> inner (fromIntegral i) 0

calc :: ST s (Vec s)
calc = do
    s <- newArray (0,VDIM-1) 0
    c <- newArray (0,VDIM-1) 0
    kahan s c
    return s

main :: IO ()
main = print . elems $ runSTUArray calc

它要快得多。不可否认，它仍然比 C 慢三倍左右，但原始在这里慢了 13 倍(而且我没有安装 llvm，所以我使用 vanilla gcc 和 native 支持的 ​​GHC，使用 llvm 可能会给出略有不同的结果)。

我不认为索引是真正的罪魁祸首。 vector 包严重依赖编译器魔法，但为分析支持进行编译会严重干扰这一点。对于像 vector 这样的包或 bytestring使用自己的融合框架进行优化，分析干扰可能是灾难性的，分析结果完全无用。我倾向于相信我们这里有这样的案例。

在 Core 中，所有读取和写入都转换为 primops readDoubleArray# , indexDoubleArray#和 writeDoubleArray# ，这是快速的。也许比 C 数组访问慢一点，但不是很多。所以我相信这不是问题，也不是造成巨大差异的原因。但是你已经把 {-# SCC #-}注释，因此禁用任何涉及重新排列任何这些术语的优化。每次输入这些点之一时，都必须记录下来。我对分析器和优化器不够熟悉，无法知道究竟发生了什么，但是，作为数据点，使用 {-# INLINE #-}关于 foldV 的编译指示, step和 kahanStep ，这些 SCC 的分析运行需要 3.17 秒，而 SCC fV_step , fV_read , fV_index , fV_write和 fV_apply删除(没有其他变化)一次分析运行只用了 2.03 秒(两次都由 +RTS -P 报告，因此减去了分析开销)。这种差异表明，廉价函数上的 SCC 和过于细粒度的 SCC 会严重扭曲分析结果。现在如果我们也放 {-# INLINE #-}关于 mkVect 的编译指示, kahan和 prng ，我们得到了一个完全没有信息的配置文件，但运行只需要 1.23 秒。 (然而，这些最后的内联对非分析运行没有影响，如果没有分析，它们会自动内联。)

因此，不要将分析结果视为不容置疑的事实。您的代码(直接或间接通过使用的库)依赖于优化的程度越高，它就越容易受到禁用优化导致的误导性分析结果的影响。这也适用于确定空间泄漏的堆分析，但程度要小得多。

当您有可疑的分析结果时，请检查删除某些 SCC 后会发生什么。如果这导致运行时间大幅下降，则该 SCC 不是您的主要问题(在修复其他问题后，它可能会再次成为问题)。

查看为您的程序生成的 Core，跳出来的是您的 kahanStep - 顺便说一下，删除 {-# NOINLINE #-} pragma from that，适得其反 - 生产一对盒装盒装 Double s 在循环中，即立即解构并拆箱组件。这种不必要的中间值装箱是昂贵的，并且会大大减慢计算速度。

当这出现在 haskell-cafe 上时今天再次有人使用 ghc-7.4.1， tibbe 从上述代码中获得了糟糕的性能。他亲自调查了 GHC 产生的核心，发现 GHC 产生了次优代码，用于从 Word 的转换。至 Double .更换 fromIntegral仅使用(包装的)原语进行自定义转换的转换(并删除在这里没有影响的爆炸模式，GHC 的严格性分析器足以看透算法，我应该学会更多地信任它；)，我们获得了与 gcc -O3 相同的版本原始 C 的输出:

{-# LANGUAGE CPP #-}
module Main (main) where

#define VDIM 100
#define VNUM 100000

import Data.Array.Base
import Data.Array.ST
import Data.Array.Unboxed
import Control.Monad.ST
import GHC.Word
import Control.Monad
import Data.Bits
import GHC.Float (int2Double)

prng :: Word -> Word
prng w = w'
  where
    w1 = w `xor` (w `shiftL` 13)
    w2 = w1 `xor` (w1 `shiftR` 7)
    w' = w2 `xor` (w2 `shiftL` 17)

type Vec s = STUArray s Int Double

kahan :: Vec s -> Vec s -> ST s ()
kahan s c = do
    let inner w j
            | j < VDIM  = do
                cj <- unsafeRead c j
                sj <- unsafeRead s j
                let y = word2Double w - cj
                    t = sj + y
                    w' = prng w
                unsafeWrite c j ((t-sj)-y)
                unsafeWrite s j t
                inner w' (j+1)
            | otherwise = return ()
    forM_ [1 .. VNUM] $ \i -> inner (fromIntegral i) 0

calc :: ST s (Vec s)
calc = do
    s <- newArray (0,VDIM-1) 0
    c <- newArray (0,VDIM-1) 0
    kahan s c
    return s

correction :: Double
correction = 2 * int2Double minBound

word2Double :: Word -> Double
word2Double w = case fromIntegral w of
                  i | i < 0 -> int2Double i - correction
                    | otherwise -> int2Double i

main :: IO ()
main = print . elems $ runSTUArray calc