c++ - <<से तेज़<= है?




performance assembly (9)

अन्य उत्तरों ने x86 आर्किटेक्चर पर ध्यान केंद्रित किया है, और मुझे ARM आर्किटेक्चर (जो आपका उदाहरण असेंबलर लगता है) विशेष रूप से उत्पन्न कोड पर टिप्पणी करने के लिए पर्याप्त नहीं है, लेकिन यह micro-optimisation का एक उदाहरण है जो बहुत वास्तुकला है विशिष्ट, और एक अनुकूलन होने की संभावना है क्योंकि यह एक अनुकूलन होना है

इस प्रकार, मैं सुझाव दूंगा कि इस प्रकार का micro-optimisation सर्वश्रेष्ठ सॉफ्टवेयर इंजीनियरिंग अभ्यास के बजाय कार्गो पंथ प्रोग्रामिंग का एक उदाहरण है।

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

फिर भी, लगभग सभी मामलों में, संकलक मूल्यांकन निर्देशों को इस तरह से आदेश दे सकता है कि व्यावहारिक रूप से, किसी भी तुलना में किसी भी तुलना में कोई फायदा नहीं हुआ। सबसे खराब मामला हालांकि, इसे ऑपरेंड स्टैक पर शीर्ष दो आइटमों को स्वैप करने के लिए एक रिवर्स निर्देश (आरईवी) जोड़ने की आवश्यकता हो सकती है। यह एक बाइट निर्देश था जिसने एक चक्र को चलाने के लिए लिया, इसलिए सबसे छोटा ओवरहेड संभव था।

इस तरह माइक्रो-ऑप्टिमाइज़ेशन एक ऑप्टिमाइज़ेशन है या एंटी-ऑप्टिमाइज़ेशन आपके द्वारा उपयोग किए जाने वाले विशिष्ट आर्किटेक्चर पर निर्भर करता है, इसलिए आमतौर पर आर्किटेक्चर विशिष्ट माइक्रो-ऑप्टिमाइज़ेशन का उपयोग करने की आदत में जाना एक बुरा विचार है, अन्यथा आप सहजता से ऐसा करने के लिए अनुचित होने पर एक का उपयोग करें, और ऐसा लगता है कि यह वही है जो आप पढ़ रहे हैं वकालत है।

मैं एक पुस्तक पढ़ रहा हूं जहां लेखक कहता है कि if( a < 901 ) तेज है if( a <= 900 )

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


असल में, वे बिल्कुल एक ही गति होगी, क्योंकि असेंबली स्तर पर वे दोनों एक पंक्ति लेते हैं। जैसे कि:

  • jl ax,dx (अगर एक्सएक्स डीएक्स से कम है तो कूदता है)
  • jle ax,dx (कूदता है अगर jle ax,dx से कम या बराबर है)

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


उनके पास एक ही गति है। हो सकता है कि कुछ विशेष आर्किटेक्चर में उसने जो कहा वह सही है, लेकिन कम से कम x86 परिवार में मुझे पता है कि वे वही हैं। क्योंकि ऐसा करने के लिए सीपीयू एक सबस्ट्रक्शन (ए - बी) करेगा और फिर ध्वज रजिस्टर के झंडे की जांच करेगा। उस रजिस्टर के दो बिट्स को जेडएफ (शून्य ध्वज) और एसएफ (साइन फ्लैग) कहा जाता है, और यह एक चक्र में किया जाता है, क्योंकि यह इसे एक मुखौटा ऑपरेशन के साथ करेगा।


ऐतिहासिक रूप से (हम 1 9 80 के दशक और 1 99 0 के दशक की शुरुआत में बात कर रहे हैं), कुछ वास्तुकलाएं थीं जिनमें यह सच था। मूल मुद्दा यह है कि पूर्णांक तुलना मूल रूप से पूर्णांक घटाव के माध्यम से कार्यान्वित की जाती है। इससे निम्नलिखित मामलों में वृद्धि होती है।

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

अब, जब A < B घटाव को घटाव के लिए एक उच्च-बिट उधार लेना पड़ता है, जैसे आप हाथ से जोड़कर और घटाते समय लेते हैं और उधार लेते हैं। यह "उधार" बिट आमतौर पर ले जाने वाली बिट के रूप में जाना जाता था और शाखा निर्देश द्वारा परीक्षण किया जा सकता था। शून्य बिट नामक दूसरी बिट सेट की जाएगी यदि घटाव समान रूप से शून्य था जो समानता को दर्शाता था।

आम तौर पर कम से कम दो सशर्त शाखा निर्देश थे, एक ले जाने वाली बिट पर एक और शून्य बिट पर एक।

अब, इस मामले के दिल को पाने के लिए, ले जाने और शून्य बिट परिणामों को शामिल करने के लिए पिछली तालिका का विस्तार करें।

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

इसलिए, A < B लिए एक शाखा को लागू करने के लिए एक निर्देश में किया जा सकता है, क्योंकि लेयर बिट केवल इस मामले में स्पष्ट है, यानी,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

लेकिन, अगर हम कम से कम बराबर तुलना करना चाहते हैं, तो हमें समानता के मामले को पकड़ने के लिए शून्य ध्वज की अतिरिक्त जांच करने की आवश्यकता है।

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

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


