क्या यह शाखा या गुणा करने के लिए अधिक कुशल है?

Question

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

int total = 0; 
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){ 
    if (i & mask){ 
     total += value[j]; 
    } 
} 

हालांकि, बाद में मैंने सोचा कि यह बेहतर हो सकता है सीपीयू पाइपलाइनिंग मदद करने के लिए शाखाओं में दूर करने के लिए और निम्नलिखित के साथ आया था।

int total = 0; 
for(unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++){ 
    total += ((i & mask) != 0) * value[j]; 
} 

नोट हालांकि यह दूसरा दृष्टिकोण के इस भाग से अगर बयान समाप्त है कि या तो 1 या 0. होने के लिए के बाद से (i & मुखौटा) एक बूलियन जवाब में परिणाम नहीं करता है, 0 के साथ तुलना परिणाम बलों कोड, दूसरे समाधान को समीकरण के अलावा प्रत्येक पुनरावृत्ति पर 0 या 1 के गुणा को चलाने की आवश्यकता है।

कौन सा कोड तेजी से चलाएगा?

Answer 1

आप इसे गुणा किए बिना शाखा रहित बना सकते हैं। ऐसा लगता है कि प्रत्येक बिट सेट के लिए आप उस बिट स्थिति को किसी सरणी में इंडेक्स के रूप में उपयोग कर रहे हैं।

सबसे पहले, आप आसानी से के साथ सेट बिट्स निकाल सकते हैं:

unsigned short set_mask= i & -i; 
i&= i - 1; 

उसके बाद, आप बिट्स (set_mask - 1) में सेट की गणना के द्वारा बिट सूचकांक मिल सकती है। इसके लिए एक स्थिर समय सूत्र है।

कुछ प्लेटफार्मों में थोड़ा सेट की बिट इंडेक्स प्राप्त करने के लिए एक आंतरिक भी है जो शायद तेज़ है। x86 में bsr है, पीपीसी में cntlz है।

तो जवाब शायद सबसे तेजी से है शाखा multiplyless संस्करण है :)

Answer 2

यह संकलक, मशीन निर्देश सेट और शायद, चंद्रमा के चरण पर पूरी तरह से पर निर्भर करता है।

इस वजह से कोई विशिष्ट सही उत्तर नहीं है। यदि आप वास्तव में जानना चाहते हैं, तो कंपाइलर से असेंबली आउटपुट की जांच करें।

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

तो सही उत्तर है: यह निर्भर करता है।

Answer 3

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

बेशक निश्चित रूप से जानने का एकमात्र तरीका कुछ तरीकों से कुछ समय लेना है।

Answer 4

उत्तर निश्चित रूप से होना चाहिए: इसे लक्षित हार्डवेयर पर देखें और देखें। और पिछले कुछ हफ्तों में SO पर पोस्ट किए गए माइक्रो-बेंचमार्क/स्टॉपवॉच-बेंचमार्क प्रश्नों की भीड़ की सलाह का पालन करना सुनिश्चित करें।

लिंक एक बेंच मार्किंग सवाल का: Is stopwatch benchmarking acceptable?

व्यक्तिगत रूप से, मैं, अगर साथ जाना चाहते हैं जब तक कि वहाँ एक बहुत सम्मोहक "अस्पष्ट" विकल्प का उपयोग करने के कारण था।

Answer 5

कौन सा कोड तेजी से चलाएगा?

यह पता लगाने के लिए परीक्षण करें।

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

Answer 6

या तो तेज़ हो सकता है। कुछ प्रोसेसर के लिए, वास्तविक इनपुट डेटा उत्तर बदल सकता है।आपको वास्तविक डेटा के साथ दोनों दृष्टिकोणों को प्रोफाइल करने की आवश्यकता होगी। यहां कुछ चीजें हैं जो x86 हार्डवेयर पर वास्तविक प्रदर्शन को प्रभावित कर सकती हैं।

