दिलचस्प पोस्ट
मैं एंड्रॉइड में छवि बटन पर पहलू अनुपात कैसे रखूं? जावा में तारीखों में अंतर की गणना करना जावा के साथ वेब स्क्रैपिंग आलसी वाल क्या करता है? एक आइफ्रेम के अंदर HTML डालकर (जावास्क्रिप्ट का उपयोग करके) डॉक्यूमेंटबिल्ल्डर बनाओ। डीडीटी संदर्भों को अनदेखा करें मैं जीआईटी में अपनी स्थानीय कार्यरत निर्देशिका को कैसे साफ़ कर सकता हूं? अपेक्षित के रूप में WPF WebBrowser माउस ईवेंट काम नहीं कर रहा है कैसे jquery का उपयोग कर एक लिंक पर क्लिक करने के लिए प्रोग्राम को ट्रिगर करने के लिए? $ Http के लिए कोयरी आईई कैशिंग समस्या जावास्क्रिप्ट में एक गणितीय अभिव्यक्ति के रूप में स्ट्रिंग का मूल्यांकन करना उपयोगकर्ताओं को उनके दृश्य में स्क्रॉल करते समय छवियों को गतिशील रूप से कैसे लोड किया जाता है (या आलसी) मैं गिटहब रेपो में फाइलों और फ़ोल्डरों को कैसे जोड़ूं? संदर्भ से जावा पास जावा प्रकार, क्लास myPackage.B, और MIME मीडिया प्रकार, एप्लिकेशन / ऑक्टेट-स्ट्रीम के लिए एक संदेश शरीर लेखक नहीं मिला

कुशल पूर्णांक फ़ंक्शन की तुलना करें

compare फ़ंक्शन एक ऐसा कार्य है, जो दो तर्कों को a और b लेता a और उनके आदेश का वर्णन करने वाला पूर्णांक देता है। यदि a b से छोटा है, तो परिणाम कुछ नकारात्मक पूर्णांक है। यदि a b से बड़ा है, तो परिणाम कुछ सकारात्मक पूर्णांक है अन्यथा, a और b समान हैं, और परिणाम शून्य है

यह फ़ंक्शन अक्सर मानक लाइब्रेरी से एल्गोरिदम सॉर्टिंग और खोज करने के लिए parametrize के लिए उपयोग किया जाता है।

वर्णों के लिए compare सुविधा कार्यान्वित करना काफी आसान है; आप बस तर्कों को घटाते हैं:

 int compare_char(char a, char b) { return a - b; } 

यह काम करता है क्योंकि दो अक्षरों के बीच का अंतर आम तौर पर एक पूर्णांक में फिट होने के लिए माना जाता है (ध्यान दें कि यह धारणा सिस्टम के लिए नहीं है जहां sizeof(char) == sizeof(int) ।)

इस चाल से इंटिजर्स की तुलना करने के लिए काम नहीं किया जा सकता, क्योंकि दो पूर्णांक के बीच का अंतर आम तौर पर पूर्णांक में फिट नहीं है। उदाहरण के लिए, INT_MAX - (-1) = INT_MIN बताता है कि INT_MAX से छोटा है (तकनीकी रूप से, अतिप्रवाह अपरिभाषित व्यवहार की ओर जाता है, लेकिन हम मॉड्यूलो अंकगणित मानते हैं)।

तो हम कैसे integers के लिए कुशलतापूर्वक तुलना समारोह को लागू कर सकते हैं? यह मेरा पहला प्रयास है:

 int compare_int(int a, int b) { int temp; int result; __asm__ __volatile__ ( "cmp %3, %2 \n\t" "mov $0, %1 \n\t" "mov $1, %0 \n\t" "cmovg %0, %1 \n\t" "mov $-1, %0 \n\t" "cmovl %0, %1 \n\t" : "=r"(temp), "=r"(result) : "r"(a), "r"(b) : "cc"); return result; } 

क्या यह 6 से कम निर्देशों में किया जा सकता है? वहाँ एक कम सीधा रास्ता है कि और अधिक कुशल है?

वेब के समाधान से एकत्रित समाधान "कुशल पूर्णांक फ़ंक्शन की तुलना करें"

निम्नलिखित ने हमेशा मेरे लिए काफी कुशल साबित किया है:

 return (a < b) ? -1 : (a > b); 

gcc -O2 -S , यह निम्न पांच निर्देशों के अनुसार संकलित है:

 xorl %edx, %edx cmpl %esi, %edi movl $-1, %eax setg %dl cmovge %edx, %eax 

