Ваша версия 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,1 с против 0,079 с).
Теперь у вас есть функция высшего порядка в C, значительно медленнее, чем оригинал, но все же намного быстрее, чем Haskellкод.Одним из важных отличий является то, что функция C принимает в качестве аргументов незаписанную пару double s и незагруженный double, тогда как Haskell kahanStep принимает пару в штучной упаковке Double s и в штучной упаковке 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 и нативную поддержку GHC, использование llvm может дать немного другие результаты).
Я не думаю, что индексация действительно виновна.Векторный пакет сильно зависит от магии компилятора, но компиляция для поддержки профилирования в значительной степени мешает этому.Для таких пакетов, как vector или bytestring, в которых для оптимизации используется собственный фьюжн-каркас, помехи профилирования могут быть довольно катастрофическими, а результаты профилирования совершенно бесполезными.Я склонен полагать, что у нас есть такой случай здесь.
В ядре все операции чтения и записи преобразуются в простые числа 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 не был вашей основной проблемой (он может снова стать проблемой после исправления других проблем).
Если посмотреть на ядро, сгенерированное для вашей программы, то что перепрыгнулоПолучилось так, что ваша 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