चलिए इस पल के लिए मान लें कि आप देर से मॉडल पेंटियम 4 का उपयोग कर रहे हैं। उस प्रोसेसर में सीपीयू में पके हुए शाखा भविष्यवाणियों के दो स्तर हैं। यदि शाखा भविष्यवाणियां शाखा दिशा को सही ढंग से अनुमान लगा सकती हैं, तो मुझे संदेह है कि पहला सबसे तेज़ होगा। यह संभवतः तब होने की संभावना है जब झंडे लगभग समान मूल्य हों या यदि वे अधिकतर समय में एक बहुत ही सरल पैटर्न में वैकल्पिक होते हैं। अगर झंडे वास्तव में यादृच्छिक हैं, तो शाखा पूर्वानुमानकर्ता आधा समय गलत होगा। हमारे hypothetical 32-चरण पेंटियम 4 के लिए, यह प्रदर्शन को मार देगा। पेंटियम 3 चिप्स, कोर 2 चिप्स, कोर i7, और अधिकांश एएमडी चिप्स के लिए, पाइपलाइन कम हैं, इसलिए खराब शाखा भविष्यवाणी की लागत बहुत कम है।

यदि आपका वैल्यू वेक्टर प्रोसेसर के कैश से काफी बड़ा है, तो या तो मेमोरी बैंडविड्थ द्वारा दृष्टिकोण सीमित होगा। वे दोनों अनिवार्य रूप से समान प्रदर्शन विशेषताओं दोनों होंगे। यदि वैल्यू वेक्टर कैश में आराम से फिट बैठता है, तो सावधान रहें कि आप कोई प्रोफाइलिंग कैसे करते हैं ताकि परीक्षण लूप में से एक को कैश भरने के लिए दंडित नहीं किया जा रहा है और इससे अन्य लाभ भी प्राप्त हो रहे हैं।

Answer 7

केवल असली तरीका निर्धारित करने के लिए एक बयान की सच्चाई का परीक्षण करने के लिए है। इस बात को ध्यान में रखते हुए मैं पिछली पोस्टों के साथ सहमत हूं जो कहें कि इसे आजमाएं!

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

Answer 8

इस संशोधन के बारे में क्या?

int total = 0; 
for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++){ 
    total += (mask & 0x0001) * value[j]; 
} 

मैं i की एक प्रति 16 बिट अहस्ताक्षरित सीमा तक सीमित में mask कर दिया है, लेकिन कोड की जाँच करता मुखौटा के अंतिम बिट सेट कर दिया जाता हो, जो उस थोड़ा करके सरणी मान बढ़ा रही हैं। यह तेजी से होना चाहिए क्योंकि प्रति पुनरावृत्ति कम ऑपरेशन हैं, और केवल मुख्य पाश शाखाओं और शर्तों की आवश्यकता है। साथ ही, यदि i प्रारंभ करने के लिए छोटा है तो लूप प्रारंभ से बाहर निकल सकता है।

---

यह दर्शाता है कि माप महत्वपूर्ण क्यों है। मैं एक पुरातन सूर्य SPARC का उपयोग कर रहा हूँ। मैंने टेस्ट 0 और टेस्ट 1 के रूप में प्रश्न के दो दावेदारों के साथ, परीक्षण 2 के रूप में अपना उत्तर दिया और फिर परीक्षण परीक्षण चलाया। 'योग' को सैनिटी चेक के रूप में मुद्रित किया जाता है - यह सुनिश्चित करने के लिए कि एल्गोरिदम सभी एक ही जवाब देते हैं।

64-बिट unoptimized:

gcc -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4 

Test 0: (sum = 1744366) 7.973411 us 
Test 1: (sum = 1744366) 10.269095 us 
Test 2: (sum = 1744366) 7.475852 us 

नाइस: मेरा थोड़ा तेजी से मूल की तुलना में है, और ऊपर souped संस्करण धीमी है।

64-बिट अनुकूलित:

gcc -O4 -m64 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib/sparcv9 -ljl -lposix4 

Test 0: (sum = 1744366) 1.101703 us 
Test 1: (sum = 1744366) 1.915972 us 
Test 2: (sum = 1744366) 2.575318 us 

अरे - मेरी संस्करण अब नाटकीय रूप से धीमी है। अनुकूलक अच्छा है!

32-बिट अनुकूलित:

gcc -O4 -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4 

Test 0: (sum = 1744366) 0.839278 us 
Test 1: (sum = 1744366) 1.905009 us 
Test 2: (sum = 1744366) 2.448998 us 

32-बिट unoptimized:

gcc -std=c99 -I$HOME/inc -o x x.c -L$HOME/lib -ljl -lposix4 

Test 0: (sum = 1744366) 7.493672 us 
Test 1: (sum = 1744366) 9.610240 us 
Test 2: (sum = 1744366) 6.838929 us 

पर (32-बिट) Cygwin और एक नहीं तो बुढ़ापे लैपटॉप एक ही कोड (32-बिट, अनुकूलित)

Test 0: (sum = 1744366) 0.557000 us 
Test 1: (sum = 1744366) 0.553000 us 
Test 2: (sum = 1744366) 0.403000 us 

अब मेरी कोड सबसे तेज है। यही कारण है कि आप उपाय करते हैं! यह भी दिखाता है कि क्यों लोग जो जीवित रहने के लिए बेंचमार्क चलाते हैं, वे परेशान हो जाते हैं।

टेस्ट दोहन (चिल्लाओ अगर आप timer.h और timer.c कोड चाहते हैं):

#include <stdio.h> 
#include "timer.h" 

static volatile int value[] = 
{ 
    12, 36, 79, 21, 31, 93, 24, 15, 
    56, 63, 20, 47, 62, 88, 9, 36, 
}; 

static int test_1(int i) 
{ 
    int total = 0; 
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++) 
    { 
     if (i & mask) 
      total += value[j]; 
    } 
    return(total); 
} 

static int test_2(int i) 
{ 
    int total = 0; 
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++) 
    { 
     total += ((i & mask) != 0) * value[j]; 
    } 
    return(total); 
} 

static int test_3(int i) 
{ 
    int total = 0; 
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++) 
    { 
     total += (mask & 0x0001) * value[j]; 
    } 
    return(total); 
} 

typedef int(*func_pointer)(int); 

static func_pointer test[] = { test_1, test_2, test_3 }; 

#define DIM(x)(sizeof(x)/sizeof(*(x))) 

int main() 
{ 
    int i, j, k; 
    char buffer[32]; 
    for (i = 0; i < DIM(test); i++) 
    { 
     Clock t; 
     long sum = 0; 
     clk_init(&t); 
     clk_start(&t); 
     for (j = 0; j < 0xFFFF; j += 13) 
     { 
      int rv; 

      for (k = 0; k < 1000; k++) 
       rv = (*test[i])(j); 
      sum += rv; 
     } 
     clk_stop(&t); 
     printf("Test %d: (sum = %ld) %9s us\n", i, sum, 
       clk_elapsed_us(&t, buffer, sizeof(buffer))); 
    } 
} 

मैं समय बिताया नहीं किया काम क्यों मेरे कोड जब अनुकूलित धीमी है।

Answer 9

क्यों यह (यह मानते हुए मैं 32 बिट है) नहीं कर

for (i2 = i; i2; i2 = i3) { 
    i3 = i2 & (i2-1); 
    last_bit = i2-i3; 
    a = last_bit & 0xffff; 
    b = (last_bit << 16); 
    j = place[a] + big_place[b]; 
    total += value[j]; 
    } 

कहाँ जगह आकार की एक तालिका है 2^15 + 1 ऐसी है कि जगह [0] = 0, जगह [1] = 1 , जगह [2] = 2, जगह [4] = 3, जगह [8] = 4 ... जगह [15] = 16 (बाकी मूल्यों से कोई फर्क नहीं पड़ता)। और big_place लगभग समान है: big_place [0] = 0, big_place [1] = 17 .... big_place [15] = 32.

Answer 10

total += ((i & mask) != 0) * value[j]; 

के स्थान पर प्रयास करें

total += (-((i & mask) != 0)) & value[j]; 

यह गुणा से बचाता है। चाहे कोई शाखा होगी या नहीं, इस पर निर्भर है कि संकलक के लिए शाखा-मुक्त कोड खोजने के लिए पर्याप्त चालाक है - (foo! = 0)। (जो संभव है, लेकिन मैं थोड़ा आश्चर्य होगा।)

(बेशक, इस two's-पूरक प्रतिनिधित्व पर निर्भर करता है;। सी मानक उस पर नास्तिक है)

आप संकलक बाहर मदद कर सकता है की तरह तो, 32-बिट ints संभालने और उस पर हस्ताक्षर किए >> प्रसारित संकेत बिट:

total += (((int)((i & mask) << (31 - j))) >> 31) & value[j]; 

है यही कारण है, बदलाव संभवतः सेट बिट सबसे महत्वपूर्ण पद के लिए छोड़ दिया है, पर हस्ताक्षर किए पूर्णांक के रूप में कास्ट, तो सही सब उपरोक्त कार्यान्वयन-परिभाषित धारणाओं के तहत, कम से कम महत्वपूर्ण स्थिति पर वापस, सभी 0 या सभी 1 को उपज देना। (मैंने इसका परीक्षण नहीं किया है।)

एक और संभावना: एक समय में 4 बिट्स (कहें) के ब्लॉक पर विचार करें। 16 अलग-अलग जोड़ अनुक्रम हैं; आप प्रत्येक कोड ब्लॉक के भीतर कोई परीक्षण नहीं होने के साथ, उनमें से प्रत्येक के लिए अनियंत्रित कोड प्रेषित कर सकते हैं। यहां आशा है कि एक अप्रत्यक्ष कूद के लिए 4 से कम परीक्षण और शाखाएं होंगी।

अद्यतन: जोनाथन Leffler की मचान का उपयोग करना, 4-बिट-पर-एक-समय विधि सबसे तेज है मेरी मैकबुक पर एक व्यापक अंतर से। नकारात्मक - और गुणा के समान होने के बारे में पता चला है। मुझे आश्चर्य है कि प्रोसेसर 0 और 1 तेज जैसे विशेष मामलों को गुणा करता है (या ऐसा कोई विशेष मामला नहीं है यदि यह अधिकतर बिट्स-स्पष्ट या अधिकतर बिट्स-सेट गुणों के लिए सामान्य रूप से तेज़ है)।

मैंने स्वीकार्य उत्तर को कोड नहीं किया है क्योंकि यह इस विशेष बेंचमार्क पर सबसे तेज़ होने की संभावना नहीं है (इसे केवल सेट बिट्स का आकलन करने से अधिक लाभ प्राप्त करना चाहिए, स्पैस सेट पर सर्वश्रेष्ठ प्रदर्शन करना चाहिए, लेकिन बिट्स का पूरी तरह से आधा इस बेंचमार्क में सेट हैं)। यहाँ Leffler की कोड के लिए मेरे परिवर्तन कर रहे हैं, इस मामले में किसी और को इस पर समय बिताने के लिए अजीब प्रेरित है:

#include <stdio.h> 
#include <time.h> 

static int value[] = 
{ 
    12, 36, 79, 21, 31, 93, 24, 15, 
    56, 63, 20, 47, 62, 88, 9, 36, 
}; 

static int test_1(int i) 
{ 
    int total = 0; 
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++) 
    { 
     if (i & mask) 
      total += value[j]; 
    } 
    return(total); 
} 

static int test_2(int i) 
{ 
    int total = 0; 
    for (unsigned short mask = 0x0001, j = 0; mask != 0; mask <<= 1, j++) 
    { 
     total += ((i & mask) != 0) * value[j]; 
    } 
    return(total); 
} 

static int test_3(int i) 
{ 
    int total = 0; 
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++) 
    { 
     total += (mask & 0x0001) * value[j]; 
    } 
    return(total); 
} 

static int test_4(int i) 
{ 
    int total = 0; 
    for (unsigned mask = i & 0xFFFF, j = 0; mask != 0; mask >>= 1, j++) 
    { 
     total += -(mask & 0x0001) & value[j]; 
    } 
    return(total); 
} 

