2012-07-21 15 views
21

मेरे पास कोड का एक टुकड़ा है जो sequence का उपयोग करके संभाव्यता वितरण से बार-बार नमूने करता है। नैतिक रूप से, यह ऐसा कुछ करता है:एक हास्केल प्रोग्राम प्रोफाइलिंग

sampleMean :: MonadRandom m => Int -> m Float -> m Float 
sampleMean n dist = do 
    xs <- sequence (replicate n dist) 
    return (sum xs) 

सिवाय इसके कि यह थोड़ा और जटिल है। वास्तविक कोड जिसमें मुझे रूचि है likelihoodWeightingthis Github repo पर फ़ंक्शन है।

मैंने देखा कि चलने का समय n के साथ nonlinearly स्केल करता है। विशेष रूप से, एक बार n एक निश्चित मान से अधिक हो जाता है, यह स्मृति सीमा को हिट करता है, और चलने का समय विस्फोट होता है। मुझे यकीन नहीं है, लेकिन मुझे लगता है कि ऐसा इसलिए है क्योंकि sequence उन हिस्सों की एक लंबी सूची तैयार कर रहा है जिन्हें sum पर कॉल तक मूल्यांकन नहीं किया जा रहा है।

एक बार जब मैं लगभग 100,000 नमूने प्राप्त करता हूं, तो प्रोग्राम क्रॉल में धीमा हो जाता है। मैं इसे अनुकूलित करना चाहता हूं (मेरी भावना यह है कि 10 मिलियन नमूने एक समस्या नहीं होनी चाहिए) इसलिए मैंने इसे प्रोफाइल करने का फैसला किया - लेकिन मुझे प्रोफाइलर के आउटपुट को समझने में थोड़ा परेशानी हो रही है।


रूपरेखा

मैं एक फ़ाइल main.hs 100,000 नमूने के साथ अपने समारोह चलाता है कि में एक छोटी निष्पादन योग्य बनाया। यहाँ

$ ghc -O2 -rtsopts main.hs 
$ ./main +RTS -s 

पहली बात मैं नोटिस करने से उत्पादन है - यह ढेर के लगभग 1.5 GB आबंटित करता है, और कचरा संग्रहण पर अपने समय का 60% खर्च करता है। क्या यह आम तौर पर बहुत आलस्य का संकेत है?

1,377,538,232 bytes allocated in the heap 
1,195,050,032 bytes copied during GC 
    169,411,368 bytes maximum residency (12 sample(s)) 
    7,360,232 bytes maximum slop 
      423 MB total memory in use (0 MB lost due to fragmentation) 

Generation 0: 2574 collections,  0 parallel, 2.40s, 2.43s elapsed 
Generation 1: 12 collections,  0 parallel, 1.07s, 1.28s elapsed 

INIT time 0.00s ( 0.00s elapsed) 
MUT time 1.92s ( 1.94s elapsed) 
GC time 3.47s ( 3.70s elapsed) 
RP time 0.00s ( 0.00s elapsed) 
PROF time 0.23s ( 0.23s elapsed) 
EXIT time 0.00s ( 0.00s elapsed) 
Total time 5.63s ( 5.87s elapsed) 

%GC time  61.8% (63.1% elapsed) 

Alloc rate 716,368,278 bytes per MUT second 

Productivity 34.2% of total user, 32.7% of total elapsed 

यहाँ से

$ ./main +RTS -p 

परिणाम पहली बार मैं इस भाग रहे हैं, यह पता चला एक समारोह को बार-बार बुलाया जा रहा था, और यह पता चला कि मैं इसे memoize सकता है, जो चीजों को भागा हालांकि, 2 के कारक से यह अंतरिक्ष रिसाव को हल नहीं किया है।

COST CENTRE   MODULE    no. entries %time %alloc %time %alloc 

