🎦 🏟️ 🛌🏾 C ++ में एक प्रोग्राम के रनटाइम का अनुकूलन (सशर्त संक्रमण हटाएं) ☎️ 🍉 🐘

एलडीपीसी डिकोडर का उपयोग करके एल्गोरिथ्म के निष्पादन समय का अनुकूलन करते समय, प्रोफाइलर एक फ़ंक्शन का नेतृत्व करता है जो निम्न मान की गणना करता है:

जहां और बी पूर्णांक हैं। कॉल की संख्या लाखों में चली गई, और इसका कार्यान्वयन पर्याप्त था सरल और अपरिष्कृत:

int LLR(int a, int b) { if (a>0) return (b>0) ? __min(a,b) : -__min(a,-b); else return (b>0) ? -__min(-a,b) : __min(-a,-b); }

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

परीक्षण परियोजना

 #include <Windows.h> static inline int LLR(int a, int b) { if (a>0) return (b>0) ? __min(a,b) : -__min(a,-b); else return (b>0) ? -__min(-a,b) : __min(-a,-b); } int _tmain(int argc, _TCHAR* argv[]) { SetPriorityClass(GetCurrentProcess(),REALTIME_PRIORITY_CLASS); SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_TIME_CRITICAL); srand(0); int x(0); __int64 t1,t2; QueryPerformanceCounter((LARGE_INTEGER*)&t1); for (size_t i=0;i<MAXUINT>>4;i++) { int a = rand() - RAND_MAX / 2; int b = rand() - RAND_MAX / 2; /* x += LLR(a,b);*/ } QueryPerformanceCounter((LARGE_INTEGER*)&t2); t2 -= t1; QueryPerformanceFrequency((LARGE_INTEGER*)&t1); _tprintf_s(_T("%f"),t2/(t1*1.)); return 0; }

X86 प्लेटफॉर्म के लिए रिलीज़ कॉन्फ़िगरेशन (डिफ़ॉल्ट सेटिंग्स) में MSVS 2008 में असेंबली का प्रदर्शन किया गया था।

शुरू करने के लिए, हम यादृच्छिक संख्याओं की पीढ़ी के साथ चक्र के निष्पादन समय का अनुमान लगाने के लिए गणना फ़ंक्शन को कॉल करते हैं (दुर्भाग्य से, QueryPerformanceCounter () के लिए कॉल स्वयं ही धीमी है और यदि यह चक्र के अंदर किया जाता है तो परिणाम की एक महत्वपूर्ण विकृति की ओर जाता है)। हम यह सुनिश्चित करने के लिए प्रोजेक्ट को कई बार लॉन्च करते हैं कि परिणाम दोहराने योग्य है। 3.4 गीगाहर्ट्ज़ की आवृत्ति के साथ इंटेल कोर i7-3770 प्रोसेसर वाली मशीन पर, औसत रनटाइम 9.2 सेकंड है। यदि आप गणना फ़ंक्शन को कॉल को अनसुना करते हैं, तो परियोजना का पुनर्निर्माण करें और प्रयोग को दोहराएं, हमें लगभग 11.5 सेकंड मिलते हैं। निष्पादन समय में वृद्धि स्पष्ट है, और हम इसके साथ लड़ेंगे।

चलो सशर्त बयानों से छुटकारा पाने की कोशिश करते हैं। सबसे पहले, उत्पाद ए और बी के संकेत का पता लगाएं। संभावित अतिप्रवाह के कारण माथे में इसकी गणना करना गलत है। चूंकि केवल संकेत हमारे लिए महत्वपूर्ण है (अर्थात, पूर्णांक के संकेत अंक के बिट का मूल्य), उत्पाद का संकेत ए और बी निर्धारित करने के लिए एक्सर ऑपरेशन का उपयोग करना उचित है। इसके बाद, परिणाम को एक x b b को 31 बिट्स (केवल एक हस्ताक्षरित अंक छोड़कर) में स्थानांतरित करें और एक ऋणात्मक संख्या के मामले में 0 प्राप्त करें और 1 नकारात्मक के मामले में। इस मान को दो से गुणा करें, एकता से घटाएं और नकारात्मक संख्या के लिए -1 और गैर-नकारात्मक के लिए 1 प्राप्त करें:

 int sign = 1-2*((unsigned)a^b)>>31);

अब हम मॉड्यूल की गणना करते हैं a और b । एक समान विधि से, हम संकेत गुणांक a और b निर्धारित करते हैं और उनके द्वारा गुणा करते हैं:

 int c; c = 1-2*(((unsigned)a)>>31); a *= c; c = 1-2*(((unsigned)b)>>31); b *= c;

हम न्यूनतम की गणना के लिए आगे बढ़ते हैं। चूंकि ए और बी में पहले से ही गैर-नकारात्मक मूल्य हैं, इसलिए न्यूनतम की गणना उनके अंतर के संकेत के आधार पर की जा सकती है:

 int numbers[2], min; numbers[0] = b; numbers[1] = a; a -= b; c = (unsigned(a))>>31; min = numbers[c];

यह सब एक साथ रखना और प्राप्त करना

अगला कार्य

 static inline int LLR_2(int a, int b) { int sign, numbers[2]; sign = 1-2*(((unsigned)a^b)>>31); a *= 1-2*(((unsigned)a)>>31); b *= 1-2*(((unsigned)b)>>31); numbers[0] = b; numbers[1] = a; a -= b; return sign*numbers[((unsigned)a)>>31]; }