static int test_5(int i) 
{ 
    int total = 0; 
    const int *p = value; 
    for (unsigned mask = i & 0xFFFF; mask != 0; mask >>= 4, p += 4) 
    { 
     switch (mask & 0xF) 
     { 
     case 0x0: break; 
     case 0x1: total += p[0]; break; 
     case 0x2: total += p[1]; break; 
     case 0x3: total += p[1] + p[0]; break; 
     case 0x4: total += p[2]; break; 
     case 0x5: total += p[2] + p[0]; break; 
     case 0x6: total += p[2] + p[1]; break; 
     case 0x7: total += p[2] + p[1] + p[0]; break; 
     case 0x8: total += p[3]; break; 
     case 0x9: total += p[3] + p[0]; break; 
     case 0xA: total += p[3] + p[1]; break; 
     case 0xB: total += p[3] + p[1] + p[0]; break; 
     case 0xC: total += p[3] + p[2]; break; 
     case 0xD: total += p[3] + p[2] + p[0]; break; 
     case 0xE: total += p[3] + p[2] + p[1]; break; 
     case 0xF: total += p[3] + p[2] + p[1] + p[0]; break; 
     } 
    } 
    return(total); 
} 

typedef int(*func_pointer)(int); 

static func_pointer test[] = { test_1, test_2, test_3, test_4, test_5 }; 

#define DIM(x)(sizeof(x)/sizeof(*(x))) 

int main() 
{ 
    int i, j, k; 
    for (i = 0; i < DIM(test); i++) 
    { 
     long sum = 0; 
     clock_t start = clock(); 
     for (j = 0; j <= 0xFFFF; j += 13) 
     { 
      int rv; 

      for (k = 0; k < 1000; k++) 
       rv = (*test[i])(j); 
      sum += rv; 
     } 
     clock_t stop = clock(); 
     printf("(sum = %ld) Test %d: %8.6f s\n", sum, i + 1, 
       (stop - start)/(1.0 * CLOCKS_PER_SEC)); 
    } 
} 

परिणाम (gcc -O4 -std=c99 branchmult2.c):

(sum = 1744366) Test 1: 0.225497 s 
(sum = 1744366) Test 2: 0.221127 s 
(sum = 1744366) Test 3: 0.126301 s 
(sum = 1744366) Test 4: 0.124750 s 
(sum = 1744366) Test 5: 0.064877 s 

संपादित करें 2: मैंने तय कर लिया परीक्षण होगा volatile क्वालीफायर के बिना अधिक यथार्थवादी बनें।

Answer 11

उदार होने के लिए आप लूप, शिफ्ट और गुणाओं से बच सकते हैं - स्विच का उपयोग करें।

switch (i) { 
    case 0: break; 
    case 1: total = value[0]; break; 
    case 2: total = value[1]; break; 
    case 3: total = value[1] + value[0]; break; 
    case 4: total = value[2]; break; 
    case 5: total = value[2] + value[0]; break; 
    ... 
} 

यह टाइप करने के लिए एक बहुत है, लेकिन मुझे लगता है कि यह बहुत तेजी से चलाने के समय में हो जाएगा। आप लुकअप टेबल के प्रदर्शन को हरा नहीं सकते!

मैं एक छोटी पर्ल स्क्रिप्ट लिखूंगा जो मेरे लिए यह कोड उत्पन्न करेगा - बस टाइपिंग त्रुटियों से बचने के लिए।

यदि आपको लगता है कि यह थोड़ा चरम है तो आप छोटे टेबल का उपयोग कर सकते हैं - 4 बिट्स के लिए, और कई बार मुखौटा को स्थानांतरित करते हुए, कई बार एक लुकअप करते हैं। प्रदर्शन थोड़ा पीड़ित होगा, लेकिन कोड बहुत छोटा होगा।

Answer 12

स्पष्ट समाधान:

int total = 0; 
for(unsigned j = 0; j < 16; j++){ 
    total += -(i>>j & 1) & value[j]; 
}