कोड निष्पादन की गति अनुकूलन

यह लेख इस बारे में है कि कैसे शास्त्रीय एल्गोरिदम हमारे कोड को तेज बनाते हैं। हम एक शून्य बिट की खोज के लिए एल्गोरिथ्म पर विचार करेंगे और यह एक सीमा से चरित्र खोजने के लिए एल्गोरिथ्म की दक्षता बढ़ाने में हमारी मदद कैसे कर सकता है (उदाहरण के लिए, एक स्ट्रिंग में 0-9 की सीमा से एक चरित्र की पहली घटना का पता लगाएं)।
यानी पाठ को संसाधित करते समय वैक्यूम में एक गोलाकार घोड़ा एक काफी सामान्य स्थिति है, जब एक मनमाना पाठ में पहले अंक की स्थिति को खोजने के लिए आवश्यक है। इस तरह से कई लोग नियमित अभिव्यक्ति सीखना शुरू करते हैं।
लेख gcc के उपयोग का वर्णन करता है। यदि वांछित है, तो छोटे परिवर्तन के साथ अन्य संकलक और भाषाओं के लिए सब कुछ दोहराया जा सकता है। सावधानी, कट के नीचे एक कोडांतरक है!

इस समस्या को हल करने के लिए, हम निम्नलिखित तरीकों का उपयोग कर सकते हैं:
1) नियमित अभिव्यक्ति पुस्तकालय का उपयोग करें।
2) अपने लिए खोज करने के लिए एक फ़ंक्शन लिखें।
यदि लाइनें छोटी हैं, तो अनुकूलन का सवाल ही नहीं उठता। यह कार्य दिलचस्प हो जाता है जब लाइनों की लंबाई बढ़ जाती है, या बड़ी संख्या में चेक लगते हैं।
हम घड़ी () फ़ंक्शन का उपयोग करके निष्पादन समय को <time.h> फ़ाइल से शामिल करेंगे।

हम REGEX का उपयोग करते हैं

नियमित अभिव्यक्ति का उपयोग करते हुए एक विधि पर विचार करें। दिमाग में आने वाली पहली विधियों में से एक REGEX लाइब्रेरी का उपयोग करना है। नियमित अभिव्यक्ति इस तरह दिखाई देगी:
"[[: अंक:]]"
इस पुस्तकालय का उपयोग करने के लिए कोड हो सकता है:

clock_t tbefore; long i; double eplased; int pmatch[1]; regex_t regex; int reti; …. /*REGEXP usage*/ tbefore = clock(); reti = regcomp( & regex, "[[:digit:]]", 0); for (i=1;i<100000;i++){ reti = regexec(& regex, test_string, 1, pmatch, 0); } eplased=clock()-tbefore; printf("Function strchr used %.3f seconds %d\n", eplased/CLOCKS_PER_SEC, pmatch[0]); regfree( & regex); /**************/ 

निष्पादन की गति: 1.74 सेकंड।
इस कोड में, मैंने जानबूझकर संकलन और खोज की सफलता पर चेक हटा दिए हैं, अर्थात, वास्तविक समस्याओं को हल करने के लिए इस कोड का उपयोग करना असंभव है। लेकिन "ग्रीनहाउस" स्थितियों में गति की जांच करने के लिए - यही है। इसके अलावा, मैं एक रेगुलर एक्सप्रेशन का संकलन करके और इसे इस्तेमाल करने के बाद मेमोरी को फ्री करके रनटाइम मापता हूं।

कस्टम खोज समारोह

आइए पारंपरिक दृष्टिकोण - माथे का उपयोग करने का प्रयास करें। खोज समारोह
इस तरह दिखेगा ( एलगोरिदम 1 ):

 int search1(char *str){ int l=0; int i; l = strlen(str); for (i=0;i<l;i++){ if ((str[i] >= '0') && (str[i] <= '9')){ return (i); } } return (-1); } 

निष्पादन की गति: 7.19 सेकंड।
और माप परिणाम चार से अधिक बार कम निष्पादन गति दिखाते हैं! जिसकी उम्मीद की जानी है।

अनुकूलित एल्गोरिथ्म

