ব্রাঞ্চলেস কোড মধ্যে

ব্রাঞ্চলেস কোড সম্পর্কে

কন্ডিশনাল কনসেপ্টটি 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 সেট করে। ডেস্টিনেশন সর্বদা একটি ৮-বিট অপারেন্ড।

cc প্রত্যয়টি jcc ও cmovcc-এর মতো একই নামকরণ অনুসরণ করে। উদাহরণস্বরূপ, ZF == 1 হলে setz ডেস্টিনেশনকে 1 সেট করে, অন্যথায় 0।

যেহেতু ডেস্টিনেশন ৮-বিট, তাই আরও চওড়া মান প্রয়োজন হলে 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 সংখ্যক ৬৪-বিট ইন্টিজার যোগ করে এমন একটি ফাংশন বিবেচনা করুন:

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 যত এলিমেন্টই প্রসেস করুক, ব্রাঞ্চটি কার্যত বিনামূল্যে।

ব্রাঞ্চ অনুমান করা কঠিন হলে, বা ইনপুট নির্বিশেষে সামঞ্জস্যপূর্ণ টাইমিং প্রয়োজন হলে ব্রাঞ্চলেস কোড লাভজনক হয়।