अंब्रोज बिज्जाक के उत्कृष्ट साथी के उत्तर के लिए अनुवर्ती के रूप में, मुझे यह आश्वस्त नहीं था कि उनके कार्यक्रम ने उसी विधानसभा कोड का परीक्षण किया जो ऊपर पोस्ट किया गया था। और, जब मैं कंपाइलर आउटपुट का अधिक बारीकी से अध्ययन कर रहा था, मैंने देखा कि कंपाइलर उसी निर्देशों का उत्पादन नहीं कर रहा था जैसा कि हमारे जवाब में पोस्ट किया गया था। इसलिए, मैंने अपना परीक्षण कार्यक्रम लिया, हाथ ने विधानसभा के आउटपुट को हमने जो पोस्ट किया था, उसमें मिलाया और परिणामी समय की तुलना की। ऐसा लगता है कि दो संस्करण लगभग समान रूप से तुलना करते हैं।

 ./opt_cmp_branchless: 0m1.070s ./opt_cmp_branch: 0m1.037s 

मैं प्रत्येक कार्यक्रम की पूरी सभा में पोस्टिंग कर रहा हूं ताकि दूसरे लोग एक ही प्रयोग का प्रयास कर सकें, और मेरी टिप्पणियों की पुष्टि या विरोध कर सकें।

निम्नलिखित cmovge अनुदेश के साथ संस्करण है ( (a < b) ? -1 : (a > b) ):

  .file "cmp.c" .text .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d=0\n" .text .p2align 4,,15 .globl main .type main, @function main: .LFB20: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 movl $arr.2789, %ebx subq $8, %rsp .cfi_def_cfa_offset 32 .L9: leaq 4(%rbx), %rbp .L10: call rand movb %al, (%rbx) addq $1, %rbx cmpq %rbx, %rbp jne .L10 cmpq $arr.2789+4096, %rbp jne .L9 xorl %r8d, %r8d xorl %esi, %esi orl $-1, %edi .L12: xorl %ebp, %ebp .p2align 4,,10 .p2align 3 .L18: movl arr.2789(%rbp), %ecx xorl %eax, %eax .p2align 4,,10 .p2align 3 .L15: movl arr.2789(%rax), %edx xorl %ebx, %ebx cmpl %ecx, %edx movl $-1, %edx setg %bl cmovge %ebx, %edx addq $4, %rax addl %edx, %esi cmpq $4096, %rax jne .L15 addq $4, %rbp cmpq $4096, %rbp jne .L18 addl $1, %r8d cmpl $500, %r8d jne .L12 movl $.LC0, %edi xorl %eax, %eax call printf addq $8, %rsp .cfi_def_cfa_offset 24 xorl %eax, %eax popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE20: .size main, .-main .local arr.2789 .comm arr.2789,4096,32 .section .note.GNU-stack,"",@progbits 

नीचे दिया गया संस्करण शाखाहीन विधि का उपयोग करता है ( (a > b) - (a < b) ):

  .file "cmp.c" .text .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d=0\n" .text .p2align 4,,15 .globl main .type main, @function main: .LFB20: .cfi_startproc pushq %rbp .cfi_def_cfa_offset 16 .cfi_offset 6, -16 pushq %rbx .cfi_def_cfa_offset 24 .cfi_offset 3, -24 movl $arr.2789, %ebx subq $8, %rsp .cfi_def_cfa_offset 32 .L9: leaq 4(%rbx), %rbp .L10: call rand movb %al, (%rbx) addq $1, %rbx cmpq %rbx, %rbp jne .L10 cmpq $arr.2789+4096, %rbp jne .L9 xorl %r8d, %r8d xorl %esi, %esi .L19: movl %ebp, %ebx xorl %edi, %edi .p2align 4,,10 .p2align 3 .L24: movl %ebp, %ecx xorl %eax, %eax jmp .L22 .p2align 4,,10 .p2align 3 .L20: movl arr.2789(%rax), %ecx .L22: xorl %edx, %edx cmpl %ebx, %ecx setg %cl setl %dl movzbl %cl, %ecx subl %ecx, %edx addl %edx, %esi addq $4, %rax cmpq $4096, %rax jne .L20 addq $4, %rdi cmpq $4096, %rdi je .L21 movl arr.2789(%rdi), %ebx jmp .L24 .L21: addl $1, %r8d cmpl $500, %r8d jne .L19 movl $.LC0, %edi xorl %eax, %eax call printf addq $8, %rsp .cfi_def_cfa_offset 24 xorl %eax, %eax popq %rbx .cfi_def_cfa_offset 16 popq %rbp .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE20: .size main, .-main .local arr.2789 .comm arr.2789,4096,32 .section .note.GNU-stack,"",@progbits 

यह किसी की कोई शाखा नहीं है, और अतिप्रवाह या अंडरफ्लो से ग्रस्त नहीं है:

 return (a > b) - (a < b); 

gcc -O2 -S , यह निम्न छह निर्देशों के अनुसार संकलित है:

 xorl %eax, %eax cmpl %esi, %edi setl %dl setg %al movzbl %dl, %edx subl %edx, %eax 

बेंचमार्क विभिन्न तुलना implementations के लिए कुछ कोड है:

 #include <stdio.h> #include <stdlib.h> #define COUNT 1024 #define LOOPS 500 #define COMPARE compare2 #define USE_RAND 1 int arr[COUNT]; int compare1 (int a, int b) { if (a < b) return -1; if (a > b) return 1; return 0; } int compare2 (int a, int b) { return (a > b) - (a < b); } int compare3 (int a, int b) { return (a < b) ? -1 : (a > b); } int compare4 (int a, int b) { __asm__ __volatile__ ( "sub %1, %0 \n\t" "jno 1f \n\t" "cmc \n\t" "rcr %0 \n\t" "1: " : "+r"(a) : "r"(b) : "cc"); return a; } int main () { for (int i = 0; i < COUNT; i++) { #if USE_RAND arr[i] = rand(); #else for (int b = 0; b < sizeof(arr[i]); b++) { *((unsigned char *)&arr[i] + b) = rand(); } #endif } int sum = 0; for (int l = 0; l < LOOPS; l++) { for (int i = 0; i < COUNT; i++) { for (int j = 0; j < COUNT; j++) { sum += COMPARE(arr[i], arr[j]); } } } printf("%d=0\n", sum); return 0; } 

मेरे 64-बिट सिस्टम पर परिणाम, gcc -std=c99 -O2 साथ संकलित, सकारात्मक पूर्णांक ( USE_RAND=1 ) के लिए:

 compare1: 0m1.118s compare2: 0m0.756s compare3: 0m1.101s compare4: 0m0.561s 

सी-केवल समाधानों में से, जो मैंने सुझाया था वह सबसे तेज़ था केवल 5 निर्देशों के संकलन के बावजूद user315052 का समाधान धीमा था। मंदी की संभावना है क्योंकि, एक कम अनुदेश होने के बावजूद, एक सशर्त निर्देश है ( cmovge )।

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

पूर्णांक की पूर्ण श्रेणी ( USE_RAND=0 ) के साथ, 4-निर्देश समाधान वास्तव में बहुत धीमा है (अन्य समान हैं):

 compare4: 0m1.897s 

ठीक है, मैं इसे चार निर्देशों में प्राप्त करने में कामयाब रहा हूं 🙂 मूल विचार इस प्रकार है:

आधा समय, एक पूर्णांक में फिट करने के लिए अंतर काफी छोटा है उस स्थिति में, बस अंतर वापस लौटाएं अन्यथा, नंबर एक को दाईं ओर स्थानांतरित करें महत्वपूर्ण सवाल यह है कि एमएसबी में बदलाव करने के लिए थोड़ा सा क्या है।

सादगी के लिए 32 बिट के बजाए 8 बिट्स का उपयोग करते हुए, दो चरम उदाहरणों को देखें:

  10000000 INT_MIN 01111111 INT_MAX --------- 000000001 difference 00000000 shifted 01111111 INT_MAX 10000000 INT_MIN --------- 111111111 difference 11111111 shifted 

INT_MIN बिट में स्थानांतरण करने से पहले केस के लिए 0 INT_MIN (हालांकि INT_MIN INT_MAX बराबर नहीं है) और दूसरे मामले के लिए कुछ नकारात्मक संख्या (हालांकि INT_MAX INT_MIN से छोटा नहीं है)।

लेकिन अगर हम बदलाव करने से पहले लेयर बिट को फ्लिप करते हैं, तो हमें समझदार संख्या मिलती है:

  10000000 INT_MIN 01111111 INT_MAX --------- 000000001 difference 100000001 carry flipped 10000000 shifted 01111111 INT_MAX 10000000 INT_MIN --------- 111111111 difference 011111111 carry flipped 01111111 shifted 

मुझे यकीन है कि यह एक गहरा गणितीय कारण है कि इसे ले जाने के लिए फ्लिप करने में समझदारी क्यों होती है, लेकिन मुझे अभी तक यह नहीं दिख रहा है।

 int compare_int(int a, int b) { __asm__ __volatile__ ( "sub %1, %0 \n\t" "jno 1f \n\t" "cmc \n\t" "rcr %0 \n\t" "1: " : "+r"(a) : "r"(b) : "cc"); return a; } 

