المستوى المطلوب: محترف — المقال ده بيفترض إنك بتعرف assembly تقريبيًا، عارف الفرق بين CPU pipeline و cache، وعندك فضول تفهم ليه نفس الـ loop بياخد 1.93 ثانية مرة و 11.5 ثانية مرة تانية بنفس البيانات وعلى نفس المعالج.
فيه سؤال شهير على Stack Overflow عمره 13 سنة لسه بيتقري كل يوم: "Why is processing a sorted array faster than processing an unsorted array?". الإجابة مش cache locality ولا compiler tricks. الإجابة وحدة صغيرة جوّا الـ CPU اسمها Branch Predictor، ولو فهمت ازاي بتشتغل، هتعرف ليه ترتيب الـ array قبل الحلقة ممكن يخفّض زمن التنفيذ من 11 ثانية لـ 1.9 ثانية على نفس Intel Core i7.
Branch Prediction: السر اللي بيقعد جنب كل if-else في كودك
المشكلة باختصار
المعالج الحديث عنده pipeline طوله 14–20 stage. علشان يفضل مشغول، هو بيتنبأ بنتيجة كل if قبل ما يحسبها فعلاً، ويبدأ ينفّذ الـ instructions اللي ورا الـ branch. لو التنبؤ صح، الكود بيطير. لو غلط، بيعمل pipeline flush ويرمي شغل 15 cycle. لو الـ branch بتاعك عشوائي 50/50، هتدفع التكلفة دي في كل تكرار، وكودك هيبطأ 4–6 أضعاف بدون أي سبب ظاهر في الـ profiler العادي.
مثال للمبتدئ: حارس النادي الذكي
تخيّل بواب نادي بيدخّل الناس بقاعدة: "اللي معاه دعوة بنفسجية يعدّي يمين، اللي معاه أصفر يعدّي شمال". لو في طابور 1000 شخص ودعواتهم متبعترة عشوائي بين البنفسجي والأصفر، البواب لازم يفحص كل واحد لوحده قبل ما يعرف يحرّكه فين، فبيقعد ثانية لكل شخص.
لو نفس الـ 1000 شخص جايين مرتبين — كل أصحاب الدعوة البنفسجية الأول، وبعد كده كل الأصفر — البواب بعد أول 50 شخص هيخمّن: "اللي جاي زيهم، خد يمين على طول". وبعد ما الترتيب يقلب، يكتشف الجديد في 50 شخص ويرجع يطير. ده بالظبط اللي بيعمله Branch Predictor جوّا الـ CPU، لكن في نانوثواني بدل ثواني.
التعريف العلمي
Branch Predictor وحدة hardware جوّا الـ Front-End بتاع المعالج، بتحتفظ بجدول اسمه Branch History Table فيه pattern آخر الـ branches اللي اتنفّذت من نفس العنوان. لمّا توصل instruction من نوع conditional jump، الـ predictor بيتنبأ taken أو not-taken بناءً على الـ pattern المحفوظ، والـ pipeline يبدأ يجيب الـ instructions اللي بعدها speculatively.
المعالجات الحديثة (Intel من Skylake فما فوق، AMD Zen 3+) بتستخدم خوارزميات من عيلة TAGE-SC-L اللي بتوصل لدقة 96–98% في الكود العادي. المشكلة بتظهر لمّا الـ branch يكون unpredictable، يعني عشوائي بنسبة قريبة من 50/50 — هنا الدقة بتنزل لـ ~50% والكود بيدفع misprediction penalty في كل miss.
الكود اللي يثبت الفرق
#include <algorithm>
#include <chrono>
#include <iostream>
int main() {
const int N = 32768;
int data[N];
for (int i = 0; i < N; i++) data[i] = std::rand() % 256;
// std::sort(data, data + N); // فعّل السطر ده وقارن
auto start = std::chrono::steady_clock::now();
long long sum = 0;
for (int i = 0; i < 100000; i++) {
for (int c = 0; c < N; c++) {
if (data[c] >= 128) sum += data[c];
}
}
auto end = std::chrono::steady_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << "ms\n";
std::cout << "sum = " << sum << "\n";
}