LLR_2 के साथ LLR () कॉल बदलें और देखें कि क्या होता है। अब कोडांतरक कोड में एक भी सशर्त कूद नहीं है, लेकिन पूर्णांक गुणन imul के लिए तीन निर्देश हैं (गुणक 2 से कंपाइलर खुद एक बदलाव के साथ बदलता है)। परीक्षण कार्यक्रम चलाने के बाद, हमें निम्नलिखित परिणाम मिलते हैं - निष्पादन का समय 9.4 सेकंड है! कुल में, वांछित मूल्य की गणना के लिए दो विकल्पों के लिए क्रमशः "शुद्ध" समय (2.1 और 0.2 सेकंड) की तुलना करते हुए, हम आवश्यक ऑपरेशन की गति में दस गुना ^* वृद्धि प्राप्त करते हैं।

चलिए थोड़ा और आगे जाने की कोशिश करते हैं। पूर्णांक संख्या के संकेत को उलटने के लिए पूर्णांक गुणा आवश्यक है, जिसे सीधे किया जा सकता है। विशेष रूप से, कैन के मापांक की गणना निम्नानुसार लागू की जा सकती है:

 unsigned int mask[] = {0,(unsigned)-1}; unsigned int constant[] = {0, 1}; int c = ((unsigned)a)>>31; a = a^mask[c]+constant[c];

अंत में, हम दाएं बदलाव को _rotl () फ़ंक्शन का उपयोग करते हुए एक एकल चक्रीय बाईं पारी के साथ 31 बिट्स द्वारा प्रतिस्थापित करते हैं। आगे देखते हुए, हम ध्यान दें कि कंपाइलर कॉल का उपयोग किए बिना सीधे अपने कॉल को एक रोएल स्टेटमेंट में बदल देता है। यह सब फिर से एक साथ लाना और प्राप्त करना

तीसरा विकल्प

 static unsigned int mask[] = {0,(unsigned)-1}; static unsigned int constant[] = {0, 1}; static inline int LLR_3(int a, int b) { int sign,c, numbers[2]; sign = (_rotl(a^b,1) & 1); c = ((_rotl(a,1) & 1)); a = (a^mask[c])+constant[c]; c = ((_rotl(b,1) & 1)); b = (b^mask[c])+constant[c]; numbers[0] = b; numbers[1] = a; c = ((_rotl(ab,1) & 1)); return (numbers[c]^mask[sign])+constant[sign]; }

हम LLR_3 () के साथ LLR () _ 2 कॉल को प्रतिस्थापित करते हैं और देखते हैं कि यह एक महत्वपूर्ण वृद्धि नहीं देता है (रनटाइम लगभग 9.4 सेकंड में एक छोटे से दिशा में थोड़ा अंतर के साथ है)। यह पता चला है कि इमुल आधुनिक प्रोसेसर पर बहुत तेज है!

आइए उस एल्गोरिदम पर वापस जाएं जिसने यह सब शुरू किया था। केवल एक फ़ंक्शन का वर्णित अनुकूलन एकल डेटा ब्लॉक के प्रसंस्करण समय को 160 से 140 सेकंड (जब i7 पर निष्पादित किया जाता है) को कम करने में कामयाब रहा, जो 10% से अधिक है और एक बहुत अच्छा परिणाम है। आगे कुछ और ऐसी ही विशेषताएं हैं ...

और अंत में, मैं अधिकतम दो पूर्णांक 32-बिट संख्या निर्धारित करने के लिए एक कार्यान्वयन विकल्प प्रस्तावित करता हूं। यह विशुद्ध रूप से अकादमिक जिज्ञासा से बाहर लिखा गया था। रुचि रखने वाले बिगाड़ने वाले के नीचे देखने के लिए जल्दी नहीं कर सकते हैं और इसे स्वयं लागू करने का प्रयास कर सकते हैं। सशर्त कूद के बिना विकल्प मानक __max () मैक्रो (जब i7 पर निष्पादित ) की तुलना में लगभग तीन गुना तेजी से काम करता है। अपने कार्यक्रमों का अनुकूलन सौभाग्य!

छिपा हुआ पाठ

 static inline int max(int a, int b) { int numbers[2][2]; numbers[0][0] = b; numbers[0][1] = a; numbers[1][0] = a; numbers[1][1] = b; int sign_a = (unsigned)a>>31; int sign_b = (unsigned)b>>31; int sign_ab = (unsigned)(a^b)>>31; int abs_a = (1-2*sign_a)*a; int abs_b = (1-2*sign_b)*b; int sign_a_b = (unsigned)(abs_a-abs_b)>>31; int c0 = sign_ab; int c1 = ((1^(sign_a_b)^(sign_a | sign_b)) & (1^c0)) | (sign_ab & sign_a); int result = numbers[c0][c1]; return result; }

* यूपीडी। टिप्पणियों में, उपयोगकर्ता शोडान ने एक उदाहरण दिया जिसमें रैंड () को समय की गिनती से हटा दिया गया था और डेटा को पूर्व-निर्मित सरणी से पढ़ा गया था। इस मामले में, प्रदर्शन में वृद्धि लगभग तीन गुना है। जाहिरा तौर पर, यह सरणी से डेटा पढ़ते समय कन्वेयर के अधिक कुशल संचालन के कारण है।

C ++ में एक प्रोग्राम के रनटाइम का अनुकूलन (सशर्त संक्रमण हटाएं)

More articles: