Haskell mathematische Leistung auf Multiply-Add-Operation
https://stackoverflow.com/questions/3115540
-
29-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich schreibe ein Spiel in Haskell, und mein aktuellen Pass an der Benutzeroberfläche beinhaltet eine Menge von Verfahren Generation der Geometrie. Ich konzentrierte sich derzeit auf die Leistung einer bestimmten Operation identifiziert (C-ish Pseudo-Code):
Vec4f multiplier, addend;
Vec4f vecList[];
for (int i = 0; i < count; i++)
vecList[i] = vecList[i] * multiplier + addend;
Das heißt, ein Moor-Standard-Multiply-Add von vier Schwimmern, die Art der Sache reif für die SIMD-Optimierung.
Das Ergebnis wird auf einen OpenGL Vertex-Puffer, so dass er schließlich in einen flachen C-Array abgeladen hat zu bekommen. Aus dem gleichen Grund sollten die Berechnungen wahrscheinlich auf C ‚float‘ Typen durchgeführt werden.
Ich habe entweder für eine Bibliothek oder eine native idiomatische Lösung sah so etwas zu tun, schnell in Haskell, aber jede Lösung, die ich mit scheint rund 2% der Leistung zu schweben kommen haben (das heißt, 50x langsamer ) im Vergleich zu C von GCC mit den richtigen Fahnen. Zugegeben, ich begann vor ein paar Wochen mit Haskell, so meine Erfahrung mit beschränktem was ist, warum ich zu euch komme. Kann jemand von Ihnen Vorschläge für eine schnellere Haskell Implementierung bieten, oder Hinweise auf die Dokumentation, wie High-Performance-Haskell-Code zu schreiben?
Zuerst wird die jüngste Haskell Lösung (Uhren etwa 12 Sekunden). Ich habe versucht, das Knall-Muster stopft von dieser SO Post , aber es hat nicht machen eine Differenz AFAICT. Ersetzen ‚multAdd‘ mit ‚(\ iv -> v * 4).‘ Gebracht Ausführungszeit bis auf 1,9 Sekunden, so dass die bitweise Sachen (und damit auch die Herausforderungen an die automatische Optimierung) scheint nicht zu viel Schuld zu sein
{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 -fvia-C -optc-O3 -fexcess-precision -optc-march=native #-}
import Data.Vector.Storable
import qualified Data.Vector.Storable as V
import Foreign.C.Types
import Data.Bits
repCount = 10000
arraySize = 20000
a = fromList $ [0.2::CFloat, 0.1, 0.6, 1.0]
m = fromList $ [0.99::CFloat, 0.7, 0.8, 0.6]
multAdd :: Int -> CFloat -> CFloat
multAdd !i !v = v * (m ! (i .&. 3)) + (a ! (i .&. 3))
multList :: Int -> Vector CFloat -> Vector CFloat
multList !count !src
| count <= 0 = src
| otherwise = multList (count-1) $ V.imap multAdd src
main = do
print $ Data.Vector.Storable.sum $ multList repCount $
Data.Vector.Storable.replicate (arraySize*4) (0::CFloat)
Hier ist, was ich in C. Der Code haben hier ein paar #ifdefs hat, die es verhindert, dass straight-up zusammengestellt werden; scrollen Sie nach unten für den Testfahrer.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef float v4fs __attribute__ ((vector_size (16)));
typedef struct { float x, y, z, w; } Vector4;
void setv4(v4fs *v, float x, float y, float z, float w) {
float *a = (float*) v;
a[0] = x;
a[1] = y;
a[2] = z;
a[3] = w;
}
float sumv4(v4fs *v) {
float *a = (float*) v;
return a[0] + a[1] + a[2] + a[3];
}
void vecmult(v4fs *MAYBE_RESTRICT s, v4fs *MAYBE_RESTRICT d, v4fs a, v4fs m) {
for (int j = 0; j < N; j++) {
d[j] = s[j] * m + a;
}
}
void scamult(float *MAYBE_RESTRICT s, float *MAYBE_RESTRICT d,
Vector4 a, Vector4 m) {
for (int j = 0; j < (N*4); j+=4) {
d[j+0] = s[j+0] * m.x + a.x;
d[j+1] = s[j+1] * m.y + a.y;
d[j+2] = s[j+2] * m.z + a.z;
d[j+3] = s[j+3] * m.w + a.w;
}
}
int main () {
v4fs a, m;
v4fs *s, *d;
setv4(&a, 0.2, 0.1, 0.6, 1.0);
setv4(&m, 0.99, 0.7, 0.8, 0.6);
s = calloc(N, sizeof(v4fs));
d = s;
double start = clock();
for (int i = 0; i < M; i++) {
#ifdef COPY
d = malloc(N * sizeof(v4fs));
#endif
#ifdef VECTOR
vecmult(s, d, a, m);
#else
Vector4 aa = *(Vector4*)(&a);
Vector4 mm = *(Vector4*)(&m);
scamult((float*)s, (float*)d, aa, mm);
#endif
#ifdef COPY
free(s);
s = d;
#endif
}
double end = clock();
float sum = 0;
for (int j = 0; j < N; j++) {
sum += sumv4(s+j);
}
printf("%-50s %2.5f %f\n\n", NAME,
(end - start) / (double) CLOCKS_PER_SEC, sum);
}
Dieses Skript wird die Tests mit einer Reihe von gcc Flagkombinationen kompilieren und ausführen. Die beste Leistung wurde, hat von cmath-64-native-O3-beschränken-Vektor-nocopy auf meinem System unter 0,22 Sekunden.
import System.Process
import GHC.IOBase
cBase = ("cmath", "gcc mult.c -ggdb --std=c99 -DM=10000 -DN=20000")
cOptions = [
[("32", "-m32"), ("64", "-m64")],
[("generic", ""), ("native", "-march=native -msse4")],
[("O1", "-O1"), ("O2", "-O2"), ("O3", "-O3")],
[("restrict", "-DMAYBE_RESTRICT=__restrict__"),
("norestrict", "-DMAYBE_RESTRICT=")],
[("vector", "-DVECTOR"), ("scalar", "")],
[("copy", "-DCOPY"), ("nocopy", "")]
]
-- Fold over the Cartesian product of the double list. Probably a Prelude function
-- or two that does this, but hey. The 'perm' referred to permutations until I realized
-- that this wasn't actually doing permutations. '
permfold :: (a -> a -> a) -> a -> [[a]] -> [a]
permfold f z [] = [z]
permfold f z (x:xs) = concat $ map (\a -> (permfold f (f z a) xs)) x
prepCmd :: (String, String) -> (String, String) -> (String, String)
prepCmd (name, cmd) (namea, cmda) =
(name ++ "-" ++ namea, cmd ++ " " ++ cmda)
runCCmd name compileCmd = do
res <- system (compileCmd ++ " -DNAME=\\\"" ++ name ++ "\\\" -o " ++ name)
if res == ExitSuccess
then do system ("./" ++ name)
return ()
else putStrLn $ name ++ " did not compile"
main = do
mapM_ (uncurry runCCmd) $ permfold prepCmd cBase cOptions
Lösung
Roman Leschinkskiy antwortet:
Eigentlich sieht der Kern meist in Ordnung, mir. Mit unsafeIndex statt (!) macht mehr das Programm als doppelt so schnell ( meine Antwort oben sehen). Das Programm unten ist viel schneller, obwohl (Und sauberere, IMO). Ich vermute, die verbleibende Differenz zwischen diesem und das C-Programm ist auf GHC allgemeinen suckiness wenn es um die schwimmenden kommt Punkt. Der HEAD produziert die die besten Ergebnisse mit der NCG und -msse2
Zunächst definiert einen neuen Vec4 Datentyp:
{-# LANGUAGE BangPatterns #-}
import Data.Vector.Storable
import qualified Data.Vector.Storable as V
import Foreign
import Foreign.C.Types
-- Define a 4 element vector type
data Vec4 = Vec4 {-# UNPACK #-} !CFloat
{-# UNPACK #-} !CFloat
{-# UNPACK #-} !CFloat
{-# UNPACK #-} !CFloat
Stellen Sie sicher, wir es in einem Array
speicherninstance Storable Vec4 where
sizeOf _ = sizeOf (undefined :: CFloat) * 4
alignment _ = alignment (undefined :: CFloat)
{-# INLINE peek #-}
peek p = do
a <- peekElemOff q 0
b <- peekElemOff q 1
c <- peekElemOff q 2
d <- peekElemOff q 3
return (Vec4 a b c d)
where
q = castPtr p
{-# INLINE poke #-}
poke p (Vec4 a b c d) = do
pokeElemOff q 0 a
pokeElemOff q 1 b
pokeElemOff q 2 c
pokeElemOff q 3 d
where
q = castPtr p
Werte und Methoden auf diese Art:
a = Vec4 0.2 0.1 0.6 1.0
m = Vec4 0.99 0.7 0.8 0.6
add :: Vec4 -> Vec4 -> Vec4
{-# INLINE add #-}
add (Vec4 a b c d) (Vec4 a' b' c' d') = Vec4 (a+a') (b+b') (c+c') (d+d')
mult :: Vec4 -> Vec4 -> Vec4
{-# INLINE mult #-}
mult (Vec4 a b c d) (Vec4 a' b' c' d') = Vec4 (a*a') (b*b') (c*c') (d*d')
vsum :: Vec4 -> CFloat
{-# INLINE vsum #-}
vsum (Vec4 a b c d) = a+b+c+d
multList :: Int -> Vector Vec4 -> Vector Vec4
multList !count !src
| count <= 0 = src
| otherwise = multList (count-1) $ V.map (\v -> add (mult v m) a) src
main = do
print $ Data.Vector.Storable.sum
$ Data.Vector.Storable.map vsum
$ multList repCount
$ Data.Vector.Storable.replicate arraySize (Vec4 0 0 0 0)
repCount, arraySize :: Int
repCount = 10000
arraySize = 20000
Mit ghc 6.12.1, -O2 -fasm:
- 1.752
Mit ghc HEAD (26. Juni), -O2 -fasm -msse2
- 1.708
Das sieht aus wie die meisten idiomatische Weg, um eine Vec4 Array zu schreiben, und bekommt die beste Leistung (11x schneller als Original). (Und dies könnte ein Maßstab für LLVM Backend des GHC werden)
Andere Tipps
Nun, das ist besser. 3.5s statt 14s.
{-# LANGUAGE BangPatterns #-}
{-
-- multiply-add of four floats,
Vec4f multiplier, addend;
Vec4f vecList[];
for (int i = 0; i < count; i++)
vecList[i] = vecList[i] * multiplier + addend;
-}
import qualified Data.Vector.Storable as V
import Data.Vector.Storable (Vector)
import Data.Bits
repCount, arraySize :: Int
repCount = 10000
arraySize = 20000
a, m :: Vector Float
a = V.fromList [0.2, 0.1, 0.6, 1.0]
m = V.fromList [0.99, 0.7, 0.8, 0.6]
multAdd :: Int -> Float -> Float
multAdd i v = v * (m `V.unsafeIndex` (i .&. 3)) + (a `V.unsafeIndex` (i .&. 3))
go :: Int -> Vector Float -> Vector Float
go n s
| n <= 0 = s
| otherwise = go (n-1) (f s)
where
f = V.imap multAdd
main = print . V.sum $ go repCount v
where
v :: Vector Float
v = V.replicate (arraySize * 4) 0
-- ^ a flattened Vec4f []
Was ist besser, als es war:
$ ghc -O2 --make A.hs
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
$ time ./A
516748.13
./A 3.58s user 0.01s system 99% cpu 3.593 total
multAdd kompiliert just fine:
case readFloatOffAddr#
rb_aVn
(word2Int#
(and# (int2Word# sc1_s1Yx) __word 3))
realWorld#
of _ { (# s25_X1Tb, x4_X1Te #) ->
case readFloatOffAddr#
rb11_X118
(word2Int#
(and# (int2Word# sc1_s1Yx) __word 3))
realWorld#
of _ { (# s26_X1WO, x5_X20B #) ->
case writeFloatOffAddr#
@ RealWorld
a17_s1Oe
sc3_s1Yz
(plusFloat#
(timesFloat# x3_X1Qz x4_X1Te) x5_X20B)
Allerdings Sie tun 4-Element in einer Zeit vervielfacht im C-Code, so wir werden das direkt tun müssen, anstatt sie durch Looping fälschen und Maskierung. GCC ist wahrscheinlich die Schleife Abrollen auch.
So identische Leistung zu erhalten, wir den Vektor multiplizieren bräuchten (ein bisschen hart, möglicherweise über den LLVM-Backend) und entrollen die Schleife (möglicherweise Verschmelzen es). Ich werde hier auf Roman verschieben, um zu sehen, ob es andere offensichtliche Dinge.
Eine Idee könnte in der Tat sein, um einen Vektor Vec4 zu verwenden, anstatt es Abflachung.
