कार्यान्वयन

treap में सुधार यहाँ (अंतर्निहित कुंजी और नोड्स में संग्रहीत कुछ अतिरिक्त जानकारी के साथ) treap का एक तरह से मेरी कार्यान्वयन है: http://hpaste.org/42839/treap_with_implicit_keys कार्यान्वयन

डेटा जीसी की रूपरेखा के अनुसार इस कार्यक्रम के लिए समय के 80% लेता है। जहां तक मैं समझता हूं, यह इस तथ्य के कारण होता है कि प्रत्येक बार जब नोड 'संशोधित' होता है, तो रूट के पथ पर प्रत्येक नोड पुनर्निर्मित होता है।

क्या प्रदर्शन में सुधार करने के लिए मैं कुछ कर सकता हूं या मुझे एसटी मोनड के दायरे में उतरना है?

स्रोत

2011-01-07 adamax

@adamax: यह व्यवहार (रूट पर सबकुछ फिर से बनाना) अपरिवर्तनीय संरचनाओं में आम है, क्या आपने क्रिस ओकासाकी द्वारा शुद्ध रूप से कार्यात्मक डेटा संरचनाएं पढ़ी हैं? http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf उन्होंने इस पर कई कागजात लिखे। –

शायद आप के साथ '+ आरटीएस -s -RTS' अपने कार्यक्रम चलाकर इस की पुष्टि करनी चाहिए के रूप में मैं इस 80% आप जब मैं यह 7.0.1 का उपयोग कर एक त्वरित रन दे दी है की बात नहीं देख सकते हैं, मैं के बारे में 16% समय बिताया देखना जीसी में – ScottWest

@ScottWest: मैं के साथ GHC -O2 -prof --make test.hs यह संकलन और के साथ चलाने के ./test + आरटीएस -s -RTS, यह कहता है% जीसी समय 77.4% (77.4% बीता), कुल समय 8.7 है सेकंड। लेकिन मेरा ghc संस्करण 6.12.1 है। बस ब्याज से बाहर, आपके सिस्टम में कुल समय क्या है? – adamax

GHC 7.0.3 का उपयोग करना, मैं अपने भारी जीसी व्यवहार को पुनः कर सकते हैं:

$ time ./A +RTS -s 
    %GC time  92.9% (92.9% elapsed) 
    ./A +RTS -s 7.24s user 0.04s system 99% cpu 7.301 total

मैं 10 मिनट खर्च कार्यक्रम के माध्यम से जा रहा है। यहाँ मैं क्या किया, क्रम में है:

सेट GHC के एच झंडा, जीसी में सीमा में वृद्धि
खोल
इनलाइन किए जाने वाले पहली पीढ़ी के आवंटन क्षेत्र को एडजस्ट करना में सुधार चेक

10 गुना गति के परिणामस्वरूप, और जीसी लगभग 45% समय के परिणामस्वरूप।

लिए, GHC का जादू -H ध्वज का उपयोग कर, हम उस क्रम काफ़ी कम कर सकते हैं:

$ time ./A +RTS -s -H 
    %GC time  74.3% (75.3% elapsed) 
    ./A +RTS -s -H 2.34s user 0.04s system 99% cpu 2.392 total

बुरा नहीं है!

Tree नोड्स पर यूएनपीएक्स प्रागम्स कुछ भी नहीं करेंगे, इसलिए उनको हटा दें।

इनलाइन करने update अधिक क्रम बंद shaves:

./A +RTS -s -H 1.84s user 0.04s system 99% cpu 1.883 total

रूप height

./A +RTS -s -H 1.74s user 0.03s system 99% cpu 1.777 total

इनलाइनिंग करता है तो यह तेजी से है, जबकि, जीसी अभी भी हावी है -, हम आवंटन परीक्षण कर रहे हैं के बाद से सब के बाद ।

./A +RTS -s -A100M 0.74s user 0.09s system 99% cpu 0.826 total

जो, है क्या 10x तेजी से हम शुरू कर दिया,

$ time ./A +RTS -s -A200M 
%GC time  45.1% (40.5% elapsed) 
./A +RTS -s -A200M 0.71s user 0.16s system 99% cpu 0.872 total

और खुलासा सीमा में वृद्धि, के रूप में JohnL सुझाव दिया एक छोटे से मदद करता है,: एक बात हम कर सकते हैं पहले जनरल आकार में वृद्धि है ? बुरा नहीं।

ghc-gc-tune का उपयोग करके आप -A और -H के एक समारोह के रूप में क्रम देख सकते हैं,

Time and GC

दिलचस्प है, सबसे अच्छा चल रहा है कई बार बहुत बड़ी -A मूल्यों, उदा का उपयोग

$ time ./A +RTS -A500M 
./A +RTS -A500M 0.49s user 0.28s system 99% cpu 0.776s

स्रोत

2011-04-17 00:16:27

वाह, यह अविश्वसनीय है! मेरे पास ghc 6.12.1 के साथ एक समान व्यवहार है, सबसे बड़ा स्पीडअप 'अपडेट' को रेखांकित करके और पहले जीन आकार को सेट करके दिया जाता है। एक सवाल, क्या आप -एच के लिए 'आकार' विकल्प शामिल करना भूल गए? बस -एच कुछ भी नहीं प्रतीत होता है, जबकि -H64m, उदाहरण के लिए, करता है। – adamax

जीएचसी 7 के साथ, -एच जीसी –

के लिए सभी सीमाएं बढ़ाता है और अधिक सटीक, -एच एक प्रकार का "स्वचालित-ए" है, यह -ए सेटिंग बढ़ाता है लेकिन समग्र स्मृति उपयोग को बढ़ाए बिना। यह संभव है क्योंकि हम जीसी की प्रतिलिपि बना रहे हैं, इसलिए प्रमुख जीसी के बीच बहुत सारी यादें अप्रयुक्त हैं। बढ़ रहा है- ए हमेशा एक अच्छा विचार नहीं है - कुछ कार्यक्रमों में यह बढ़ी हुई कैश यादों के कारण चीजों को और खराब कर देगा। –

कार्यान्वयन

उत्तर

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