मल्टीप्ली-एडे ऑपरेशन पर हास्केल गणित प्रदर्शन

Question

मैं हास्केल में एक गेम लिख रहा हूं, और यूआई में मेरे वर्तमान पास में ज्यामिति की बहुत सारी प्रक्रियात्मक पीढ़ी शामिल है। मैं वर्तमान में एक विशेष आपरेशन (सी-ish स्यूडोकोड) के प्रदर्शन की पहचान करने पर ध्यान केंद्रित कर रहा हूँ:

Vec4f multiplier, addend; 
Vec4f vecList[]; 
for (int i = 0; i < count; i++) 
    vecList[i] = vecList[i] * multiplier + addend; 

है यही कारण है, एक दलदल की मानक चार तैरता के गुणा-ऐड, बात SIMD अनुकूलन के लिए परिपक्व की तरह।

परिणाम ओपनजीएल वर्टेक्स बफर पर जा रहा है, इसलिए इसे अंततः एक फ्लैट सी सरणी में डालना होगा। इसी कारण से, गणना सी 'फ्लोट' प्रकारों पर संभवतः की जानी चाहिए।

मैंने हास्केल में इस तरह की चीज को जल्दी से करने के लिए या तो लाइब्रेरी या देशी बेवकूफ समाधान की तलाश की है, लेकिन मेरे द्वारा आने वाले हर समाधान के प्रदर्शन के लगभग 2% (यानी, 50x धीमी गति से) जीसीसी से सी की तुलना में धीमी झंडे के साथ। अनुमोदित, मैंने कुछ हफ्ते पहले हास्केल के साथ शुरुआत की, इसलिए मेरा अनुभव सीमित है-यही कारण है कि मैं आप लोगों के पास आ रहा हूं। क्या आप में से कोई भी तेज हास्केल कार्यान्वयन के लिए सुझाव प्रदान कर सकता है, या उच्च प्रदर्शन वाले हास्केल कोड को लिखने के तरीके पर दस्तावेज़ों के लिए पॉइंटर्स?

पहला, सबसे हालिया हास्केल समाधान (लगभग 12 सेकंड घड़ियों)। मैंने this SO post से बैंग-पैटर्न सामग्री की कोशिश की, लेकिन इससे AFAICT में कोई फर्क नहीं पड़ता। '(\ I v -> v * 4)' के साथ 'multAdd' को प्रतिस्थापित करने से निष्पादन समय 1.9 सेकेंड तक चला गया, इसलिए बिटवाई सामान (और स्वचालित अनुकूलन के लिए परिणामी चुनौतियां) गलती पर बहुत अधिक प्रतीत नहीं होती हैं।

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

यहां मेरे पास सी है। इस कोड में कुछ #ifdefs हैं जो इसे सीधे संकलित करने से रोकते हैं; परीक्षण चालक के लिए नीचे स्क्रॉल करें।

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

यह स्क्रिप्ट संकलन और कई जीसीसी ध्वज संयोजनों के साथ परीक्षण चलाएगी। सबसे अच्छा प्रदर्शन मेरे सिस्टम पर cmath-64-native-O3-limit-vector-nocopy द्वारा 0.22 सेकंड ले रहा था।

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 

Answer 1

रोमन Leschinkskiy प्रतिक्रिया करता है:

वास्तव में, कोर ज्यादातर मुझे के लिए ठीक लग रहा है। के बजाय का उपयोग करना unsafeIndex (!) कार्यक्रम दो बार तेजी (see my answer above) के रूप में की तुलना में अधिक बनाता है। नीचे प्रोग्राम बहुत तेज है, हालांकि (और क्लीनर, आईएमओ)। मैं इस और के बीच शेष अंतर सी कार्यक्रम GHC के सामान्य suckiness की वजह से है, जब यह चल बात करने के लिए आता है संदेह है। HEAD NCG साथ सबसे अच्छा परिणाम और पैदा करता है -msse2

सबसे पहले, एक नया Vec4 डेटा के प्रकार को परिभाषित:

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

सुनिश्चित करें हम एक सरणी में यह स्टोर कर सकते हैं

instance 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 

मान

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 

: और इस प्रकार के तरीकों

GHC 6.12.1, -O2 -fasm के साथ:

• 1.752

GHC HEAD (जून 26) के साथ

, -O2 -fasm -msse2

• 1.708

यह सबसे मुहावरेदार तरह से एक Vec4 सरणी लिखने के लिए की तरह लग रहा है, और सबसे अच्छा performan हो जाता है सीई (आपके मूल से 11x तेज)। (और यह जीएचसी के एलएलवीएम बैकएंड के लिए बेंचमार्क बन सकता है)

Answer 2

अच्छा, यह बेहतर है। 14 एस के बजाय 3.5 एस।

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

कौन सा बेहतर है की तुलना में यह था:

$ 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 ठीक संकलित:

 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) 

हालांकि, अगर आप सी कोड में एक समय पलता पर 4-तत्व कर रहे हैं , इसलिए हमें लूपिंग और मास्किंग द्वारा इसे फिक्र करने के बजाय इसे सीधे करने की आवश्यकता होगी। जीसीसी शायद लूप को अनलॉक कर रहा है।

तो समान प्रदर्शन प्राप्त करने के लिए, हमें वेक्टर गुणा करने की आवश्यकता होगी (शायद थोड़ा एलएलवीएम बैकएंड के माध्यम से) और लूप को अनलोल करें (संभवतः इसे फ्यूज करना)। मैं यहां देखने के लिए रोमन को रोक दूंगा कि क्या अन्य स्पष्ट चीजें हैं।

एक विचार वास्तव में वेक्टर Vec4 का उपयोग करने के बजाय इसे फ़्लैटन करने के बजाय हो सकता है।