सशर्त शाखाओं से बचने के लिए कौन सी तकनीकें आपको पता हैं?

Question

कभी-कभी एक लूप जहां सीपीयू अधिकतर समय बिताता है, वहां कुछ शाखा भविष्यवाणी मिस (गलत भविष्यवाणी) होती है (लगभग 5 संभावना।) मैंने बहुत अलग थ्रेड पर कुछ तकनीकें देखी हैं लेकिन कभी भी एक सूची नहीं है। जिन लोगों को मैं जानता हूं वे पहले से ही उन स्थितियों को ठीक करते हैं जहां स्थिति को एक बूल में बदल दिया जा सकता है और 0/1 को बदलने के लिए किसी भी तरीके से उपयोग किया जाता है। क्या अन्य सशर्त शाखाएं हैं जिन्हें टाला जा सकता है?

उदा। (स्यूडोकोड)

loop() { 
    if (in[i] < C) 
    out[o++] = in[i++] 
    ... 
} 

इस तरह, फिर से लिखा जा सकता है यकीनन कुछ पठनीयता को खोने, कुछ के साथ:

loop() { 
    out[o] = in[i] // copy anyway, just don't increment 
    inc = in[i] < C // increment counters? (0 or 1) 
    o += inc 
    i += inc 
} 

इसके अलावा, मैं जंगली कुछ संदर्भों में सशर्त में & करने के लिए && बदलने में तकनीक को देखा है अभी मेरे दिमाग से बच रहा है। मैं अनुकूलन के इस स्तर पर एक रूकी हूं लेकिन यह सुनिश्चित करता है कि और अधिक होना है।

Answer 1

मुझे विश्वास है कि ब्रांचिंग से बचने का सबसे आम तरीका है अपने कोड में मौजूद कुल कूद को कम करने में थोड़ा समांतरता का लाभ उठाना। जितना अधिक बुनियादी ब्लॉक, कम पाइपलाइन कम हो जाती है।

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

यहाँ निम्नलिखित सी कोड का एक उदाहरण है:

if (b > a) b = a; 

किसी भी छलांग, बिट हेरफेर का उपयोग कर (और चरम टिप्पणी) द्वारा बिना विधानसभा में

:

sub eax, ebx ; = a - b 
sbb edx, edx ; = (b > a) ? 0xFFFFFFFF : 0 
and edx, eax ; = (b > a) ? a - b : 0 
add ebx, edx ; b = (b > a) ? b + (a - b) : b + 0 

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

Answer 2

आपके द्वारा दिए गए उदाहरण का सामान्यीकरण "गणित के साथ सशर्त मूल्यांकन को प्रतिस्थापित करें" है; सशर्त-शाखा से बचने के लिए काफी हद तक उबाल जाता है।

&& को & के साथ बदलने के साथ क्या चल रहा है, && शॉर्ट-सर्किट है, यह सशर्त मूल्यांकन का गठन करता है। & आपको वही तार्किक परिणाम मिलते हैं यदि दोनों पक्ष या तो 0 या 1 हैं, और शॉर्ट सर्किट नहीं है। || और | पर भी लागू होता है, सिवाय इसके कि आपको यह सुनिश्चित करने की आवश्यकता नहीं है कि पक्ष 0 या 1 (फिर से, केवल तर्क उद्देश्यों के लिए बाध्य हैं, यानी आप केवल बूलेनली के परिणाम का उपयोग कर रहे हैं)।

Answer 3

जीसीसी पहले से ही सरल निर्देशों के साथ सशर्तों को बदलने के लिए पर्याप्त स्मार्ट है। उदाहरण के लिए नए इंटेल प्रोसेसर cmov (सशर्त चाल) प्रदान करते हैं। यदि आप इसका उपयोग कर सकते हैं, तो एसएसई 2 एक समय में compare 4 integers (या 8 शॉर्ट्स, या 16 वर्ण) को कुछ निर्देश प्रदान करता है।

Additionaly न्यूनतम आप उपयोग कर सकते हैं गणना करने के लिए (देखें इन magic tricks):

min(x, y) = x+(((y-x)>>(WORDBITS-1))&(y-x)) 

हालांकि, जैसी बातों पर ध्यान देना:

c[i][j] = min(c[i][j], c[i][k] + c[j][k]); // from Floyd-Warshal algorithm 

भी कोई छलांग लगाए गए

तुलना में बहुत धीमी है

int tmp = c[i][k] + c[j][k]; 
if (tmp < c[i][j]) 
    c[i][j] = tmp; 

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

Answer 4

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

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

Answer 5

