डेटा का अनुक्रमण है। Vector.Unboxed.Mutable.MVector वास्तव में यह धीमा?

Question

मेरे पास एक ऐसा एप्लिकेशन है जो Kahan summation algorithm का उपयोग करके उच्च आयामी वैक्टर (मंद = 100) की एक बड़ी सूची (10^7) के केंद्र की गणना करने के अपने 80% समय का खर्च करता है। मैंने संक्षेप में अनुकूलन करने के लिए अपना सर्वश्रेष्ठ प्रयास किया है, लेकिन यह अभी भी समकक्ष सी कार्यान्वयन की तुलना में 20x धीमी है। प्रोफाइलिंग इंगित करता है कि अपराधी और unsafeWriteData.Vector.Unboxed.Mutable से फ़ंक्शन हैं। मेरा सवाल है: क्या ये कार्य वास्तव में धीमे हैं या क्या मैं प्रोफाइलिंग आंकड़ों को गलत समझ रहा हूं?

यहां दो कार्यान्वयन हैं। Haskell एक llvm बैकएंड का उपयोग कर ghc-7.0.3 के साथ संकलित है। सी एक 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 

LLVM बैकएंड का उपयोग कर GHC-7.0.3 के साथ संकलन:

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 

सी में बराबर कार्यान्वयन:

#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-जीसीसी के साथ संकलित:

>llvm-gcc -o Test_c -O3 -msse2 -std=c99 test.c 

>time ./Test_c 
real 0m0.096s 
user 0m0.088s 
sys  0m0.004s 

अद्यतन 1: मैं अन-inlined सी संस्करण में kahanStep। यह मुश्किल से प्रदर्शन में एक दांत बना दिया। मुझे उम्मीद है कि अब हम सभी अम्दाहल के कानून को स्वीकार कर सकते हैं और आगे बढ़ सकते हैं। kahanStep के रूप में अक्षम हो सकता है, unsafeRead और unsafeWrite 9-10x धीमी हैं। मैं उम्मीद कर रहा था कि कोई उस तथ्य के संभावित कारणों पर कुछ प्रकाश डाल सकता है।

इसके अलावा, मैं कहना चाहिए कि के बाद से मैं एक पुस्तकालय Data.Vector.Unboxed का उपयोग करता है के साथ बातचीत कर रहा हूँ, इसलिए मैं इस बिंदु पर थोड़े से शादी कर रहा हूँ, और इसके साथ अलग बहुत दर्दनाक होगा :-)

अद्यतन 2 : मुझे लगता है कि मैं अपने मूल प्रश्न में पर्याप्त स्पष्ट नहीं था। मैं इस microbenchmark को तेज करने के तरीकों की तलाश नहीं कर रहा हूं। मैं काउंटर अंतर्ज्ञानी प्रोफाइलिंग आंकड़ों की व्याख्या की तलाश में हूं, इसलिए मैं तय कर सकता हूं कि vector के खिलाफ एक बग रिपोर्ट दर्ज करना है या नहीं।

Answer 1

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

मैं एक सी संस्करण है कि हास्केल संस्करण के करीब है बना दिया है,

कहां।ज:

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% पहली सी संस्करण यहाँ की तुलना में धीमी चलाता है (0.1 एस बनाम 0.079 एस)।

अब आपके पास सी में उच्च ऑर्डर फ़ंक्शन है, मूल से काफी धीमा है, लेकिन अभी भी हास्केल कोड से बहुत तेज़ है। एक महत्वपूर्ण अंतर सी समारोह double और एक अनबॉक्स्ड double तर्कों के रूप का एक अनबॉक्स्ड जोड़ी लेता है कि, हास्केल kahanStep बॉक्सिंग Double एस के एक बॉक्स्ड जोड़ी और एक बॉक्सिंग Double लेता है और बॉक्सिंग Double एस के एक बॉक्स्ड जोड़ी देता है, जबकि, महंगा की आवश्यकता होती है foldV लूप में मुक्केबाजी और अनबॉक्सिंग। यह अधिक इनलाइनिंग द्वारा संबोधित किया जा सकता है। स्पष्ट रूप से foldV, kahanStep इनलाइन करने, और step समय 0.90s 0.74s यहाँ से नीचे GHC-7.0.4 (यह 0.90s करने के लिए नीचे GHC-7.4.1 के उत्पादन पर एक छोटे प्रभाव पड़ता है, 0.99s से) के साथ लाता है।

