C # में मेमोरी में बड़ी मात्रा में डेटा प्रोसेस करना

मैं स्मृति में बड़ी मात्रा में डेटा लोड करने और संसाधित करने के लिए हाल ही में सी # में प्राप्त अपने अनुभव को साझा करना चाहता हूं। निम्नलिखित सभी विजुअल स्टूडियो 2008 और .Net फ्रेमवर्क 3.5.1 पर लागू होते हैं, अगर भाषा या पुस्तकालयों के अन्य संस्करणों में कोई अंतर है।

इसलिए, हमारे पास निम्नलिखित कार्य थे:
1. स्मृति में स्टोर करने के लिए एक स्ट्रिंग 16 वर्णों (अद्वितीय कुंजी) और दो पूर्णांक मान, 4 बाइट्स प्रत्येक से मिलकर 100 मिलियन रिकॉर्ड तक;
2. जल्दी से कुंजी द्वारा एक रिकॉर्ड ढूंढें और संपादित करें।

समस्या नंबर 1 का समाधान। स्मृति में स्थान।

चलो पोस्ट करके शुरू करते हैं। रिकॉर्ड में उपयोगी जानकारी का कुल आकार 24 बाइट्स है। पूरे डेटा ऐरे को लगभग 2.4 जीबी पर कब्जा करना चाहिए (हम 1024 सीमा के साथ सटीक पुनर्गणना से नहीं निपटेंगे)। यहां पहली परेशानी हमें इंतजार कर रही है: x32 पर, विंडोज ओएस प्रक्रिया केवल 2 जीबी आवंटित कर सकती है। व्यवहार में, .Net प्रक्रिया में, यह मान और भी कम है, मैं 1.8 जीबी के आसपास कहीं आवंटित करने में कामयाब रहा। मुझे लगता है कि बाकी जगह परियोजना में उपयोग किए जाने वाले पुस्तकालयों द्वारा कब्जा कर लिया गया है। इस प्रकार हम पूरी समस्या को x64 प्लेटफॉर्म पर ही हल कर सकते हैं। उदाहरण में, हम अभी भी तुलना के लिए x32 पर विचार करेंगे।

इसलिए, आगे की हलचल के बिना, एक पेन (माउस और कीबोर्ड) लें और जो मन में आता है उसे तुरंत गढ़ना शुरू करें। हम स्मृति में रिकॉर्ड का एक प्रतिनिधि बनाते हैं:

public class Entry { public string Key; public int IntValue1; public int IntValue2; } 

Int alias क्रॉस-प्लेटफ़ॉर्म है और हमेशा Int32 से मेल खाता है, इसलिए यह x32 और x64 के लिए समान होगा।
हम एक सरल सरणी बनाते हैं और उसमें 10 मिलियन रिकॉर्ड लोड करते हैं:

 public Entry[] Entries = new Entry[10000000]; private void btnCreate_Click(object sender, EventArgs e) { int i; for (i = 0; i < Entries.Length; i++) { Entries[i] = new Entry() {Key = i.ToString("0000000000000000")}; } GC.Collect(); var msg = string.Format("Created {0}, Memory {1}", i.ToString("0,0"), GC.GetTotalMemory(true).ToString("0,0")); lbLog.Items.Add(msg); } 

और हम देखते हैं कि हमने लगभग 760 एमबी (x32) और 1040 एमबी (x64) पर कब्जा कर लिया, अर्थात। रिकॉर्डिंग के लिए बिल्कुल 76/104 बी, जिनमें से केवल 24 उपयोगी हैं। यह पता चला है कि 100 मिलियन 7.6 / 10.4 जीबी लेंगे!