नहीं, यह अधिकांश आर्किटेक्चर पर तेज़ नहीं होगा। आपने निर्दिष्ट नहीं किया है, लेकिन x86 पर, सभी अभिन्न तुलना आमतौर पर दो मशीन निर्देशों में लागू की जाएंगी:

  • एक test या cmp निर्देश, जो EFLAGS सेट EFLAGS
  • और तुलनात्मक प्रकार (और कोड लेआउट) के आधार पर एक Jcc (कूद) निर्देश :
    • jne - अगर बराबर नहीं है -> ZF = 0
    • jz - शून्य (बराबर) -> ZF = 1 कूदें
    • jg - यदि अधिक हो तो कूदें -> ZF = 0 and SF = OF
    • (आदि...)

उदाहरण ( $ gcc -m32 -S -masm=intel test.c लिए संपादित) $ gcc -m32 -S -masm=intel test.c साथ संकलित

    if (a < b) {
        // Do something 1
    }

के लिए संकलित:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

तथा

    if (a <= b) {
        // Do something 2
    }

के लिए संकलित:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

तो दोनों के बीच एकमात्र अंतर एक jg निर्देश बनाम एक jg । दोनों एक ही समय ले लेंगे।

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

लेटेंसी - निर्देश बनाने वाले सभी μops के निष्पादन को पूरा करने के लिए निष्पादन कोर के लिए घड़ी चक्रों की संख्या आवश्यक है।

थ्रूपुट - समस्या चक्रों से पहले इंतजार करने के लिए घड़ी चक्रों की संख्या एक ही निर्देश को फिर से स्वीकार करने के लिए स्वतंत्र हैं। कई निर्देशों के लिए, निर्देश का थ्रूपुट इसकी विलंबता से काफी कम हो सकता है

Jcc लिए Jcc हैं:

      Latency   Throughput
Jcc     N/A        0.5

Jcc पर निम्नलिखित फुटनोट के साथ:

7) सशर्त कूद निर्देशों का चयन शाखाओं की भविष्यवाणी में सुधार के लिए धारा धारा 3.4.1, "शाखा भविष्यवाणी अनुकूलन" की सिफारिश पर आधारित होना चाहिए। जब शाखाओं की सफलतापूर्वक भविष्यवाणी की जाती है, तो jcc की विलंबता प्रभावी रूप से शून्य होती है।

इसलिए, इंटेल डॉक्स में कुछ भी कभी भी एक Jcc निर्देश को दूसरों से अलग तरीके से नहीं मानता है।

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

संपादित करें: फ़्लोटिंग प्वाइंट

यह x87 फ्लोटिंग पॉइंट के लिए भी सच है: (उपरोक्त के रूप में बहुत अधिक कोड, लेकिन int बजाय double साथ।)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

फ़्लोटिंग पॉइंट कोड के लिए, <= तुलना वास्तव में आधुनिक आर्किटेक्चर पर भी धीमी हो सकती है (एक निर्देश द्वारा)। पहला कार्य यहां दिया गया है:

int compare_strict(double a, double b) { return a < b; }

पावरपीसी पर, सबसे पहले यह एक फ्लोटिंग पॉइंट तुलना करता है (जो cr , कंडीशन रजिस्टर अपडेट करता है), फिर स्थिति रजिस्टर को जीपीआर में ले जाता है, "बिट से कम" की तुलना में थोड़ा सा स्थानांतरित करता है, और फिर लौटाता है। इसमें चार निर्देश होते हैं।

अब इसके बजाय इस फ़ंक्शन पर विचार करें:

int compare_loose(double a, double b) { return a <= b; }

इसके लिए उपरोक्त compare_strict के समान कार्य की आवश्यकता है, लेकिन अब ब्याज के दो बिट हैं: "इससे कम था" और "बराबर था।" इन दो बिट्स को एक में गठबंधन करने के लिए इसके लिए एक अतिरिक्त निर्देश ( cror -कंडीशन रजिस्टर bitwise OR) की आवश्यकता होती है। तो compare_loose लिए पांच निर्देशों की आवश्यकता है, जबकि compare_strict चार की आवश्यकता है।

आपको लगता है कि संकलक दूसरे फ़ंक्शन को इस तरह अनुकूलित कर सकता है:

int compare_loose(double a, double b) { return ! (a > b); }

हालांकि यह गलत तरीके से NaNs को संभालेगा। NaN1 <= NaN2 और NaN1 > NaN2 को दोनों को झूठी मूल्यांकन करने की आवश्यकता है।


मैं देखता हूं कि न तो तेज़ है। संकलक प्रत्येक शर्त में एक अलग मूल्य के साथ एक ही मशीन कोड उत्पन्न करता है।

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

मेरा उदाहरण if जीसीसी से x86_64 मंच पर लिनक्स पर है।

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

मैंने देखा कि यदि यह स्थिर नहीं है, तो एक ही मशीन कोड किसी भी मामले में उत्पन्न होता है।

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

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


शायद उस अज्ञात पुस्तक के लेखक ने पढ़ा है कि a > 0 a >= 1 से तेज़ चलता है और सोचता है कि यह सार्वभौमिक रूप से सत्य है।

लेकिन ऐसा इसलिए है क्योंकि 0 शामिल है (क्योंकि CMP आर्किटेक्चर के आधार पर, OR साथ बदल सकता है) और < कारण नहीं।






relational-operators