जीसीसी

Question

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

bool conditionA = getA(); 
bool conditionB = getB(); 
bool conditionC = getC(); 
//Etc. 

startTiming(); 

do { 
    if(conditionA) { 
     doATrueStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } else { 
     doAFalseStuff(); 
     if(conditionB) { 
      //Etc. 
     } else { 
      //Etc. 
     } 
    } 
} while (testCondition()); 

endTiming(); 

कहाँ doATrueStuff() एक इनलाइन समारोह तो वहाँ यह बुला में कोई भूमि के ऊपर है कि कुछ सरल संख्यात्मक गणना करता है।

दुर्भाग्य से, शर्तों को पहले से परिभाषित नहीं किया जा सकता है, उन्हें रनटाइम के दौरान गणना की जानी चाहिए। हम भरोसेमंद या गलत होने का मौका भी अनुमानित नहीं कर सकते हैं। getA()rand()%2 भी हो सकता है। लेकिन एक बार गणना की, उनका मूल्य कभी नहीं बदलता है।

दो समाधान मैं की, एक होने के वैश्विक समारोह संकेत दिए गए कि पाश के भीतर उचित समारोह कॉल करने के लिए उपयोग किया जाता है, इस तरह सोचा है के होते हैं:

void (*ptrA)(void); 
//Etc. 

int main(int argc, char **argv) { 
    //... 
    if (conditionA) { 
     ptrA=&aTrueFunc; 
    } else { 
     ptrA=&aFalseFunc; 
    } 
    //... 
    do { 
     (*ptrA)(); 
    } while (testCondition()); 
    //... 
} 

इस तरह मैं से सभी शाखाओं को समाप्त कर सकते लूप, हालांकि तब मुझे कई फंक्शन कॉल का ओवरहेड होगा जो मुझे धीमा कर देगा।

या मैं बस की स्थिति के प्रत्येक संयोजन के लिए एक अलग पाश, कुछ इस तरह हो सकता है:

if(conditionA) { 
    if(conditionB) { 
     do { 
      //Do A == true B == true stuff 
     } while (testCondition()); 
    } else { 
     do { 
      //Do A == true B == false stuff 
     } while (testCondition()); 
    } 
} else { 
    //Etc. 
} 

हालांकि कि बहुत कम खूबसूरत है और एक तो कुशलता से करने के लिए एक बार एक भी होने शुरू होता है असंभव हो जाता है कई स्थितियों, क्योंकि एक्स शर्तों के लिए एक को 2^एक्स loops लिखने की जरूरत है।

क्या यह अनुकूलित करने के लिए एक और अधिक सुरुचिपूर्ण/तेज़ तरीका है?

क्या इसमें कोई भी बिंदु है या संकलक किसी भी तरह से समझता है कि लूप के दौरान स्थिति बदलती नहीं है और इसे स्वयं अनुकूलित करती है?

और जिज्ञासा से बाहर, क्या कोई अन्य प्रोग्रामिंग भाषा है जो इस तरह के कोड को आसान/संभव बना देगी? या यह केवल एक बार स्मृति में लोड होने के बाद प्रोग्राम के निर्देशों को बदलने के लिए असेंबली का उपयोग करके संभव होगा?

Answer 1

थ्योरी:

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

1. शाखा भविष्यवाणी: संकलक क्या कर सकते हैं कि profile guided optimizations का उपयोग कर, मुख्य रूप से प्रत्येक शाखा की संभावना का आकलन करने के द्वारा संकलक और भी प्रोसेसर कोड 2 तकनीक का उपयोग का अनुकूलन कर सकते हैं। सीपीयू में शाखा लक्ष्य बफर भी हैं जो प्रत्येक लक्ष्य के आंकड़ों की गणना के अलावा शाखाकरण पैटर्न का पता लगाने का प्रयास करते हैं।
2. शाखा विशेषण: संकलक या CPU कोड समानांतर में दोनों शाखाओं पर अमल (क्योंकि आजकल प्रोसेसर superscalar कर रहे हैं) और हालत परिणाम के आधार पर, यह सिर्फ गलत पथ के परिणाम उपेक्षा देगा (जैसे CMOV अनुदेश)। आप अक्षम शाखा भविष्यवाणी का उपयोग कर सकते हैं: -फनो-अगर-रूपांतरण और -फनो-अगर-रूपांतरण 2। इससे मदद मिल सकती है कि प्रत्येक शाखा पर बहुत अधिक गणना है और सभी पथों को निष्पादित करने से निर्देश डिकोडर्स और निष्पादन बंदरगाहों का अपशिष्ट हो जाएगा।

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

शाखा भविष्यवाणी दक्षता देखने के लिए, perf stat ./binary का उपयोग करें और शाखा मिस अनुपात देखें, और प्रत्येक अनुकूलन के लिए शाखा मिस की संख्या देखें।

अपने कोड मामले में:

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

Answer 2

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

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

template <bool B0, bool B1, bool B2> 
void doStuffStage3() 
{ 
    // Once you get here, you can use B0, B1, and B2 in 
    // any expressions you want, in the inner loop, and the compiler 
    // will optimize everything out since they're known compile-time. Basically, 
    // the compiler will create separate versions of this function 
    // for all required combinations of the input 
    do { 
     if(B0) { 

     } else { 

     } 
    } while(testCondition()); 
} 

template <bool B0, bool B1> 
void doStuffStage2(bool b2) 
{ 
    if(b2) doStuffStage3<B0,B1,true>(); 
    else doStuffStage3<B0,B1,false>(); 
} 

template <bool B0> 
void doStuffStage1(bool b1, bool b2) 
{ 
    if(b1) doStuffStage2<B0,true> (b2); 
    else doStuffStage2<B0,false>(b2); 
} 

void doStuff(bool b0, bool b1, bool b2) 
{ 
    if(b0) doStuffStage1<true> (b1, b2); 
    else doStuffStage1<false>(b1, b2); 
} 

int main() 
{ 
    doStuff(getA(), getB(), getC()); 
}