मैं डेटाबेस में रैखिक खोज के संदर्भ में C ++ में संयोजन कोड पीढ़ी के बारे में लेख पढ़ता हूं:
C और C ++ में अनुकूलन क्षमता और
विकास और निष्पादन की गति C में प्राप्त नहीं होती है । आइए C में विकास और निष्पादन गति प्राप्त करने का प्रयास करें?
जब मैंने दूसरे लेख से C ++ कोड संकलित करना शुरू किया, तो मुझे आश्चर्य हुआ कि क्या मैं C में एक एनालॉग लिख सकता हूं जो कोड ... तेजी से संकलित होने पर काम करेगा? मेरे पास समय नहीं था, कोड 5 मिनट के बाद संकलित किया गया था, और सी के अनुरूप सभी 15 लिखा गया था।
तो, समस्या का विवरण - कई क्षेत्रों की एक संरचना है, एक फिल्टर है जो यह जांचता है कि प्रत्येक क्षेत्र निर्दिष्ट सीमा में है या नहीं। या जाँच नहीं करता है - प्रत्येक क्षेत्र के लिए। हमें कोड की आवश्यकता है जो एक निश्चित फ़िल्टर पर यह जांच बहुत जल्दी करता है। डेटा यादृच्छिक है, इसलिए कम सशर्त संक्रमण बेहतर है - यादृच्छिक डेटा पर संक्रमण की भविष्यवाणी इतनी-इतनी काम करती है।
समस्या को दो चरणों में हल किया जाता है:
1. आइए तुलनात्मक कार्यों को कुछ सरल के साथ बदलना सीखें, उदाहरण के लिए और बिटवाइज़ संचालन
2. आइए जानें कि 1 से कई ऑपरेशन को एक साथ कैसे जोड़ा जाए, मुफ्त में।
तो, पहला बिंदु। बी का एक मान है और [ए, सी] की एक सीमा है, हमें एक <= बी और बी <= सी की गणना करने की आवश्यकता है। कोई तुलना नहीं। निश्चितता के लिए, a, b, c को गैर-ऋणात्मक मानें और 7 बिट्स में डालें - i.e. 0 से 127 तक।
यह देखना आसान है कि अभिव्यक्ति (128 - ए) + बी 8 बिट्स में फिट होने की गारंटी है; इसके अलावा, परिणाम का 8 वां बिट 1 है और केवल अगर एक <= b। उदाहरण के लिए, यदि a = 0, तो अभिव्यक्ति के मूल्य में 128 + b 8 वीं बिट हमेशा 1 है; यदि a = 1 है, तो अभिव्यक्ति के मूल्य में 127 + b 8 वीं बिट 1 है यदि b 0 या 1 है, और इसी तरह।
B और c की तुलना करने का परिणाम बहुत ही समान तरीके से प्राप्त होता है - अभिव्यक्ति (127 - c) + b को 8 बिट्स में रखा गया है, और परिणाम का 8 वां बिट 0 है यदि और केवल यदि b <= c है।
तो जयकार! एक <= b की गिनती करने के बजाय, हम ((128 - a) + b) और 128 की गणना करेंगे। ऐसा प्रतीत होगा, क्यों ..?
बिंदु दो। बिट ऑपरेशंस की एक अद्भुत संपत्ति होती है जिसे हर कोई जानता है - एक निर्देश के साथ, आप एक ही समय में एक ही प्रकार के बिट ऑपरेशन कर सकते हैं। ऐसा लगता है कि वर्ष 2013 पहले से ही है, आपने आग के साथ दिन के दौरान एसएसई के बिना एक प्रोसेसर भी नहीं पाया है, इसलिए हम यह मान लेंगे कि यह 64 बिट्स है - आप निश्चित रूप से कर सकते हैं।
हर कोई नहीं जानता कि अंकगणितीय ऑपरेशनों में एक समान उत्कृष्ट संपत्ति होती है - यदि आप सावधान रहें और डेटा को पूर्व-तैयार करें। उदाहरण के लिए, मान लें कि हमारे पास 32-बिट अंकगणित है, और सात-बिट अहस्ताक्षरित संख्याओं के 4 जोड़े हैं। देखें कि उन्हें कैसे मोड़ा जा सकता है:
1. प्रत्येक संख्या में एक अतिरिक्त उच्च-क्रम बिट जोड़ें, जो शून्य से आरंभीकृत है:
आआआआआआ -> 0 आआआआआआआआआ
2. 8 बिट के 4 समूह क्रमिक रूप से लिखे गए हैं:
0aaaaaaa0bbbbbbb0ccccccc0ddddddd
3. दो परिणामी 32-बिट संख्याएं जोड़ें; हमें 32-बिट संख्या में 4 8-बिट अतिरिक्त परिणाम मिलते हैं।
4. यदि आप 7-बिट अंकगणित चाहते हैं, तो ट्रांसफर बिट्स को रीसेट किया जा सकता है।
यह तुरंत स्पष्ट हो जाता है कि वांछित कार्य में क्या करने की आवश्यकता है:
1. हमने डेटा को 64-बिट रजिस्टर में रखा है ताकि प्रत्येक मूल्य में एक अतिरिक्त उच्च बिट हो। यह संयोग से हुआ कि लेख से उदाहरण 62 बिट्स की ऐसी पैकिंग के साथ टूट गया - एक एकल-बिट क्षेत्र के लिए अभी भी जगह है!
struct T_cash_account_row { unsigned reserved0:1; unsigned code:20; // 0 - 1000000 unsigned carry_code:1; unsigned gender:1; // 0 - 1 unsigned carry_gender:1; unsigned age:7; // 0 - 100 unsigned carry_age:1; unsigned reserved1:1; unsigned amount_of_money:20;// 0 - 1000000 unsigned carry_amount_of_money:1; unsigned height:9; // 0 – 300 unsigned carry_height:1; };
ध्यान दें, यहाँ हम एक विशेष संकलक में बिट फ़ील्ड बिछाने के क्रम के ज्ञान का उपयोग करते हैं; वास्तव में, आपको संरचना को लंबे समय तक अप्रयुक्त के साथ बदलने और बिट संचालन के माध्यम से मूल्यों को वहां रखने की आवश्यकता है, लेकिन इसके लिए आपको संदर्भ कोड बदलना होगा। कोड थोड़ा कम क्रॉस-प्लेटफ़ॉर्म बन गया है जितना कि यह था, इसका इलाज किया जा रहा है।
2. हम उपरोक्त उदाहरण से (128 - ए) और (128 - 1 - सी) जैसे नंबरों से अग्रिम में दो शब्द उत्पन्न करते हैं। 128 के बजाय हम बिट्स में प्रत्येक क्षेत्र की चौड़ाई को प्रतिस्थापित करते हैं। पागल न होने के लिए, हम मैक्रोज़ का उपयोग करते हैं।
#define FILL(enum, field, bits) \ if (range_filters->use_filter[enum]) { \ begin_add.field = (1 << bits) - range_filters->begin.field; \ begin_add.carry_##field = range_filters->begin.field == 0; \ end_add.field = (1 << bits) - 1 - range_filters->end.field; \ mask_add.carry_##field = 1; \ }
मैं शुरू करने के लिए carry_field भरने पर ध्यान आकर्षित करता हूं - अतिरिक्त बिना अंकगणित के साथ बिट फ़ील्ड का संचालन करते हैं। विस्तारित बिट, इसलिए यदि = 0 शुरू होता है, तो आपको फ़ील्ड को शून्य से भरने की आवश्यकता है, और एक के साथ carry_field। यदि आप बिट फ़ील्ड के बजाय अहस्ताक्षरित लंबे और बिट संचालन का उपयोग करते हैं, तो आप बस (1 << बिट्स) लिख सकते हैं - शुरू करें।
3. 64-बिट संख्या को जोड़ें जिसमें हमारे क्षेत्र दो नियंत्रण शर्तों के साथ ढेर हो गए हैं; हमें हस्तांतरण बिट्स में आवश्यक जानकारी मिलती है
unsigned long long value = *(unsigned long long*)&array_ptr[i]; unsigned long long begin_result = (value + begin_add_i) ^ mask_add_i; unsigned long long end_result = value + end_add_i;
इस कोड के टुकड़े में, हमने दुर्भावनापूर्वक सख्त अलियासिंग का उल्लंघन किया (और इसके साथ नरक करने के लिए), और 0 के साथ कैरी बिट्स में 1 को भी बदल दिया।
4. जाँच करें कि हम जिन कैरी बिट्स में रुचि रखते हैं (जिन्हें फ़िल्टर द्वारा माना जाना चाहिए) पहले जोड़ के बाद 1 हैं और दूसरे के बाद 0 हैं।
if (((begin_result | end_result) & mask_add_i) == 0)
चूँकि हमने 1 को 0 से बदल दिया है, इसलिए यह जाँचना पर्याप्त है कि हम जिस भी बिट में रुचि रखते हैं, वह शून्य के बराबर है।
5. हम प्रदर्शन को मापते हैं, हमें C ++ कोड की तुलना में लगभग 2 गुना की वृद्धि मिलती है, जिसे संकलन में 5 मिनट लगते हैं।
Microsoft (R) C/C++ Optimizing Compiler Version 17.00.50727.1 for x64 Generated rows: 100000000 C-search took 0.778000 seconds. C++-optimized search took 0.307000 seconds. C-optimized-search took 0.171000 seconds.
और सिर्फ मामले में,
पूरे कोड । यह MSVC में / TP स्विच के साथ संकलित करता है (क्योंकि यह C89 नहीं है, न तो मेरे परिवर्तनों से पहले, न ही बाद में), और gcc में स्विच (यादृच्छिक) के बिना।
बेशक,
आप उस तरह के प्रदर्शन को माप नहीं सकते ।
बेशक, मैं 62 बिट्स के साथ भाग्यशाली था (और मूल लेख के लेखक 4000 विकल्पों के साथ भाग्यशाली थे)।
लेकिन हर किसी को अपने लिए निष्कर्ष निकालना चाहिए।
अंत में, मैं यह नोट करना चाहता हूं कि - ऐसा लगता है - उत्पादन के लिए वास्तविक समाधान सोआ डेटा स्टैकिंग का उपयोग करेगा - संरचनाओं की एक सरणी का उपयोग करने के बजाय, प्रत्येक क्षेत्र के लिए एक सरणी का उपयोग करें (उदाहरण के लिए, बिटमैप पैकेजिंग)। फिर, सबसे पहले, आप रैखिक स्कैन द्वारा पढ़े गए डेटा की मात्रा को बचा सकते हैं, दूसरे, आपको संकलन-समय के कॉम्बिनेटरिक्स की आवश्यकता नहीं है, तीसरा, कम कोड लिखें, चौथा, फ़ील्ड की संख्या और क्वेरी संरचना को गतिशील रूप से बदलना आसान है। बेशक, वास्तविक उत्पादन समाधान (ओह, हॉरर) प्लेटफॉर्म-विशिष्ट SIMD का उपयोग करेगा।