52/80 बी क्या लिया? कई बिंदु हैं: .Net वस्तुओं की संरचना और स्मृति में स्थान का संरेखण। पहले वाले से शुरू करते हैं। एक अच्छा लेख यहाँ पढ़ा जा सकता है । यह पता चला है कि वर्ग के बुनियादी ढांचे पर हम लिंक पर 8/16 बी और एक और 4/8 बी खो देते हैं (वर्ग उदाहरणों की हमारी सरणी वास्तव में उदाहरणों के संकेत की एक सरणी है)। संरचना के साथ वर्ग की जगह की जाँच करें:

 public struct Entry ... 

माप ने प्रति रिकॉर्डिंग 64/80 बी की लागत को दिखाया। सब कुछ परिवर्तित हो जाता है - हमने 12/24 बी को बचाया। संरचना वैल्यू टाइप है, इसलिए यह मान लेना तर्कसंगत है कि सरणी में अब हमारे पास लिंक नहीं हैं, लेकिन स्वयं मान हैं। यह सही है, यही कारण है कि हमने वास्तव में लिंक पर 4/8 बी बचाया है। संरचना का बुनियादी ढांचा ही कुछ नहीं लेता है। इससे पहले कि हम आगे बढ़ें और कुंजी का अनुकूलन शुरू करें, जिस पर, जाहिर है, हम बहुत कुछ खो रहे हैं, हम एक महत्वपूर्ण बिंदु पर ध्यान केंद्रित करेंगे। रिकॉर्ड को एक संरचना में स्थानांतरित करते हुए, हमने अपने लिए एक छेद खोदा - यदि हम डेटा को एक सरणी में रखते हैं, तो हमें मेमोरी के एक बहुत बड़े ब्लॉक की आवश्यकता होती है। यदि पर्याप्त मुक्त मेमोरी है, तो भी विखंडन के कारण ऐसा कोई ठोस ब्लॉक नहीं हो सकता है। व्यवहार में, मैंने 500 एमबी से अधिक की आवंटन समस्याओं का सामना करना शुरू कर दिया। हम इस समस्या को 2 समस्या में हल करेंगे। इसके अतिरिक्त, रिकॉर्ड के प्रत्येक हस्तांतरण के साथ हम अब संरचना की क्लोनिंग पर खो देंगे, और लिंक का आयोजन करते समय - पैकेजिंग / अनबॉक्सिंग (बॉक्सिंग / अनबॉक्सिंग) पर। लेकिन कहीं जाने के लिए, आपको अंतरिक्ष को बचाने की आवश्यकता है।

कुंजी फ़ील्ड के साथ जारी रखें। स्ट्रिंग प्रकार एक वर्ग है, इसलिए हम तुरंत रिकॉर्ड पर 12/24 बी खो देते हैं। वास्तव में लाइन बहुत भारी है, उदाहरण के लिए यहां पढ़ना संभव है । व्यवहार में, लंबाई 16 की स्ट्रिंग की एक सरणी बनाकर, हम लेखन के लिए कुंजी क्षेत्र 56/72 बी द्वारा कब्जे के बारे में आश्वस्त हैं। कुल:
वर्ग के लिए: 8 (दो ints) + 56/72 (कुंजी) +12/24 (कक्षा बुनियादी ढांचा + लिंक) = 76/103 बी।
संरचना के लिए: 8 (दो इंट) + 56/72 (कुंजी) = 64/80 बी।

आइए मुख्य क्षेत्र को char [] में अनुवाद करने का प्रयास करें। हम दोनों प्लेटफार्मों पर 8 बी का लाभ प्राप्त करते हैं। एक सरणी भी एक वर्ग है, इसलिए हमने बुनियादी ढांचे पर बचत नहीं की, लेकिन केवल स्ट्रिंग के आंतरिक संगठन पर, यह देखते हुए कि इसके अंदर एक चार सरणी भी संग्रहीत है। प्रत्येक चरित्र यूनिकोड है और 2 बाइट्स रखता है। इसके अलावा स्मृति संरेखण में कहीं न कहीं एक भूमिका हो सकती है। इसके बारे में बात करने का समय आ गया है।