चलो अनुकूलन करने की कोशिश करते हैं। एक बार मैं जी वॉरेन की किताब "अल्गोरिथमिक ट्रिक्स फॉर प्रोग्रामर्स" पर आया था। और इस पुस्तक में एक स्ट्रिंग में अशक्त चरित्र को खोजने के लिए एल्गोरिदम का वर्णन था। इन एल्गोरिदम का उपयोग किया जाता है, उदाहरण के लिए, सी में एक पंक्ति का अंत खोजने के लिए। इसके अलावा, एक पैराग्राफ में, श्रेणी विवरण के लिए इन एल्गोरिदम में से एक का सामान्यीकरण प्रस्तावित है।
एल्गोरिथ्म का विचार यह है कि एक स्ट्रिंग में एक वर्ण के सूचकांक को खोजने के लिए एक वर्ण पर एक से अधिक नहीं, लेकिन एक समय में चार, सरणी से दोहरा शब्द पढ़ना (डॉर्ड = 4 बाइट)। यानी C के संदर्भ में, हमने चरित्र सरणी (char) से बिना पढ़े हुए लंबे पूर्णांक को पढ़ा।
इसके बाद, शब्द के साथ अंकगणितीय संचालन किए जाते हैं। शून्य से नौ तक की सीमा के लिए, यह इस तरह दिखता है:

 int zbytel3(unsigned z) { unsigned y; x = z ^ 0x30303030; // Original byte: 00 80 other y = (x & 0x7F7F7F7F) + 0x76767676; // 7F 7F 1xxxxxxx y = ~(y | x | 0x7F7F7F7F); // 80 00 00000000 // These steps map: if (y == 0) return 4; // 00000000 ==> 4, else if (y > 0x0000FFFF) // 80xxxxxx ==> 0, return (y >> 31) ^ 1; // 0080xxxx ==> 1, else // 000080xx ==> 2, return (y >> 15) ^ 3; // 00000080 ==> 3. } 

वह है, x = z ^ 0x30303030 - एक विशेष ऑपरेशन या जो कि रेंज की न्यूनतम संख्या "0" - 0x30 से 0. 0x76 = 0x7F-9 है, जहां 9 = n-1 है, जहां n श्रेणी में वर्णों की संख्या है।
अगला, सरल बाइट अंकगणित, जिसके परिणामस्वरूप आप एक संख्या प्राप्त कर सकते हैं जिसे शाखा में संसाधित किया जाता है, और इसके परिणामस्वरूप हमें 1 से 4. तक नंबर मिलते हैं। यदि प्रतीक नहीं मिलता है, तो 4।
अब हमारा कार्य निम्नलिखित रूप लेगा:

 int search2( char *str){ int n, j = 0; unsigned x, y, *r; const char *c_ptr; //   ,   . for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr) if ((*c_ptr >= '0') && (*c_ptr <= '9')) return c_ptr - str; r = (unsigned *) c_ptr; j = c_ptr - str ; while (1){ x = *r ^ 0x30303030; y = (x & 0x7F7F7F7F) + 0x76767676; y = ~(y | x | 0x7F7F7F7F); // These steps map: if (y == 0) n = 4; // 00000000 ==> 4, else if (y > 0x0000FFFF) // 80xxxxxx ==> 0, n= (y >> 31) ^ 1; // 0080xxxx ==> 1, else // 000080xx ==> 2, n= (y >> 15) ^ 3; // 00000080 ==> 3. j=j+n ; if (n<4) {j =j +3 -2*n; break;} r++; } return (j); } 

निष्पादन की गति: 1.71 सेकंड।
माप परिणाम regexp के करीब गति दिखाते हैं। क्या हम इसे तेजी से कर सकते हैं? हाँ!
हम कोडांतरक आवेषण का उपयोग करते हैं। वर्णित पद्धति की ताकत यह है कि यह आपको घड़ी चक्र की संख्या को कम करने की अनुमति देता है जो प्रोसेसर प्राथमिक अंकगणितीय संचालन के उपयोग के माध्यम से निष्पादन पर खर्च करता है। एक उच्च-स्तरीय भाषा में प्रोग्रामिंग हमें पूरी तरह से इस एल्गोरिथ्म की क्षमताओं का एहसास करने की अनुमति नहीं देता है।
और इसलिए, अब हमारा कार्य निम्नलिखित रूप लेगा:

 int search3( char *str){ int n, j = 0; unsigned x, y, *r; const char *c_ptr; for (c_ptr=str; ((unsigned long int)c_ptr & (sizeof(x) - 1)) != 0; ++c_ptr) if ((*c_ptr >= '0') && (*c_ptr <= '9')) return c_ptr - str; r = (unsigned *) c_ptr; j = c_ptr - str ; while (1){ __asm__( "movl $5, %%edx\n" "movl (%%ebx), %%eax\n" "xor $0x30303030, %%eax\n" // "and $0x7F7F7F7F, %%eax\n" "add $0x76767676, %%eax\n" "movl %%eax, %%ecx\n" "or %%eax, %%ecx\n" "or $0x7F7F7F7F, %%ecx\n" "notl %%ecx\n" :"=c"(y) :"b"( r ) ); // These steps map: if (y == 0) n = 4; // 00000000 ==> 4, else if (y > 0x0000FFFF) // 80xxxxxx ==> 0, n= (y >> 31) ^ 1; // 0080xxxx ==> 1, else // 000080xx ==> 2, n= (y >> 15) ^ 3; // 00000080 ==> 3. j=j+n ; if (n<4) {j =j +3 -2*n; break;} r++; } return (j); } 

निष्पादन की गति: 1.23 सेकंड।
मैंने असेंबली असेंबली की जगह केवल अंकगणितीय ऑपरेशन किए। ब्रांचिंग को कोडांतरक कोड के साथ भी बदला जा सकता है, लेकिन मैं एक महत्वपूर्ण लाभ के बारे में सुनिश्चित नहीं हूं, लेकिन लेबल के साथ कई ब्रांचिंग डिबगिंग प्रक्रिया को बहुत जटिल कर देगा।
लाभ मौजूद है, लेकिन रेगेक्स की तुलना में कई बार नहीं। सिद्धांत रूप में, असेंबली भाषा के आवेषण के साथ अनुकूलन करना आप अभी भी कोड में सुधार कर सकते हैं, लेकिन यह सब डिबगिंग प्रक्रिया की जटिलता को दर्शाता है। यदि आप ब्रांचिंग और लूप का अनुकूलन करते हैं, तो आप गति में डेढ़ गुना वृद्धि प्राप्त कर सकते हैं। लेकिन कोड डीबग करना अधिक कठिन होगा। आप 32 के बजाय 64 बिट्स के लिए इस एल्गोरिथ्म को भी ऑप्टिमाइज़ कर सकते हैं, प्रक्रिया को समानांतर करने की कोशिश कर सकते हैं।

कुल हमें मिलता है:

regex	1.74
एल्गोरिथम 1	7.19
एल्गोरिथम 2	1.71
एल्गोरिथम 2 + asm	1.23

निष्कर्ष खुद ही पता चलता है: साइकिल का आविष्कार स्वागत योग्य नहीं है, और हमेशा विधानसभा अनुकूलन से लाभ इतना महत्वपूर्ण नहीं हो सकता है।

स्रोत संग्रह से लिंक करें:
webfile.ru/5706721

युपीडी:
प्रोसेसर आर्किटेक्चर के लिए अनुकूलन का संकेत दिया गया है, मैं -O 2 पैरामीटर जोड़ता हूं।
मैं किसी तरह से परिणाम का उपयोग करने के लिए परीक्षण कार्यों के अंदर भी जोड़ देता हूं।
परिणाम:

regex	4.56
एल्गोरिथम 1	2.99
एल्गोरिथम 2	1
एल्गोरिथम 2 + asm	1.7 *

* -O2 स्विच के साथ सही ढंग से काम करना बंद कर दिया, __volatile_ ने मदद नहीं की, -O1 स्विच के साथ लेकिन जोड़ योग के साथ परिणाम।

UPD 2:

Maratyszcza उपयोगकर्ता (उसके लिए धन्यवाद!) ने SIMD एक्सटेंशन का उपयोग करके एक और भी तेज विकल्प की पेशकश की ।

 #include <intrin.h> const char* find_digit(const char* str) { static const __m128i str_mask[16] = { _mm_set_epi32(0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00FFFFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x0000FFFF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x000000FF, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x00FFFFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x0000FFFF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x000000FF, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x00FFFFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x0000FFFF), _mm_set_epi32(0x00000000, 0x00000000, 0x00000000, 0x000000FF) }; static const __m128i str_offset = _mm_set1_epi8(127 - '9'); static const __m128i str_threshold = _mm_set1_epi8(127 - 10); const size_t str_misalignment = ((size_t)str) & ((size_t)15); const __m128i* str_aligned = (const __m128i*)(((size_t)str) - str_misalignment); __m128i str_vector = _mm_load_si128(str_aligned); str_vector = _mm_and_si128(str_vector, str_mask[str_misalignment]); str_vector = _mm_add_epi8(str_vector, str_offset); int str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold)); unsigned long index; _BitScanForward(&index, str_bitmask); while (str_bitmask == 0) { str_aligned += 1; str_vector = _mm_load_si128(str_aligned); str_vector = _mm_add_epi8(str_vector, str_offset); str_bitmask = _mm_movemask_epi8(_mm_cmpgt_epi8(str_vector, str_threshold)); _BitScanForward(&index, str_bitmask); } return ((const char*)str_aligned) + index; } 

यह अब तक का सबसे तेज विकल्प है।