यह संभावना है()/संभावना नहीं()

Question

मान लीजिए मैं एक अभिव्यक्ति है जो केवल का एक हिस्सा बहुत संभावना नहीं है नहीं है, लेकिन अन्य सांख्यिकीय तटस्थ है के रूप में एक अभिव्यक्ति का ही हिस्सा चिह्नित करने के लिए उचित है:

if (could_be || very_improbable) { 
    DoSomething(); 
} 

चाहेंगे अगर मैं unlikely() मैक्रो में बहुत असंभव बिट डालता हूं तो यह संकलक को किसी भी तरह से मदद करता है?

if (could_be || unlikely(very_improbable)) { 
    DoSomething(); 
} 

नोट: मैं नहीं पूछ रहा कि मार्को कैसे काम करता है - मैं इसे समझता हूं। यहां सवाल जीसीसी के संबंध में है और क्या यह अभिव्यक्ति को अनुकूलित करने में सक्षम होगा अगर मैं केवल इसके बारे में संकेत देता हूं। मैं यह भी मानता हूं कि यह प्रश्न में अभिव्यक्तियों पर भारी निर्भर हो सकता है - मैं उन लोगों से अपील कर रहा हूं जिनके पास इन मैक्रोज़ का अनुभव है।

Answer 1

हाँ, यह उचित है, और compilers सही परिदृश्य में इसका लाभ उठा सकते हैं और कर सकते हैं।

अपने वास्तविक उदाहरण में, यदि could_be और very_improbable वास्तव में अभिन्न चर हैं, वहाँ नहीं है क्योंकि क्या संकलक वास्तव में के बारे में क्या कर सकते हैं, विधेय की एक उप-अभिव्यक्ति पर likely या unlikely मैक्रो डालने के लिए किसी भी बिंदु होने जा रहा है यह तेजी से बना रहा है? कंपाइलर शाखा के संभावित परिणाम के आधार पर if ब्लॉक को अलग-अलग व्यवस्थित कर सकता है, लेकिन सिर्फ इसलिए कि very_improbably की संभावना नहीं है: इसे अभी भी परीक्षण करने के लिए कोड उत्पन्न करने की आवश्यकता है।

की एक उदाहरण है जहां संकलक अधिक काम कर सकते हैं लेते हैं:

extern int fn1(); 
extern int fn2(); 
extern int f(int x); 

int test_likely(int a, int b) { 
    if (likely(f(a)) && unlikely(f(b))) 
    return fn1(); 
    return fn2(); 
} 

यहाँ विधेय तर्क के साथ f() करने के लिए दो कॉल से बना है, और icclikely के 4 संयोजन में से 3 के लिए अलग अलग कोड का उत्पादन और unlikely: likely(f(a)) && likely(f(b)) के लिए

कोड produced:

test_likely(int, int): 
     push  r15           #8.31 
     mov  r15d, esi          #8.31 
     call  f(int)           #9.7 
     test  eax, eax          #9.7 
     je  ..B1.7  # Prob 5%      #9.7 
     mov  edi, r15d          #9.23 
     call  f(int)           #9.23 
     test  eax, eax          #9.23 
     je  ..B1.7  # Prob 5%      #9.23 
     pop  r15           #10.12 
     jmp  fn1()          #10.12 
..B1.7:       # Preds ..B1.4 ..B1.2 
     pop  r15           #11.10 
     jmp  fn2()          #11.10 

यहां, दोनों भविष्यवाणी संभवतः सत्य हैं, इसलिए icc दोनों मामले के लिए सीधी रेखा कोड उत्पन्न करता है, जहां दोनों सत्य हैं, या तो गलत होने पर बाहर निकलते हैं। unlikely(f(a)) && likely(f(b)) के लिए

कोड produced:

test_likely(int, int): 
     push  r15           #8.31 
     mov  r15d, esi          #8.31 
     call  f(int)           #9.7 
     test  eax, eax          #9.7 
     jne  ..B1.5  # Prob 5%      #9.7 
..B1.3:       # Preds ..B1.6 ..B1.2 
     pop  r15           #11.10 
     jmp  fn2()          #11.10 
..B1.5:       # Preds ..B1.2 
     mov  edi, r15d          #9.25 
     call  f(int)           #9.25 
     test  eax, eax          #9.25 
     je  ..B1.3  # Prob 5%      #9.25 
     pop  r15           #10.12 
     jmp  fn1()          #10.12 

अब, विधेय संभावना गलत है, तो icc उस मामले में एक वापसी के लिए सीधे प्रमुख सीधे लाइन कोड पैदा करता है, और करने के लिए B1.5 को लाइन से बाहर कूदता भविष्यवाणी जारी रखें। उस स्थिति में, यह दूसरी कॉल (f(b)) को सत्य होने की अपेक्षा करता है, इसलिए यह tail-call से fn1() में समाप्त होने वाले कोड के माध्यम से गिरता है। यदि दूसरा कॉल झूठा हो जाता है, तो यह पहले ही कूदने के मामले में पहले से ही इकट्ठा किए गए वही अनुक्रम तक कूदता है (हालांकि B1.3 लेबल)।

यह भी पता चला है के लिए unlikely(f(a)) && unlikely(f(b)) उत्पन्न कोड किया जाना है। इस मामले में, आप कल्पना कर सकते हैं कि jmp fn2() को फॉल-थ्रू केस के रूप में रखने के लिए कोड के अंत को बदलने वाला संकलक, लेकिन ऐसा नहीं है। यह ध्यान देने योग्य है कि यह B1.3 पर पहले अनुक्रम का पुनः उपयोग करने से रोक देगा और यह भी है कि हम इस कोड को भी निष्पादित कर रहे हैं, इसलिए यह पहले से ही असंभव मामले को अनुकूलित करने के लिए छोटे कोड आकार का पक्ष लेना उचित लगता है। likely(f(a)) && unlikely(f(b)) के लिए