मुझे लगता है कि बहुत से लोग जानते हैं कि एक प्लेटफ़ॉर्म-विशिष्ट सीमा के साथ मेमोरी में डेटा संरेखित करना फायदेमंद है, उदाहरण के लिए, एक इंट 32 बॉर्डर पर। आप इसके बारे में और अधिक यहाँ पढ़ सकते हैं। हमारे मामले में, हमने एंट्री क्लास / संरचना के स्थान पर कुछ भी नहीं खोया है, क्योंकि सभी क्षेत्र 4 बाइट्स की सीमा के साथ बिल्कुल झूठ बोलते हैं (याद रखें कि कुंजी एक लिंक है)। आप StructLayout विशेषता की सेटिंग्स को बदलकर और Marshal.SizeOf (नई प्रविष्टि ()) पैमाइश का उपयोग करके प्रयोग कर सकते हैं। लेकिन अगर हम int के बजाय टाइप बाइट का एक भी क्षेत्र बनाते हैं, तो यह पता चलता है कि हम सरणी पर समान मात्रा में मेमोरी पर कब्जा कर लेते हैं, भले ही हम PackL Property को StructLayout में सेट कर दें। संरचना को 1 बाइट की सीमा पर पैक किया जाएगा, लेकिन सरणी के तत्व 4 बाइट्स की सीमा पर स्थित होंगे। मुझे तुरंत कहना होगा कि मैंने पैकिंग सरणियों की समस्या को हल नहीं किया, क्योंकि समस्या के अंतिम समाधान के लिए इसकी आवश्यकता नहीं थी। इसलिए, इस विषय के साथ-साथ तार / वर्णों के विषय का भी यहाँ पूरी तरह से खुलासा नहीं किया गया है। मैं यह भी जोड़ना चाहता हूं कि स्ट्रक्चाइलआउट विशेषता के चारसेट = चारसेट.एएनएसआई का मूल्य किसी भी तरह से न तो कब्जे वाली मेमोरी के आकार को प्रभावित करता है और न ही स्ट्रिंग []।

इसलिए, फिलहाल हमने रिकॉर्डिंग पर 20/32 B बचा लिया है। क्योंकि इस कार्य में स्ट्रिंग गैर-यूनिकोड नहीं थी, यह चार [] के बजाय बाइट [] का उपयोग करने का निर्णय लिया गया था। दोनों प्लेटफार्मों पर एक और 16 बी बचाओ। एक रिकॉर्ड अब सरणी के संगठन के लिए 40/56 बी। अधिशेष - 16/32 बी लेता है। यह पता चला है कि .Net असुरक्षित मोड का उपयोग करके स्थिर स्थिर बफर को व्यवस्थित करने की क्षमता रखता है:

 private unsafe fixed byte _key[16]; 

यहां, अंत में, हम 100% तर्कसंगतता प्राप्त करते हैं - हमारा रिकॉर्ड दोनों प्लेटफार्मों पर स्मृति में बिल्कुल 24 बी लेता है। X32 पर हम लगभग 75 मिलियन (1.8 जीबी) डाउनलोड कर सकते हैं, x64 पर सभी 100 मिलियन (2.4 जीबी)। X64 पर अधिकतम संख्या अनिवार्य रूप से उपलब्ध मेमोरी के आकार द्वारा सीमित है। आप इस खुशी का उपयोग केवल असुरक्षित और फिक्स्ड ब्लॉक में कर सकते हैं। एक संदेह है कि यहां हम प्रदर्शन में हार जाएंगे, लेकिन कितना - मुझे नहीं पता, मैंने माप नहीं लिया, क्योंकि अंतिम संस्करण पूरी तरह से जरूरतों को पूरा किया।

हम धूम्रपान करते हैं और दूसरी समस्या को हल करने के लिए आगे बढ़ते हैं।

समस्या नंबर 2 का समाधान। त्वरित पहुँच।

100 मिलियन रिकॉर्ड्स तक त्वरित पहुंच के लिए, हमें हैश टेबल की तरह कुछ चाहिए। मानक हैशटेबल उपयुक्त नहीं है, क्योंकि ऑब्जेक्ट का उपयोग करता है, जिसका अर्थ है कि प्रत्येक रिकॉर्ड-संरचना को एक विशेष वर्ग (बॉक्सिंग) में रखा जाएगा और हम फिर से कक्षा के बुनियादी ढांचे पर खोना शुरू कर देंगे। हमें जेनेरिक चाहिए। एक है - डिक्शनरी <टीके, टीवील्यू>। उपयोग करने और जुदा करने के असफल प्रयास के बाद, हम निम्नलिखित पाते हैं (कोई भी व्यक्ति जो हैश तालिकाओं के सिद्धांतों से परिचित नहीं है, यहां पढ़ा जा सकता है ):

- प्रति प्रविष्टि 8 बी से अधिक:

 [StructLayout(LayoutKind.Sequential)] private struct Entry { public int hashCode; public int next; public TKey key; public TValue value; } 

हम हैशकोड और लिंक्ड सूची के संगठन (भंडारण विधि का उपयोग किया जाता है) का भंडारण खो देते हैं। यहां, वैसे, हमें दो संरचनाओं की आवश्यकता है - एक कुंजी के लिए, दूसरा मानों के लिए।

- डेटा के लिए एक सेगमेंट:

 private Entry<TKey, TValue>[] entries; 

स्मृति के एक बड़े ब्लॉक को आवंटित करने की एक तीव्र समस्या है।