MAIN     MAIN     1  0 0.0 0.0 100.0 100.0 
main     Main     434  4 0.0 0.0 100.0 100.0 
    likelihoodWeighting AI.Probability.Bayes 445  1 0.0 0.3 100.0 100.0 
    distributionLW  AI.Probability.Bayes 448  1 0.0 2.6  0.0 2.6 
    getSampleLW  AI.Probability.Bayes 446 100000 20.0 50.4 100.0 97.1 
    bnProb   AI.Probability.Bayes 458 400000 0.0 0.0  0.0 0.0 
    bnCond   AI.Probability.Bayes 457 400000 6.7 0.8  6.7 0.8 
    bnVals   AI.Probability.Bayes 455 400000 20.0 6.3 26.7 7.1 
    bnParents  AI.Probability.Bayes 456 400000 6.7 0.8  6.7 0.8 
    bnSubRef   AI.Probability.Bayes 454 800000 13.3 13.5 13.3 13.5 
    weightedSample AI.Probability.Bayes 447 100000 26.7 23.9 33.3 25.3 
    bnProb   AI.Probability.Bayes 453 100000 0.0 0.0  0.0 0.0 
    bnCond   AI.Probability.Bayes 452 100000 0.0 0.2  0.0 0.2 
    bnVals   AI.Probability.Bayes 450 100000 0.0 0.3  6.7 0.5 
     bnParents  AI.Probability.Bayes 451 100000 6.7 0.2  6.7 0.2 
    bnSubRef   AI.Probability.Bayes 449 200000 0.0 0.7  0.0 0.7 

यहां एक ढेर प्रोफ़ाइल है। मुझे नहीं पता कि यह रनटाइम का दावा क्यों करता है 1.8 सेकेंड - इस दौड़ में लगभग 6 सेकंड लग गए। अर्थात पहचान करने के लिए जहां टोंटी है, और कैसे चीजें तेजी लाने के लिए सुझाव प्रदान -

enter image description here

किसी को भी मुझे प्रोफाइलर के आउटपुट की व्याख्या करने में मदद कर सकते हैं?

+0

'अनुक्रम के बजाय' replicateM n' का उपयोग करने का प्रयास करें।प्रतिलिपि n' – dflemstr

+4