कोड produced:

test_likely(int, int): 
     push  r15           #8.31 
     mov  r15d, esi          #8.31 
     call  f(int)           #9.7 
     test  eax, eax          #9.7 
     je  ..B1.5  # Prob 5%      #9.7 
     mov  edi, r15d          #9.23 
     call  f(int)           #9.23 
     test  eax, eax          #9.23 
     jne  ..B1.7  # Prob 5%      #9.23 
..B1.5:       # Preds ..B1.4 ..B1.2 
     pop  r15           #11.10 
     jmp  fn2()          #11.10 
..B1.7:       # Preds ..B1.4 
     pop  r15           #10.12 
     jmp  fn1()          #10.12 

यह सिवाय इसके कि दूसरे विधेय के लिए उम्मीद अब गलत है, पहले मामले (likely && likely) के समान है, तो यह फिर से आदेश ताकि ब्लॉक return fn2() केस गिरावट वाला है।

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

यहां कुछ अन्य नोटों कि "पूरा टेक्स्ट" उपचार नहीं मिला रहे हैं, ऐसे में आप इस दूर हो गया है:

• मैं icc इस्तेमाल किया उदाहरण दर्शाते हैं, लेकिन इस परीक्षण के लिए कम से कम दोनों clang और gcc समान बुनियादी अनुकूलन (4 मामलों में से 3 को अलग-अलग संकलित) बनाते हैं।
• उप-भविष्यवाणियों की संभावनाओं को जानकर एक "स्पष्ट" ऑप्टिमाइज़ेशन एक संकलक भविष्यवाणी के क्रम को उलटाना है। उदाहरण के लिए, यदि आपके पास likely(X) && unlikely(Y) है, तो आप पहले Y स्थिति की जांच कर सकते हैं, क्योंकि यह आपको वाई पर शॉर्टकट की अनुमति देने की संभावना है। जाहिर है, gcc make this optimization सरल भविष्यवाणियों के लिए कर सकता है, लेकिन मैं इसे करने में icc या clang को कॉक्स करने में सक्षम नहीं था। जीसीसी ऑप्टिमाइज़ेशन स्पष्ट रूप से काफी नाजुक है: disappears यदि आप भविष्य को थोड़ा सा बदलते हैं, भले ही अनुकूलन उस मामले में बेहतर होगा।
• कंपाइलर अनुकूलन करने से प्रतिबंधित हैं जब वे गारंटी नहीं दे सकते कि परिवर्तित कोड "जैसे" व्यवहार करेगा, इसे सीधे भाषा अर्थशास्त्र के अनुसार संकलित किया गया था। विशेष रूप से, उनके पास संचालन को पुन: व्यवस्थित करने की सीमित क्षमता होती है जब तक कि वे साबित नहीं कर सकते कि परिचालनों का दुष्प्रभाव नहीं है। अपने भविष्यवाणियों की संरचना करते समय इसे ध्यान में रखें।

---

^{1 बेशक}, यह केवल अनुमति जब संकलक कि X और Y कोई साइड इफेक्ट है देख सकते हैं, और यह नहीं हो सकता है प्रभावी अगर Y भी बहुत कुछ करने के लिए महंगा है X की तुलना में जांच करें (क्योंकि Y पर चेक से बचने का कोई भी लाभ अतिरिक्त X मूल्यांकन की उच्च लागत से अभिभूत है)।

Answer 2

हाँ, सी बुद्धिमान या गार्डिंग का उपयोग करता है। तो अगर हम

if(a() || b()) 

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

तो यदि कोई() सस्ता या संभावित है, बी() महंगा या असंभव है, तो यह पहले() पहले डालने का भुगतान करता है। लेकिन कोड

if(a()) 
    { 
     do_it(); 
    } 
    /* action point */ 
    else if(b()) 
    { 
    do_it(); 
    } 

एक बार नियंत्रण प्रवाह "action_point" तक पहुँचता है equaivalent है आप देखते हैं कि संकलक बता रहा है कि क्या कूद की संभावना है या नहीं मदद मिल सकती है।

Answer 3

हां, यह सहायता हो सकती है। उदाहरण के लिए, उदाहरण के लिए, जब XXX बंद है, तो जीसीसी x अप्रत्याशित y > 0 से पहले परीक्षण करेगा (सिग्विन, जीसीसी 5.4) पर असंभव कोड के निष्पादन से परहेज करेगा। बेशक इस विशेष मामले में y चेक x चेक से पहले लिखा गया है लेकिन यह महत्वपूर्ण नहीं है क्योंकि कोडजन के दौरान आपके कोड को जीसीसी द्वारा किसी भी तरह से अप्रत्याशित तरीके से फिर से बदल दिया जा सकता है। (यानी __builtin_expect पर ध्यान नहीं दिया)

foo: 
    testl %ecx, %ecx 
    je  .L4 
    testl %edx, %edx 
    jg  .L4 
    rep ret 

जब XXX परिभाषित किया गया है:

#ifdef XXX 
#define __builtin_expect(x, y) (x) 
#endif 

void bar(); 

void foo(int x, int y, int z) { 
    if(__builtin_expect(y > 0, 0) || x == 0) 
    bar(); 
} 

जब XXX बंद है (यानी __builtin_expect सक्रिय है)

foo: 
    testl %edx, %edx 
    jg  .L4 
    testl %ecx, %ecx 
    je  .L4 
    rep ret