- हैश खंड क्षमता से अधिक या उसके बराबर है (बहुत सारे सवाल उठते हैं):

 private void Initialize(int capacity) { … num = HashHelpers.GetPrime(capacity); this.buckets = new int[num]; … 

- भरने के दौरान, आकार दो से कम-से-कम मार्जिन के साथ होता है, हैश सेगमेंट को इस आकार में फिट करना और उसी के अनुसार रिहा करना:

 private unsafe void Resize() { … num = HashHelpers.GetPrime(this.count * 2); numArray = new int[num]; … entryArray = new Entry<TKey, TValue>[num]; … this.buckets = numArray; this.entries = entryArray; } 

मुझे लगता है कि आपको विस्तार से वर्णन नहीं करना चाहिए कि यह सब किस ओर जाता है। मिलियन वॉल्यूम में कम से कम दोहरे विकास के तर्क पर विचार करें।

इस तरह के अनुचित व्यवहार की खोज करने के बाद, मैं अब अपने देशी संग्रह में कुछ और तर्कसंगत के लिए तल्लीन करना शुरू नहीं किया, लेकिन अपना खुद का शब्दकोश लिखा। वास्तव में, सब कुछ काफी तुच्छ है, खासकर जब से मुझे 90% कार्यक्षमता की आवश्यकता नहीं है जो मानक लागू करता है। मैं कोड नहीं दूंगा, मैं केवल मुख्य बिंदुओं को इंगित करूंगा:
- कुंजी और मूल्य अलग-अलग, सभी एक प्रविष्टि संरचना में उपयोग न करें।
- प्रवेश संरचना में, GetHashCode () विधि अवरुद्ध है (और संरचना में किसी चीज को कैसे ओवरलैप किया जा सकता है!)। यहाँ से एक संशोधित FNV विधि का इस्तेमाल किया (अंजीर । 4)
- प्रवेश संरचना में, यह बराबरी (वस्तु obj) विधि को ओवरलैप करता है। तुलना केवल एक कुंजी है।
- हैश सेगमेंट का आकार कंस्ट्रक्टर में कस्टम बना दिया। इसके आकार में परिवर्तन और पुनर्वसन प्रदान नहीं किया जाता है।
- हैश सेगमेंट में सूचकांक की गणना हैश कोड को हैश सेगमेंट के आकार से विभाजित करने के शेष के रूप में की जाती है।
- प्रत्येक हैश सेगमेंट सेल एक नियमित सूची है, जो समान हैश कोड के साथ प्रविष्टियों से भरी हुई है। यह वह जगह है जहां मेमोरी के एक बड़े ब्लॉक की समस्या हल हो जाती है।

हम गणना करते हैं कि हम संगठन पर स्मृति कितना खर्च करते हैं:
- हैश खंड = सूचियों के लिए लिंक का सरणी (हैश खंड आकार * 4/8 बी);
- सूची उदाहरण = वर्ग अवसंरचना + सूची क्षेत्र (हैश खंड आकार * (8/16_1/44))।
कुल, 1 मिलियन के सेगमेंट के संगठन के लिए, हम लगभग 40/68 एमबी खर्च करेंगे।

सब कुछ बहुत अच्छा होगा और शैंपेन पीने का समय होगा। लेकिन वहाँ यह था। यह पता चला है कि सूची:

- जैसे मानक शब्दकोश दोहरीकरण के साथ बढ़ता है:

 private void EnsureCapacity(int min) { … num = (((int) this._items.Length) == null) ? 4 : (((int) this._items.Length) * 2); … 

- अत्यधिक कब्जे वाली स्मृति को मुक्त करने के लिए फ़ंक्शन 0.1 वॉल्यूम मुक्त नहीं करता है:

 public void TrimExcess() { int num; num = (int) (((double) ((int) this._items.Length)) * 0.9); if (this._size >= num) { goto Label_002A; } this.Capacity = this._size; Label_002A: return; } 

- ठीक है, परिशिष्ट में यह (हमारे उद्देश्यों के लिए) क्षेत्रों द्वारा और एक वर्ग क्या है द्वारा निरर्थक है:

 public class List... { private const int _defaultCapacity = 4; private static T[] _emptyArray; private T[] _items; private int _size; [NonSerialized] private object _syncRoot; private int _version; ... 

मुझे अपनी सूची लिखनी थी, कस्टम लीनियर ग्रोथ के साथ, मेमोरी को पूरी तरह से मुक्त करना और _syncRoot और _version फ़ील्ड्स में 8 B की बचत करना। आप इसे 12 B को सहेजते हुए, संरचना में भी स्थानांतरित कर सकते हैं।

सब कुछ, समस्या हल हो गई है - हम शैंपेन पीते हैं!

और थोड़ा अभ्यास

पीसी कोर 2 क्वाड Q9400 @ 2.66, रैम 4 जीबी, विंडोज सर्वर 2008 आर 2 स्टैंडर्ड x64

हैश खंड 1 मिलियन, सूची विकास 25।
100 मिलीलीटर भरना। 5 मिनट 50 सेकंड। मेमोरी 2.46 जीबी, चोटी 3.36 जीबी।
सांख्यिकी: 100% भरण, न्यूनतम 56 श्रृंखला, अधिकतम 152, मानक विचलन 10।
बाह्य 100 मिलियन 4 मिनट 10 सेकंड के साथ स्मृति में 100 मिलियन की तुलना।

हैश खंड 2 मिलियन, सूची विकास 20।
100 मिलीलीटर भरना। 4 मिनट 43 सेकंड। मेमोरी 2.53 जीबी, चोटी 3.57 जीबी।
सांख्यिकी: 100% भरने, न्यूनतम श्रृंखला 20, अधिकतम 89, मानक विचलन 7।
बाह्य 100 मिलियन 2 मिनट 56 सेकंड के साथ स्मृति में 100 मिलियन की तुलना।

एक छोटी टिप्पणी: .Net स्मृति को तुरंत मुक्त नहीं करता है, भले ही हमने बड़ी संख्या में वस्तुओं को मुक्त किया हो। कचरा संग्रहण के बाद ऐसा नहीं हो सकता है। मेमोरी भविष्य में उपयोग के लिए आरक्षित रहती है और सिस्टम में मेमोरी की तीव्र कमी (संभवत: कुछ अन्य मानदंडों द्वारा) होने पर मुक्त हो जाती है।

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