Является ли индексирование Data.Vector.Unboxed.Mutable.MVector действительно медленным?

У меня есть приложение, которое тратит около 80% своего времени на вычисление центроида большого списка (10 ^ 7) высокоразмерных векторов (dim = 100) с помощью алгоритм суммирования Kahan. Я сделал все возможное для оптимизации суммирования, но он по-прежнему в 20 раз медленнее, чем эквивалентная реализация C. Профилирование указывает, что виновниками являются функции unsafeRead и unsafeWrite от Data.Vector.Unboxed.Mutable. Мой вопрос: эти функции действительно медленны или я неправильно понимаю статистику профилирования?

Вот две реализации. Haskell скомпилирован с помощью ghc-7.0.3 с использованием бэкэнда llvm. Компонента C с помощью llvm-gcc.

Суммирование Кахана в Хаскелле:

{-# 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

Компиляция с помощью ghc-7.0.3 с использованием бэкэнда llvm:

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

memory residency by cost centermemory residency by type for <code>foldV</code>memory residency by type for <code>unsafeRead</code>memory residency by type for <code>unsafeWrite</code>

Эквивалентная реализация в 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-10x медленнее. Я надеялся, что кто-то сможет пролить свет на возможные причины этого факта.

Кроме того, я должен сказать, что, так как я взаимодействую с библиотекой, которая использует Data.Vector.Unboxed, поэтому я на этот раз влюблена в нее, и расставание с ней было бы очень травматичным: -)

Обновление 2: Я думаю, что в моем первоначальном вопросе я не был достаточно ясен. Я не ищу способы ускорить этот микрообъект. Я ищу объяснение счетной интуитивной статистики профилирования, поэтому я могу решить, следует ли сообщать отчет об ошибке с vector.

Ответы

Ответ 1

Ваша версия C не эквивалентна вашей реализации Haskell. В C вы ввели важный шаг суммирования Кахана самостоятельно, в Haskell вы создали полиморфную функцию более высокого порядка, которая делает намного больше и принимает шаг преобразования в качестве параметра. Перемещение kahanStep в отдельную функцию в C не является точкой, она все равно будет встроена в компилятор. Даже если вы помещаете его в свой собственный исходный файл, компилируйте отдельно и связывайте без оптимизации времени соединения, вы обращаетесь только к части разницы.

Я сделал версию C, которая ближе к версии Haskell,

kahan.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;
}

main.c:

#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");
};

Скомпилирован отдельно и связан, что работает примерно на 25% медленнее, чем первая версия C здесь (0.1s против 0.079s).

Теперь у вас функция более высокого порядка на C, значительно медленнее оригинала, но все же намного быстрее, чем код Haskell. Важным отличием является то, что функция C принимает распакованную пару double и unboxed double в качестве аргументов, в то время как Haskell kahanStep берет коробку в коробке double и коробку double и возвращает коробку пара в штучной упаковке double s, требующая дорогостоящего бокса и распаковки в цикле foldV. Это можно устранить путем большей инкрустации. Явно встраивание foldV, kahanStep и step сокращает время от 0,90 до 0,74 с здесь с помощью ghc-7.0.4 (оно оказывает меньшее влияние на выход ghc-7.4.1, начиная с 0.99 с до 0.90s).

Но бокс и распаковка - это, увы, меньшая часть разницы. 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 или bytestring, которые используют свою собственную инфраструктуру фьюжн для оптимизации, профилирующие помехи могут быть довольно катастрофическими, а результаты профилирования совершенно бесполезны. Я склонен полагать, что у нас есть такой случай.

В ядре все чтения и записи преобразуются в примитивы readDoubleArray#, indexDoubleArray# и writeDoubleArray#, которые бывают быстрыми. Может быть, немного медленнее, чем доступ к массиву C, но не очень. Поэтому я уверен, что это не проблема и причина большой разницы. Но вы добавили к ним аннотации {-# SCC #-}, поэтому отключите любую оптимизацию, включающую перегруппировку любого из этих терминов. И каждый раз, когда вводится одна из этих точек, она должна быть записана. Я недостаточно знаком с профилировщиком и оптимизатором, чтобы узнать, что именно происходит, но, как точка данных, с {-# INLINE #-} прагмами на foldV, step и kahanStep, профилирование с этими SCC 3.17s, а с SCC fV_step, fV_read, fV_index, fV_write и fV_apply удалены (ничего больше не изменилось) профайлинг-прогон занял всего 2.03s (оба раза, как сообщалось +RTS -P, поэтому с вычитанием служебных данных профилирования). Эта разница показывает, что SCC по дешевым функциям и слишком мелкозернистые SCC могут значительно искажать результаты профилирования. Теперь, если мы также поместим {-# INLINE #-} прагмы на mkVect, kahan и prng, мы остаемся с полностью неинформативным профилем, но пробег занимает всего 1.23s. (Тем не менее, эти последние наложения не влияют на выполнение без профилирования, без профилирования, они автоматически устанавливаются.)

Итак, не принимайте результаты профилирования как неоспоримые истины. Чем больше ваш код (прямо или косвенно через используемые библиотеки) зависит от оптимизации, тем больше он уязвим для вводящих в заблуждение профилирующих результатов, вызванных отключенными оптимизациями. Это также имеет место, но в гораздо меньшей степени, для кучного профилирования для устранения утечек пространства.

Когда у вас есть подозрительный результат профилирования, проверьте, что происходит, когда вы удаляете некоторые SCC. Если это приводит к большому падению времени выполнения, этот SCC не был вашей основной проблемой (это может снова стать проблемой после устранения других проблем).

Глядя на ядро, сгенерированное для вашей программы, выскочил из-за того, что ваш kahanStep - кстати, удалите прагму {-# NOINLINE #-} из этого, она контрпродуктивная - создала коробку с короткими коробками double в цикл, который был немедленно деконструирован, и компоненты были распакованы. Такой ненужный промежуточный бокс ценностей дорог и замедляет вычисления на много.


Как это появилось сегодня на 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

Ответ 2

В этом компиляторе Data.Vector есть смешное смешение комбинаторов списков. Если я сделаю первую очевидную поправку, заменив

mkVect = U.force . U.map fromIntegral . U.fromList . take 100 . iterate prng 

с правильным использованием Data.Vector.Unboxed:

mkVect = U.force . U.map fromIntegral . U.iterateN 100 prng

тогда мое время падает на две трети - от real 0m1.306s до real 0m0.429s Похоже, что все функции верхнего уровня имеют эту проблему, кроме prng и zero

Ответ 3

Это появилось в списках рассылки, и я обнаружил, что есть ошибка в коде Word- > Double conversion в GHC 7.4.1 (по крайней мере). Эта версия, которая работает с ошибкой, работает так же быстро, как и код C на моей машине:

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

#define VDIM 100
#define VNUM 100000

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

import GHC.Exts

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 ()

        outer i | i <= VNUM = inner (fromIntegral i) 0 >> outer (i + 1)
                | otherwise = return ()
    outer (1 :: Int)

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

{- I originally used this function, which isn't quite correct.
   We need a real bug fix in GHC.
word2Double :: Word -> Double
word2Double (W# w) = D# (int2Double# (word2Int# w))
-}

correction :: Double
correction = 2 * int2Double minBound

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

Помимо работы с ошибкой Word- > Double, я также удалил дополнительные списки, чтобы лучше соответствовать версии C.

Ответ 4

Я знаю, что вы не просили улучшить этот микро-бенчмарк, но я дам вам объяснение, которое может оказаться полезным при написании циклов в будущем:

Неизвестный вызов функции, например, сделанный аргументом более высокого порядка foldV, может быть дорогостоящим, когда это делается в цикле. В частности, это будет препятствовать распаковке аргументов функции, что приведет к увеличению распределения. Причина, по которой он запрещает декомпозицию аргументов, заключается в том, что мы не знаем, что функция, которую мы вызываем, является строгой в этих аргументах, и поэтому мы передаем аргументы, например. (Double, Double), а не как Double# -> Double#.

Компилятор может определить информацию о строкости, если цикл (например, foldV) соответствует телу цикла (например, kahanStep). По этой причине я рекомендую людям INLINE функции более высокого порядка. В этом случае inline foldV и удаление NOINLINE на kahanStep улучшает время выполнения для меня немного.

В этом случае это не приводит к производительности наравне с C, так как есть другие вещи (как прокомментировали другие), но это шаг в правильном направлении (и это шаг, который вы можете сделать без каждый из которых должен смотреть на профилирующий вывод).