हास्केल डेटा संरचनाएं और वे कचरा कलेक्टर को कैसे प्रभावित करते हैं

स्टैनफोर्ड क्रिप्टोग्राफी पाठ्यक्रम से समस्याओं में से एक को हल करने के लिए, एक Word64 -> पूर्णांक पत्राचार तालिका बनाना और कई मिलियन बार एक तत्व की उपस्थिति की जांच करना और एक नया जोड़ना आवश्यक था। समाधान स्पष्ट है: हैश टेबल। hoogle ने Data.HashTable का सुझाव दिया, कार्यक्रम लिखा गया था, इसने सफलतापूर्वक काम किया और आप सब कुछ भूल सकते हैं, लेकिन मैं प्रोफाइलिंग और अनुकूलन का अभ्यास करना चाहता था।

+ RTS -sstderr से शुरू होने से थोड़ा झटका लगा: लगभग आधा समय कचरा संग्रह पर व्यतीत हुआ।

13,902,917,208 बाइट्स ढेर में आवंटित
जीसी के दौरान 3,275,041,156 बाइट्स कॉपी किए गए
MUT समय 26.69 s (40.10s बीता हुआ)
जीसी समय 27.84s (32.47 सेकंड बीता)
% जीसी समय 51.1% (44.7% बीता हुआ)

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

शुरुआत के लिए, Data.HashTable को हैशटेबल्स के एक ट्रिपल के साथ बदल दिया गया है: बेसिक, कोयल और लिनियर। परिणाम कुछ आश्चर्यजनक थे: बुनियादी और कोयल ने समग्र परिचालन समय में बदलाव नहीं किया, लेकिन साथ ही, जीसी ने 70% समय लेना शुरू कर दिया। मूल कोड तेजी से काम करना शुरू कर दिया, और जीसी ने बाकी समय लिया। मेमोरी को काफी कम कॉपी किया गया था।

बेसिक:
ढेर में 12,781,006,960 बाइट आवंटित
जीसी के दौरान 408,935,780 बाइट्स कॉपी किए गए
MUT समय 15.00s (15.16 सेकंड बीतने पर)
जीसी का समय 43.29 (43.79 से अधिक)
% GC समय 74.3% (74.3% बीत चुका)

कोयल:
11,611,257,712 बाइट्स ढेर में आवंटित
419,308,168 बाइट्स जीसी के दौरान कॉपी किए गए
MUT समय 17.31s (17.65s बीत चुका है)
जीसी समय 38.08s (38.42 बीता हुआ)
% जीसी समय ६ed. GC% (६ 68.५% बीता हुआ)

रैखिक तालिका, जैसा कि एक की उम्मीद होगी, पूरी तरह से अलग परिदृश्यों के लिए अभिप्रेत है और प्रतियोगिता को तुरंत छोड़ देती है:
12,547,294,380 बाइट्स ढेर में आवंटित
जीसी के दौरान 17,997,812,764 बाइट्स कॉपी किए गए
MUT समय 26.65 (27.16 को समाप्त)
जीसी समय 123.72s (124.30s बीता हुआ)
% GC समय 82.3% (82.1% बीत चुका)

रीडिंग कोड की कुछ और अनुकूलन, तालिका के शुरू में सही आकार का संकेत और CuckooHashTable आत्मविश्वास से नेतृत्व लिया:
ढेर में आवंटित 3,835,164,148 बाइट्स
179,941,588 बाइट्स को जीसी के दौरान कॉपी किया गया
MUT समय 7.84s (7.97 बीत चुके)
जीसी समय 20.05s (20.18 सेकंड बीता)
% GC समय 71.9% (71.7% बीत गया)

कुल रनटाइम पहले ही आधा हो गया है, लेकिन जीसी पर 70% है? कंजर्वेटरी में कुछ बदलने की जरूरत है।
Data.Judy जूडी टेबल के कार्यान्वयन के लिए एक आवरण है, यह पूरी तरह से GC के अंतर्गत नहीं आता है और निर्णायक रूप से खेल के नियमों को बदलता है:
ढेर में आवंटित 5,366,256,252 बाइट्स
जीसी के दौरान 3,725,456 बाइट्स कॉपी किए गए
MUT समय 8.99s (9.12s बीत गया)
जीसी समय 1.44s (1.45s बीता हुआ)
% GC समय 13.4% (13.3% बीत चुका)

हीप प्रोफ़ाइल से पता चलता है कि आवंटित मेमोरी की मात्रा बिल्कुल नहीं बदलती है: एक फ्लैट क्षैतिज रेखा, सभी डेटा जीसी पहुंच से बाहर है।

तीन नुकसान:

• आपको -fvia-C फेंककर पैकेज को पैच करने की आवश्यकता है, इसके बिना पूरी तरह से अनजाने लिंक की त्रुटियां सामने आती हैं;
• वर्ड से वर्ड की सख्ती से मैपिंग करें, इसलिए वर्ड 64 कीज के लिए आपको एरे की एक सरणी बनानी होगी। स्रोत में बाइटस्ट्रिंग को संचय करने का एक उदाहरण है, लेकिन फिर भी अनावश्यक काम;
• और अंत में, सी में, मैं यह सब सीधे लिख सकता हूं! हमारे साथ हास्केल या कहाँ?

क्या बचा है? बेशक Data.Map। कोई IO, कोई C, सच्चा हैस्केल कोड, जो सुंदर दिखता है। परिणाम SUDDEN हैं:
5,569,024,484 बाइट्स ढेर में आवंटित
4,241,345,748 बाइट्स जीसी के दौरान कॉपी किए गए
MUT समय 18.55s (18.77 सेकंड बीता)
जीसी समय 12.66s (13.07 वर्ष बीता)
% GC समय 40.6% (41.1% बीत चुका)

CuckooHashTable की तुलना में सिर्फ 10% धीमा, और Data.HashTable के साथ कोई तुलना नहीं। "सोचने की ज़रूरत नहीं है, बस हिलाओ" के लिए एक तैयार चित्रण: ये सभी नृत्य क्यों, यदि आप पूरी तरह से सीधा कोड लिख सकते हैं और नुकसान लगभग अदृश्य हैं?

और Data.HashMap.Strict के साथ unordered- कंटेनरों का अंतिम तार, Data.Map के लिए एक त्वरित प्रतिस्थापन: बस आयात और संरचना प्रकार बदलें, बाकी संगत है।
5,688,939,936 बाइट्स ढेर में आवंटित
जीसी के दौरान 3,659,088,964 बाइट्स कॉपी किए गए
227,864,212 बाइट्स अधिकतम निवास (23 नमूना)
MUT का समय 10.16s (10.75 को बीता हुआ)
जीसी समय 8.93s (9.61s बीता हुआ)
% GC समय 46.8% (47.2% समाप्त)

प्रोफ़ाइल पर बहुत सारी कॉपी की गई, तालिका के स्पष्ट रूप से दिखाई देने वाले पुन: आवंटन पर। आइए थोड़ी और मेमोरी को तुरंत खिसकाने की कोशिश करें, + RTS -A250M।
ढेर में आवंटित 5,663,421,460 बाइट
887,689,168 बाइट्स जीसी के दौरान कॉपी किए गए
MUT समय 11.40s (11.70s बीता हुआ)
जीसी समय 3.61s (3.83 बीत चुके)
% GC समय 24.1% (24.7% बीत चुका)

टा-दा! जूडी कम पड़ जाते हैं, लेकिन अन्य सभी विकल्प पीछे रह जाते हैं। नि: शुल्क बोनस के रूप में, Data.Map के रूप में एक ही बन्स: आपको हैश रूपांतरण के लिए अपनी कुंजी लिखने की आवश्यकता नहीं है, जैसे कि हैशटेबल्स में, आपको मोनाड्स में सब कुछ डालने की ज़रूरत नहीं है, कोड दो गुना छोटा है।

खैर, पारंपरिक निष्कर्ष: समयपूर्व अनुकूलन सभी बुराई की जड़ है। ललाट समाधान बाकी की तुलना में अच्छी तरह से तेज हो सकता है।