ब्रांचलेस कोड में

ब्रांचलेस कोड के बारे में

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

लेकिन आधुनिक CPU तेज़ होते हैं और कई निर्देशों को एक साथ निष्पादित कर सकते हैं। किसी शर्त की रनटाइम जाँच के इंतजार में CPU के रुकने तक सारा काम रोक देना बहुत महँगा पड़ेगा।

इसीलिए अंदरूनी तौर पर CPU इंतजार नहीं करता। वह शर्त के नतीजे का अनुमान लगाने के लिए ब्रांच प्रेडिक्टर का इस्तेमाल करता है और अनुमानित रास्ते पर अनुमान लगाकर निष्पादन शुरू कर देता है।

अगर अनुमान सही होता है, तो निष्पादन ऐसे चलता है जैसे कोई ब्रांच ही न हो। लेकिन अगर अनुमान गलत होता है, तो CPU को अनुमानित रास्ते पर किया गया काम छोड़ देना पड़ता है और सही रास्ते पर फिर से शुरू करना पड़ता है।

इसे ब्रांच मिसप्रेडिक्शन कहते हैं, और यह महँगा पड़ता है; इससे देरी होती है।

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

कोड को ऐसे लिखने के कई तरीके हैं कि वह कम बार ब्रांच करे, या जो ब्रांच करे भी वे ज़्यादा अनुमान-योग्य हों। खास तौर पर, x86-64 में निर्देशों के दो समूह हैं जो ब्रांचलेस कोड लिखने में आम तौर पर इस्तेमाल होते हैं।

कंडीशनल मूव्स

निर्देशों का समूह cmovcc स्रोत ऑपरेंड को गंतव्य में तभी कॉपी करता है जब कोई खास शर्त पूरी होती है। वरना गंतव्य वैसा ही रहता है।

cc प्रत्यय का नामकरण jcc जैसा ही है और उसका अर्थ भी वही है:

नियम jcc जैसे ही हैं:

1. साइन्ड तुलना के लिए l और g इस्तेमाल होते हैं; अनसाइन्ड के लिए b और a।
2. किसी प्रत्यय में e जोड़ने से बराबरी भी शामिल हो जाती है।
3. n जोड़ने से शर्त उलट जाती है।
4. कुछ ऐसे भी रूप हैं जो किसी फ्लैग के सेट होने पर आधारित होते हैं। जैसे cmovz और cmovc।

मान लीजिए rdi में एक साइन्ड पूर्णांक रखा है और हमें उसका निरपेक्ष मान चाहिए, जो rax में लौटाया जाता है। अब इसे jcc से लिखें, तो फंक्शन दो रास्तों में से एक चुनता है:

abs_branch:
    mov rax, rdi
    cmp rax, 0
    jge .done
    neg rax
.done:
    ret

इसे cmovcc से लिखें, तो दोनों संभावित वैल्यू बिना किसी शर्त के हिसाब लगा ली जाती हैं और कंडीशनल मूव उनमें से एक चुन लेता है:

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi
    cmp rdi, 0
    cmovge rax, rdi    ; if rdi >= 0, rax = rdi
                       ; otherwise rax stays = -rdi
    ; now rax = abs(rdi)
    ret

ब्रांचलेस वाला रूप हमेशा वही निर्देश चलाता है। इसमें ऐसा कोई jcc नहीं है जिसका प्रेडिक्टर अनुमान लगाए।

cmovcc का गंतव्य एक रजिस्टर होना चाहिए। स्रोत रजिस्टर या मेमोरी लोकेशन हो सकता है, लेकिन इमीडिएट नहीं।

abs_branchless:
    mov rax, rdi
    neg rax            ; rax = -rdi. `neg` sets SF = 1 if the result is negative
    cmovs rax, rdi     ; if SF = 1 (i.e., rax < 0), replace rax with rdi
                       ; otherwise rax stays = -rdi, which is non-negative
    ; now rax = abs(rdi)
    ret

कंडीशनल सेट

निर्देशों का समूह setcc किसी खास शर्त के पूरा होने पर गंतव्य ऑपरेंड को 1 पर सेट करता है, और वरना 0 पर। गंतव्य हमेशा एक 8-बिट ऑपरेंड होता है।

cc प्रत्यय का नामकरण jcc और cmovcc जैसा ही है। जैसे setz गंतव्य को 1 पर सेट करता है अगर ZF == 1 हो, और वरना 0 पर।

चूँकि गंतव्य 8-बिट होता है, जब ज़्यादा चौड़ी वैल्यू चाहिए तो setcc के बाद movzx लिखना आम बात है:

cmp rdi, rsi
setg al             ; al = 1 if rdi > rsi (signed), 0 otherwise
movzx eax, al       ; eax (and rax) = 1 or 0, with the upper bits cleared

तुलना के नतीजे को पूर्णांक 0 या 1 में बदलने का यह एक आम तरीका है।

ब्रांचलेस कोड कब इस्तेमाल करें

ब्रांचलेस कोड हमेशा ब्रांच वाले कोड से तेज़ नहीं होता। जब किसी ब्रांच का अनुमान आसानी से लग जाता है, तो प्रेडिक्टर लगभग हर बार सही होता है और jcc की कीमत कुछ नहीं के बराबर होती है। ऐसी ब्रांच की जगह लेने वाला ब्रांचलेस कोड धीमा पड़ता है, क्योंकि वह दोनों संभावित गणनाएँ हमेशा करता है।

लूप काउंटर इसका सबसे साफ उदाहरण है। ऐसा फंक्शन लीजिए जो rdi से शुरू होकर rsi 64-बिट पूर्णांकों का जोड़ करता है:

sum_array:
    xor rax, rax
.loop:
    add rax, [rdi]
    add rdi, 8
    dec rsi
    jnz .loop          ; taken on every iteration except the last
    ret

यह ठीक वैसा ही पैटर्न है जिसे ब्रांच प्रेडिक्टर अच्छी तरह सँभाल लेते हैं, इसलिए sum_array चाहे कितने ही एलिमेंट प्रोसेस करे, ब्रांच की कीमत लगभग शून्य ही रहती है।

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