ऑप्टिमाइज़ेशन का यह स्तर हॉटस्पॉट के सबसे गर्म लेकिन सभी में एक सार्थक अंतर बनाने की संभावना नहीं है।यह मानते हुए (इसे किसी विशिष्ट मामले में साबित किए बिना) का अनुमान अनुमानित है, और अनुकूलन का पहला नियम अनुमान पर कार्य नहीं करता है।

Answer 6

इस स्तर पर चीजें बहुत हार्डवेयर-निर्भर और संकलक-निर्भर हैं। क्या संकलक आप नियंत्रण प्रवाह के बिना < संकलित करने के लिए पर्याप्त स्मार्ट का उपयोग कर रहे हैं? x86 पर gcc पर्याप्त स्मार्ट है; lcc नहीं है। पुराने या एम्बेडेड निर्देश सेट पर नियंत्रण प्रवाह के बिना < की गणना करना संभव नहीं हो सकता है।

इस कैसंड्रा जैसी चेतावनी से परे, कोई उपयोगी सामान्य बयान देना मुश्किल है। तो यहां कुछ सामान्य बयान दिए गए हैं जो अनुपयोगी हो सकते हैं:

• आधुनिक शाखा-पूर्वानुमान हार्डवेयर भयभीत रूप से अच्छा है। यदि आपको एक वास्तविक कार्यक्रम मिल सकता है जहां खराब शाखा भविष्यवाणी 1% -2% से अधिक मंदी की लागत है, तो मैं बहुत आश्चर्यचकित हूं।

• प्रदर्शन काउंटर या अन्य टूल जो आपको बताते हैं कि शाखा गलतफहमी कहां मिलें, अनिवार्य हैं।

• आप वास्तव में इस तरह के कोड में सुधार करने की जरूरत है, मैं पता लगाने निर्धारण और पाश unrolling पर गौर करेंगे:

  • लूप unrolling पाश निकायों replicates और अपने अनुकूलक के साथ काम करने के लिए और अधिक नियंत्रण प्रवाह देता है।

  • ट्रेस शेड्यूलिंग यह पहचानता है कि कौन से पथ सबसे अधिक होने की संभावना है, और अन्य चालों के बीच, यह शाखा दिशाओं को ट्विक कर सकता है ताकि शाखा-भविष्यवाणी हार्डवेयर सबसे आम पथों पर बेहतर काम कर सके। unrolled छोरों के साथ, वहाँ अधिक और लंबे समय तक पथ, तो ट्रेस अनुसूचक

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

Answer 7

अधिकांश प्रोसेसर शाखा भविष्यवाणी प्रदान करते हैं जो 50% से बेहतर है। वास्तव में, यदि आपको शाखा भविष्यवाणी में 1% सुधार मिलता है तो आप शायद एक पेपर प्रकाशित कर सकते हैं। यदि आप रुचि रखते हैं तो इस विषय पर कागजात का पर्वत है।

आप कैश हिट और मिस के बारे में चिंता करने से बेहतर हैं।

Answer 8

मूल प्रश्न में प्रदर्शित तकनीक का एक विस्तार तब लागू होता है जब आपको उत्तर पाने के लिए कई नेस्टेड परीक्षण करना पड़ता है। आप सभी परीक्षणों के परिणामों से एक छोटा सा बिटकमा बना सकते हैं, और एक तालिका में जवाब "देखो"।

if (a) { 
    if (b) { 
    result = q; 
    } else { 
    result = r; 
    } 
} else { 
    if (b) { 
    result = s; 
    } else { 
    result = t; 
    } 
} 

ए और बी लगभग यादृच्छिक (जैसे, मनमाने ढंग से डेटा से) कर रहे हैं, और यह एक तंग पाश में है, तो शाखा भविष्यवाणी विफलताओं वास्तव में इस धीमा कर सकते हैं। के रूप में लिखा जा सकता है:

// assuming a and b are bools and thus exactly 0 or 1 ... 
static const table[] = { t, s, r, q }; 
unsigned index = (a << 1) | b; 
result = table[index]; 

आप इसे कई सशर्तों में सामान्यीकृत कर सकते हैं। मैंने इसे 4 के लिए किया है। अगर घोंसला उस गहरे हो जाता है, हालांकि, आप यह सुनिश्चित करना चाहते हैं कि उन सभी का परीक्षण शॉर्ट-सर्किट मूल्यांकन द्वारा सुझाए गए न्यूनतम परीक्षणों की तुलना में वास्तव में तेज़ है।

Answer 9

मैट योजक के उदाहरण का उपयोग:

if (b > a) b = a; 

तुम भी विधानसभा कोड में खुदाई करने के लिए बिना, निम्नलिखित कर सकता है:

bool if_else = b > a; 
b = a * if_else + b * !if_else;