मैंने कोड को एक लाख यादृच्छिक इनपुट के साथ साथ INT_MIN, -INT_MAX, INT_MIN / 2, -1, 0, 1, INT_MAX / 2, INT_MAX / 2 + 1, INT_MAX के हर संयोजन के साथ परीक्षण किया है। सभी परीक्षण पारित क्या आप मुझे गलत साबित कर सकते हैं?

इसके लिए मैं एक एसएसई 2 का कार्यान्वयन एक साथ रखता हूं। vec_compare1 रूप में एक ही दृष्टिकोण का उपयोग करता है, लेकिन सिर्फ तीन एसएसई 2 अंकगणितीय निर्देशों की आवश्यकता होती है:

 #include <stdio.h> #include <stdlib.h> #include <emmintrin.h> #define COUNT 1024 #define LOOPS 500 #define COMPARE vec_compare1 #define USE_RAND 1 int arr[COUNT] __attribute__ ((aligned(16))); typedef __m128i vSInt32; vSInt32 vec_compare1 (vSInt32 va, vSInt32 vb) { vSInt32 vcmp1 = _mm_cmpgt_epi32(va, vb); vSInt32 vcmp2 = _mm_cmpgt_epi32(vb, va); return _mm_sub_epi32(vcmp2, vcmp1); } int main () { for (int i = 0; i < COUNT; i++) { #if USE_RAND arr[i] = rand(); #else for (int b = 0; b < sizeof(arr[i]); b++) { *((unsigned char *)&arr[i] + b) = rand(); } #endif } vSInt32 vsum = _mm_set1_epi32(0); for (int l = 0; l < LOOPS; l++) { for (int i = 0; i < COUNT; i++) { for (int j = 0; j < COUNT; j+=4) { vSInt32 v1 = _mm_loadu_si128(&arr[i]); vSInt32 v2 = _mm_load_si128(&arr[j]); vSInt32 v = COMPARE(v1, v2); vsum = _mm_add_epi32(vsum, v); } } } printf("vsum = %vd\n", vsum); return 0; } 

इसके लिए समय 0.137 है

एक ही सीपीयू और कंपाइलर के साथ तुलना 2 का समय 0.674 है।

इसलिए SSE2 का कार्यान्वयन 4x तेज है, जैसा कि उम्मीद की जा सकती है (क्योंकि यह 4-चौड़ा सीआईडीडी है)।

इस कोड में कोई शाखा नहीं है और 5 निर्देशों का उपयोग करता है। यह हाल के इंटेल प्रोसेसर पर अन्य शाखा-कम विकल्पों को पीछे छोड़ सकता है, जहां cmov * निर्देश काफी महंगा हैं I नुकसान गैर-सममित रिटर्न वैल्यू (INT_MIN + 1, 0, 1) है।

 int compare_int (int a, int b) { int res; __asm__ __volatile__ ( "xor %0, %0 \n\t" "cmpl %2, %1 \n\t" "setl %b0 \n\t" "rorl $1, %0 \n\t" "setnz %b0 \n\t" : "=q"(res) : "r"(a) , "r"(b) : "cc" ); return res; } 

इस प्रकार को आरंभीकरण की आवश्यकता नहीं है, इसलिए यह केवल 4 निर्देशों का उपयोग करता है:

 int compare_int (int a, int b) { __asm__ __volatile__ ( "subl %1, %0 \n\t" "setl %b0 \n\t" "rorl $1, %0 \n\t" "setnz %b0 \n\t" : "+q"(a) : "r"(b) : "cc" ); return a; } 

हो सकता है कि आप निम्न विचार (छद्म-कोड में; asm-code नहीं लिखे क्योंकि मैं सिंटैक्स के साथ सहज नहीं हूँ):

  1. संख्या घटाएं ( result = a - b )
  2. यदि कोई अतिप्रवाह नहीं किया जाता है, तो ( jo अनुदेश और शाखा भविष्यवाणी बहुत अच्छी तरह से काम करनी चाहिए)
  3. अगर अतिप्रवाह होता है, तो किसी भी मजबूत विधि का उपयोग करें return (a < b) ? -1 : (a > b) )

संपादित करें: अतिरिक्त सादगी के लिए: यदि अतिप्रवाह होता है, तो चरण 3 की बजाय, परिणाम का चिह्न फ्लिप करें

आप 64 बिट मूल्यों के लिए पूर्णांक को बढ़ावा देने पर विचार कर सकते हैं