चलने वाले समय में कोई बदलाव नहीं - संभवतः यह आश्चर्यजनक नहीं है, क्योंकि 'प्रतिकृति एम एन' [परिभाषित] है [http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/नियंत्रण-Monad.html#replicateM) 'अनुक्रम। दोहराना दोहराएं। –

+1

'लंबाई xs' हमेशा' n' है, है ना? तो 'n' के साथ' (लंबाई xs) 'को प्रतिस्थापित करें और फिर 'xs' को किसी भी समय स्मृति में पूरी तरह से निवासी रहने की आवश्यकता नहीं है। – dave4420

उत्तर

12

में foldM का उपयोग करने से JohnL's suggestion को शामिल करके एक बड़ा सुधार पहले से ही हासिल किया जा चुका है। इससे दस गुणा के बारे में मेमोरी उपयोग कम हो गया, और जीसी टाइम्स को लगभग या वास्तव में नगण्य रूप से महत्वपूर्ण रूप से कम कर दिया गया।

एक रूपरेखा वर्तमान स्रोत पैदावार

probabilityIO    AI.Util.Util   26.1 42.4 413 290400000 
weightedSample.go   AI.Probability.Bayes 16.1 19.1 255 131200080 
bnParents     AI.Probability.Bayes 10.8 1.2 171 8000384 
bnVals      AI.Probability.Bayes 10.4 7.8 164 53603072 
bnCond      AI.Probability.Bayes 7.9 1.2 125 8000384 
ndSubRef     AI.Util.Array   4.8 9.2  76 63204112 
bnSubRef     AI.Probability.Bayes 4.7 8.1  75 55203072 
likelihoodWeighting.func AI.Probability.Bayes 3.3 2.8  53 19195128 
%!       AI.Util.Util   3.3 0.5  53 3200000 
bnProb      AI.Probability.Bayes 2.5 0.0  40  16 
bnProb.p     AI.Probability.Bayes 2.5 3.5  40 24001152 
likelihoodWeighting  AI.Probability.Bayes 2.5 2.9  39 20000264 
likelihoodWeighting.func.x AI.Probability.Bayes 2.3 0.2  37 1600000 

और 13MB स्मृति उपयोग -s द्वारा रिपोर्ट के साथ चलाने के लिए, ~ 5MB अधिकतम निवास। यह पहले से ही बहुत बुरा नहीं है।

फिर भी, कुछ बिंदुएं हैं जो हम सुधार सकते हैं। सबसे पहले, एक अपेक्षाकृत मामूली बात है, में भव्य योजना, AI.UTIl.Array.ndSubRef:

ndSubRef :: [Int] -> Int 
ndSubRef ns = sum $ zipWith (*) (reverse ns) (map (2^) [0..]) 

सूची पीछे, और मानचित्रण (2^) एक और सूची पर अक्षम है, बेहतर है

ndSubRef = L.foldl' (\a d -> 2*a + d) 0 

जो रखने के लिए की जरूरत नहीं है मेमोरी में पूरी सूची (शायद एक बड़ा सौदा नहीं है, क्योंकि सूचियां कम होंगी) क्योंकि इसे उलटकर, और दूसरी सूची आवंटित करने की आवश्यकता नहीं है।आवंटन में कमी, ध्यान देने योग्य है के बारे में 10%, और वह हिस्सा, कुछ हद तेजी से चलाता है

ndSubRef     AI.Util.Array   1.7 1.3  24 8000384 
संशोधित रन की प्रोफ़ाइल में

, लेकिन जब से यह केवल समग्र समय एक छोटा सा हिस्सा लेता है, समग्र प्रभाव है छोटे। weightedSample और likelihoodWeighting में तलना संभवतः बड़ी मछली है।

की है कि कैसे चीजें बदल जाता है देखने के लिए weightedSample में कठोरता का एक सा जोड़ें:

weightedSample :: Ord e => BayesNet e -> [(e,Bool)] -> IO (Map e Bool, Prob) 
weightedSample bn fixed = 
    go 1.0 (M.fromList fixed) (bnVars bn) 
    where 
     go w assignment []  = return (assignment, w) 
     go w assignment (v:vs) = if v `elem` vars 
      then 
       let w' = w * bnProb bn assignment (v, fixed %! v) 
       in go w' assignment vs 
      else do 
       let p = bnProb bn assignment (v,True) 
       x <- probabilityIO p 
       go w (M.insert v x assignment) vs 

     vars = map fst fixed 

go का वजन पैरामीटर मजबूर कभी नहीं है, और न ही, असाइनमेंट पैरामीटर है इस तरह वे Thunks का निर्माण कर सकते हैं। यह probabilityIO को पार करने से पहले तुरंत प्रभावी करने के लिए {-# LANGUAGE BangPatterns #-} और बल अद्यतन सक्षम है, यह भी मूल्यांकन p करते हैं:

go w assignment (v:vs) = if v `elem` vars 
    then 
     let !w' = w * bnProb bn assignment (v, fixed %! v) 
     in go w' assignment vs 
    else do 
     let !p = bnProb bn assignment (v,True) 
     x <- probabilityIO p 
     let !assignment' = M.insert v x assignment 
     go w assignment' vs 

कि आवंटन में एक और कमी (~ 9%) और एक छोटे से speedup (~% 13%) लाता है, लेकिन कुल स्मृति उपयोग और अधिकतम निवास में काफी बदलाव नहीं आया है।

मैं वहाँ बदलने के लिए, तो चलो likelihoodWeighting को देखो करने के लिए स्पष्ट और कुछ नहीं देखें: अंतिम पंक्ति में

func m _ = do 
    (a, w) <- weightedSample bn fixed 
    let x = a ! e 
    return $! x `seq` w `seq` M.adjust (+w) x m 

, पहले, w पहले से ही अब weightedSample में मूल्यांकन किया जाता है, इसलिए हमने इसे seq की जरूरत नहीं है यहां, अद्यतन x को अद्यतन मानचित्र का मूल्यांकन करने की आवश्यकता है, इसलिए seq आईएनजी आवश्यक नहीं है। उस रेखा पर बुरी चीज M.adjust है। adjust में अद्यतन फ़ंक्शन के परिणाम को मजबूर करने का कोई तरीका नहीं है, ताकि मानचित्र के मानों में थंक बन सकें। आप संशोधित मूल्य को देख और उस पर बाध्य करके Thunks के मूल्यांकन मजबूर कर सकते हैं, लेकिन जब से कुंजी द्वारा नक्शा अद्यतन किया जाता है की गारंटी है उपस्थित रहने की Data.Map यहाँ एक और अधिक सुविधाजनक तरीका प्रदान करता है,, insertWith':

func !m _ = do 
    (a, w) <- weightedSample bn fixed 
    let x = a ! e 
    return (M.insertWith' (+) x w m) 

(नोट: return $! ... के मुकाबले m पर जीएचसी बैंग-पैटर्न के साथ बेहतर अनुकूलित करता है)। यही कारण है कि थोड़ा कुल आवंटन कम कर देता है और कुछ हद चलने का समय परिवर्तन नहीं करता है, लेकिन इस्तेमाल किया कुल स्मृति और अधिकतम निवास पर काफी प्रभाव पड़ता है:

934,566,488 bytes allocated in the heap 
    1,441,744 bytes copied during GC 
     68,112 bytes maximum residency (1 sample(s)) 
     23,272 bytes maximum slop 
      1 MB total memory in use (0 MB lost due to fragmentation) 

समय चल रहा है में सबसे बड़ी सुधार के लिए randomIO से परहेज द्वारा किया जाएगा किया जा , इस्तेमाल किया गया StdGen बहुत धीमा है।

मुझे आश्चर्य है कि bn* कार्यों में कितना समय लगता है, लेकिन उन में कोई स्पष्ट अक्षमता दिखाई नहीं दे रही है।

+0

धन्यवाद डैनियल, यह वास्तव में उपयोगी है। मैंने आपके सुझाए गए परिवर्तन किए हैं और मैं 'randomIO' से छुटकारा पाने के आपके विचार को देखूंगा। मुझे लगता है कि मैं अब 'असली' हास्केल प्रोग्राम लिखने के करीब हूं ... –

+1

आपको मेरे काम से अधिक समय देने के लिए मेरा उपरांत मिलता है। –

4

मैंने यहां एक बहुत ही प्राथमिक उदाहरण रखा है, यहां पोस्ट किया गया: http://hpaste.org/71919। मुझे यकीन नहीं है कि यह आपके उदाहरण की तरह कुछ है .. काम करने लगते बस एक बहुत ही कम चीज है।

-prof और -fprof-auto साथ संकलन और 100000 पुनरावृत्तियों के साथ चल रहा रूपरेखा उत्पादन के निम्नलिखित प्रमुख (मेरी लाइन नंबर क्षमा) झुकेंगे:

8 COST CENTRE     MODULE    %time %alloc 
    9 
10 sample      AI.Util.ProbDist  31.5 36.6 
11 bnParents      AI.Probability.Bayes 23.2 0.0 
12 bnRank      AI.Probability.Bayes 10.7 23.7 
13 weightedSample.go    AI.Probability.Bayes 9.6 13.4 
14 bnVars      AI.Probability.Bayes 8.6 16.2 
15 likelihoodWeighting   AI.Probability.Bayes 3.8 4.2 
16 likelihoodWeighting.getSample AI.Probability.Bayes 2.1 0.7 
17 sample.cumulative    AI.Util.ProbDist  1.7 2.1 
18 bnCond      AI.Probability.Bayes 1.6 0.0 
19 bnRank.ps      AI.Probability.Bayes 1.1 0.0 

और यहाँ सारांश आँकड़े हैं:

1,433,944,752 bytes allocated in the heap 
1,016,435,800 bytes copied during GC 
    176,719,648 bytes maximum residency (11 sample(s)) 
    1,900,232 bytes maximum slop 
      400 MB total memory in use (0 MB lost due to fragmentation) 

INIT time 0.00s ( 0.00s elapsed) 
MUT  time 1.40s ( 1.41s elapsed) 
GC  time 1.08s ( 1.24s elapsed) 
Total time 2.47s ( 2.65s elapsed) 

%GC  time  43.6% (46.8% elapsed) 

Alloc rate 1,026,674,336 bytes per MUT second 

Productivity 56.4% of total user, 52.6% of total elapsed 

ध्यान दें कि प्रोफाइलर ने अपनी उंगली को sample पर इंगित किया है। मैं $! का उपयोग करके कि समारोह में return मजबूर कर दिया, और यहाँ कुछ सारांश आँकड़े बाद में कर रहे हैं:

1,776,908,816 bytes allocated in the heap 
    165,232,656 bytes copied during GC 
    34,963,136 bytes maximum residency (7 sample(s)) 
     483,192 bytes maximum slop 
      68 MB total memory in use (0 MB lost due to fragmentation) 

INIT time 0.00s ( 0.00s elapsed) 
MUT  time 2.42s ( 2.44s elapsed) 
GC  time 0.21s ( 0.23s elapsed) 
Total time 2.63s ( 2.68s elapsed) 

%GC  time  7.9% (8.8% elapsed) 

Alloc rate 733,248,745 bytes per MUT second 

Productivity 92.1% of total user, 90.4% of total elapsed 

बहुत अधिक जीसी के मामले में उत्पादक है, लेकिन बहुत ज्यादा नहीं समय पर बदल दिया है। आप अपनी बाधाओं को लक्षित करने और कुछ बेहतर प्रदर्शन करने के लिए इस प्रोफ़ाइल/ट्विक फैशन में पुन: प्रयास करने में सक्षम हो सकते हैं।

+0

बहुत बहुत धन्यवाद! सचमुच, मुझे प्रभावित है कि आप एक उदाहरण को एक साथ रखने के लिए काम करने के लिए मेरे भयानक कोड को पढ़ते हैं ... –

+0

त्वरित प्रश्न - मैं अपनी टेस्ट स्क्रिप्ट को '-prof -auto-all' के साथ संकलित कर रहा हूं लेकिन मुझे केवल मिलता है यदि मैं स्पष्ट '{- # SCC# -}' एनोटेशन जोड़ता हूं तो लागत केंद्र द्वारा टूटना। आप उन्हें स्वचालित रूप से कैसे प्राप्त करते हैं? मैंने '-प्रोफ-फ्रोफ-ऑटो' के साथ संकलन करने की कोशिश की लेकिन जीसीएच दूसरे ध्वज को पहचान नहीं पाया। –

+0

आपको पुराने जीएचसी का उपयोग करना होगा - मैं 7.4.1 का उपयोग कर रहा हूं, जो [इन प्रोफाइलिंग विकल्पों] का समर्थन करता है (http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/prof-compiler -options.html)। 7.0.2 [इन] का समर्थन करता है (http://www.haskell.org/ghc/docs/7.0.2/html/users_guide/prof-compiler-options.html); ऐसा लगता है कि '-auto-all' नेस्टेड फ़ंक्शंस को अनदेखा करता है। – jtobin

4

मुझे लगता है कि अपने प्रारंभिक निदान सही है, और मैं एक रूपरेखा रिपोर्ट उपयोगी है कि एक बार स्मृति प्रभाव में लात कभी नहीं देखा।

समस्या यह है कि आप sequence और फिर सूची से गुजरने रहे हैं दो बार, एक बार है sum के लिए। हास्केल में, बड़ी सूचियों के एकाधिक सूची ट्रैवर्स वास्तव में प्रदर्शन के लिए वास्तव में खराब हैं। समाधान आम तौर पर foldM जैसे कुछ प्रकार के फोल्ड का उपयोग करना है। आपका sampleMean समारोह के रूप में

{-# LANGUAGE BangPatterns #-} 

sampleMean2 :: MonadRandom m => Int -> m Float -> m Float 
sampleMean2 n dist = foldM (\(!a) mb -> liftM (+a) mb) 0 $ replicate n dist 
उदाहरण के लिए

लिखा जा सकता है, केवल एक बार सूची traversing।

आप likelihoodWeighting के साथ भी वही काम कर सकते हैं। Thunks को रोकने के लिए, यह सुनिश्चित करना महत्वपूर्ण है कि आपके गुना समारोह में जमाकर्ता उचित कठोरता है।

+0

आपका उदाहरण टाइप चेक नहीं करता है। चरण समारोह को 'लिफ्टएम' की तरह दिखना चाहिए। (+) '। यह थोड़ा और सख्त भी हो सकता है; 'randomRO' के साथ परीक्षण बड़ी संख्याओं के साथ अतिप्रवाह ढेर में आता है, शायद कुछ \ \ mb -> mb >> = \ b -> $ वापसी करें! ए + बी'? – Vitus

+0

धन्यवाद, मैं एक गुना के साथ 'likelihoodWeighting' rewriting ry होगा। –

+0

@ विटस - धन्यवाद, तय। मैं आमतौर पर सख्तता जोड़ने के लिए बैंग पैटर्न का उपयोग करना पसंद करता हूं, लेकिन आपका सुझाव शायद समान है। –

7

मुझे इन प्रोफाइलों को पचाने में परेशानी है, लेकिन मुझे अपने गधे को पहले लात मार दिया गया है क्योंकि MonadRandom हैकेज पर सख्त है। MonadRandom का आलसी संस्करण बनाना मेरी याददाश्त की समस्याएं दूर हो गईं।

मेरे सहयोगी को अभी तक कोड जारी करने की अनुमति नहीं मिली है, लेकिन मैंने Control.Monad.LazyRandom ऑनलाइन pastebin पर रखा है। या यदि आप कुछ अंश देखना चाहते हैं जो यादृच्छिक गणनाओं की अनंत सूचियों सहित पूरी तरह से आलसी यादृच्छिक खोज की व्याख्या करते हैं, तो Experience Report: Haskell in Computational Biology देखें।

+1

+1 इसे अधिक सख्त बनाने की नियमित सलाह के बजाय कम सख्त कार्यान्वयन का प्रस्ताव देने के लिए –

+0

धन्यवाद, यह एक दिलचस्प विचार है। डैनियल फिशर ने सुझाव दिया कि मैं अपनी यादों को 'यादृच्छिक' से छुटकारा पाता हूं, इसलिए मुझे लगता है कि मेरे नमूना कार्य करने से 'रैंड ए' वापस आ जाता है और फिर उन्हें 'evalRandIO' के साथ बुलाया जाता है। –

+1

@ क्रिस: मैंने अपना पेपर ऑनलाइन रखा है; इसमें 'रैंड ए' के ​​साथ कंप्यूटिंग के कुछ उदाहरण हैं। हम शीर्ष स्तर पर केवल एक बार 'evalRand' कहते हैं, या समानांतर गणनाओं की एक सूची को फोर्क करते समय। –

 संबंधित मुद्दे

  • कोई संबंधित समस्या नहीं^_^