लेकिन मुक्केबाजी और अनबॉक्सिंग, अंतर के छोटे हिस्से हैं, हां। foldV सी के kahan से कहीं अधिक है, यह वैक्टरों की सूची संग्रहक को संशोधित करने के लिए उपयोग किया जाता है। वेक्टर की सूची सी कोड में पूरी तरह से अनुपस्थित है, और इससे बड़ा अंतर आता है। इन सभी 100000 वैक्टरों को आवंटित, भरना और एक सूची में रखा जाना चाहिए (आलस्य के कारण, उनमें से सभी एक साथ जीवित नहीं हैं, इसलिए कोई अंतरिक्ष समस्या नहीं है, लेकिन वे, साथ ही साथ सूची कक्षों को आवंटित करना और कचरा होना है एकत्रित, जो काफी समय लेता है)। और लूप उचित में, Word# को एक रजिस्टर में पास करने के बजाय, प्रीकंप्यूटेड मान वेक्टर से पढ़ा जाता है।

आप हास्केल के लिए सी के एक और अधिक प्रत्यक्ष अनुवाद का उपयोग करते हैं,

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

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

मुझे नहीं लगता कि इंडेक्सिंग वास्तव में अपराधी है। वेक्टर पैकेज संकलक जादू पर भारी निर्भर करता है, लेकिन प्रोफाइलिंग समर्थन के लिए संकलन बड़े पैमाने पर उसमें हस्तक्षेप करता है। vector या bytestring जैसे पैकेजों के लिए जो ऑप्टिमाइज़ेशन के लिए अपने स्वयं के फ़्यूज़न फ्रेमवर्क का उपयोग करते हैं, प्रोफाइलिंग हस्तक्षेप बल्कि विनाशकारी हो सकता है और प्रोफाइलिंग परिणाम पूरी तरह बेकार हो सकते हैं। मुझे विश्वास है कि हमारे पास ऐसा मामला है।

कोर में, रीड और राईट primops readDoubleArray#, indexDoubleArray# और writeDoubleArray#, जो तेजी से कर रहे हैं करने के लिए बदल रहे हैं। हो सकता है कि सी सर एक्सेस से थोड़ी धीमी हो, लेकिन बहुत ज्यादा नहीं। तो मुझे विश्वास है कि यह समस्या और बड़े अंतर का कारण नहीं है। लेकिन आपने उन पर {-# SCC#-} एनोटेशन लगाए हैं, इसलिए किसी भी अनुकूलन को अक्षम करना शामिल है जिसमें से किसी भी शर्तों का पुनर्गठन शामिल है। और प्रत्येक बार इन बिंदुओं में से एक दर्ज किया जाता है, इसे रिकॉर्ड किया जाना चाहिए। मैं, एक डेटा बिंदु के रूप में प्रोफाइलर और अनुकूलक को पता है कि वास्तव में क्या होता है के साथ पर्याप्त परिचित नहीं हूँ, लेकिन, foldV, step और kahanStep, एक रूपरेखा इन SCCS के साथ चलने पर {-# INLINE #-} pragmas के साथ 3 ले लिया।17 एस, और एससीसी fV_step, fV_read, fV_index, fV_write और fV_apply हटा दिए गए (कुछ और नहीं बदला गया) एक प्रोफाइलिंग रन केवल 2.03 (दोनों बार +RTS -P द्वारा रिपोर्ट किया गया था, इसलिए प्रोफाइलिंग ओवरहेड घटाया गया था)। उस अंतर से पता चलता है कि सस्ते कार्यों पर एससीसी और बहुत बढ़िया एससीसी बड़े पैमाने पर प्रोफाइलिंग परिणामों को छोड़ सकते हैं। अब अगर हम प्रागमा mkVect, kahan और prng पर भी डालते हैं, तो हमें पूरी तरह से अनौपचारिक प्रोफ़ाइल के साथ छोड़ दिया जाता है, लेकिन रन केवल 1.23 लेता है। (हालांकि, इन अंतिम इनलाइनिंगों में गैर-प्रोफाइलिंग रनों के लिए कोई प्रभाव नहीं पड़ता है, वे प्रोफाइलिंग के बिना स्वचालित रूप से रेखांकित हैं।)

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

