C++-এ কেন সর্টেড অ্যারে প্রসেস করা আনসর্টেডের চেয়ে দ্রুত?

C++-এ সর্টেড অ্যারে প্রসেস করা আনসর্টেড অ্যারের চেয়ে দ্রুত হয় কারণ ব্রাঞ্চ প্রেডিকশন (Branch Prediction)। কম্পিউটার আর্কিটেকচারে ব্রাঞ্চ প্রেডিকশন নির্ণয় করে যে কোনো কন্ডিশনাল ব্রাঞ্চ (জাম্প) প্রোগ্রামের ইনস্ট্রাকশন ফ্লোতে নেওয়া হবে কিনা।

উদাহরণ:

if (arr[i] > 50) {
    // Operation B
} else {
    // Operation A
}

সর্টেড অ্যারে (১ থেকে ১০০):

1, 2, 3, 4, 5, ..., 50, 51, ..., 100
A, A, A, A, A, ..., A,  B,  B, ..., B
প্রেডিকশন: সঠিক, সঠিক, সঠিক, ..., সঠিক
পাইপলাইন: সুষ্ঠু প্রবাহ, কম মিসপ্রেডিকশন

আনসর্টেড অ্যারে:

5, 51, 6, 90, 4, 49, 60, ...
A,  B, A,  B, A,  A,  B, ...
প্রেডিকশন: ভুল, ভুল, ভুল, ...
পাইপলাইন: বারবার ফ্লশ, বেশি মিসপ্রেডিকশন পেনাল্টি

ব্যাখ্যা

সর্টেড ডেটা: ব্রাঞ্চ প্রেডিক্টর সহজে প্যাটার্ন শিখে (প্রথমে সব A, তারপর সব B)। প্রায় ১০০% সঠিক প্রেডিকশন।
আনসর্টেড ডেটা: প্যাটার্ন র‍্যান্ডম, প্রেডিক্টর ভুল করে, পাইপলাইন ফ্লশ হয়, পারফরম্যান্স কমে।
মডার্ন CPU-তে মিসপ্রেডিকশন পেনাল্টি ১০-২০ সাইকেল হতে পারে।

প্রায়োগিক টিপস:

লুপের ভিতরে কন্ডিশনাল থাকলে, ডেটা সর্ট করে প্রসেস করলে স্পিডআপ পাওয়া যায়।
std::sort O(n log n) — যদি লুপ O(n) হয় এবং বারবার চলে, সর্টিং খরচ বাদ দিয়ে নেট গেইন হতে পারে।
ব্রাঞ্চলেস প্রোগ্রামিং (branchless programming) টেকনিকও ব্যবহার করা যায় (যেমন cmov, লুকআপ টেবিল)।