Ответ 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