जब आपके पास संदिग्ध प्रोफाइलिंग परिणाम होता है, तो जांचें कि जब आप कुछ एससीसी हटाते हैं तो क्या होता है। यदि इसका परिणाम रन टाइम की एक बड़ी बूंद में होता है, तो एससीसी आपकी प्राथमिक समस्या नहीं थी (अन्य समस्याओं को ठीक करने के बाद यह फिर से समस्या हो सकती है)। वैसे, कि से {-# NOINLINE #-} pragma निकालने के लिए, यह प्रतिकूल है - - पाश में बॉक्सिंग Double एस के एक बॉक्स्ड जोड़ी का उत्पादन किया, कि

कोर को देखते हुए अपने कार्यक्रम के लिए उत्पन्न, क्या बाहर कूद गया है कि अपने kahanStep था तुरंत deconstructed और घटकों unboxed था। मूल्यों की इस तरह की अनावश्यक मध्यवर्ती मुक्केबाजी महंगा है और बहुत कम गणना करता है।

---

इस रूप में आज फिर haskell-cafe पर आया था, जहां किसी को GHC-7.4.1 के साथ ऊपर कोड से भयानक प्रदर्शन मिला, tibbe खुद पर ले लिया कोर कि GHC उत्पादित जांच करने के लिए और पाया कि GHC करने से इनकी कोड का उत्पादन Word से Double पर रूपांतरण के लिए। केवल (लपेटा) प्राइमेटिव का उपयोग करके कस्टम रूपांतरण के साथ रूपांतरण के fromIntegral को प्रतिस्थापित करना (और बैंग पैटर्न को हटा देना जो यहां कोई फर्क नहीं पड़ता है, जीएचसी का सख्त विश्लेषण विश्लेषक एल्गोरिदम के माध्यम से देखने के लिए पर्याप्त है, मुझे इसे और अधिक विश्वास करना सीखना चाहिए

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

Answer 2

इस प्रतीत होता है Data.Vector कोड के सभी में सूची combinators का एक अजीब मिश्रण है:;), हम एक संस्करण मूल सी के लिए gcc -O3 के उत्पादन के साथ सममूल्य पर है कि प्राप्त करते हैं। अगर मैं पहले ही स्पष्ट संशोधन, Data.Vector.Unboxed के सही उपयोग के साथ

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

जगह बनाने:

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

तो मेरा समय हो जाता है दो तिहाई से - real 0m0.429s करने के लिए real 0m1.306s से यह के सभी तरह लग रहा है शीर्ष स्तर के कार्यों में prng और zero

Answer 3

मुझे पता है कि आपने इस माइक्रो-बेंचमार्क को बेहतर बनाने के लिए कोई तरीका नहीं पूछा है, लेकिन मैं आपको एक स्पष्टीकरण दूंगा भविष्य में लूप लिखते समय एचटी उपयोगी साबित होता है:

एक अज्ञात फ़ंक्शन कॉल, जैसे कि foldV के उच्च-आदेश तर्क में किए गए एक, लूप में अक्सर किए जाने पर महंगा हो सकता है। विशेष रूप से, यह फ़ंक्शन तर्कों के अनबॉक्सिंग को रोक देगा, जिससे आवंटन में वृद्धि होगी।तर्क अनब्लॉकिंग को अवरुद्ध करने का कारण यह है कि हम नहीं जानते कि हम जिस फ़ंक्शन को बुला रहे हैं वह उन तर्कों में सख्त है और इस प्रकार हम तर्कों को उदा। (Double, Double), Double# -> Double# के बजाय।

यदि लूप (उदा। foldV) लूप बॉडी (उदा। kahanStep) से मिलता है तो संकलक सख्त जानकारी को समझ सकता है। इसी कारण से मैं अनुशंसा करता हूं कि लोग INLINE उच्च-आदेश कार्य करें। इस मामले में, foldV को रेखांकित करना और NOINLINE को kahanStep पर हटाकर रनटाइम को मेरे लिए थोड़ा सा सुधारता है।

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

Answer 4

इस मेलिंग सूची पर आया और मुझे पता चला वहाँ Word- में एक बग है कि> GHC 7.4.1 में डबल रूपांतरण कोड (कम से कम)। इस संस्करण है, जो बग के आसपास काम करता है, मेरी मशीन पर सी कोड के रूप में के रूप में तेजी से होता है:

{-# 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-> डबल बग के आसपास काम करने से, मैं भी हटा दिया है अतिरिक्त सूचियों सी संस्करण से मेल करने के लिए बेहतर।