المستوى المطلوب: محترف — المقال ده بيفترض إنك بتعرف 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";
}

على Intel Core i7-11700K مع g++ -O0 (بدون optimizations علشان الـ compiler ميقلبهاش cmov):

• بدون std::sort: 11,540ms — الـ predictor بيخسر ~48% من تنبؤاته.
• بعد std::sort: 1,930ms — الـ predictor بيدخل في streak ويوصل لدقة ~99%.
• الفرق: 5.98× أسرع رغم إن عدد الـ instructions اللي بتتنفّذ هو نفسه بالظبط.

شغّل الكود بـ perf stat -e branch-misses,branches ./a.out هتلاقي عدد الـ misses قافز من ~3 مليون في الـ sorted لـ ~1.6 مليار في الـ unsorted. ده الرقم اللي بيكلّفك التسع ثواني الزيادة، وده الرقم اللي مش هيظهرلك في أي flame graph عادي.

الحل البديل: branchless code

بدل ما تعتمد على الـ predictor، اكتب الـ inner loop بدون branches أصلاً:

int t = (data[c] - 128) >> 31;   // 0 لو >= 128، -1 غير كده
sum += ~t & data[c];              // مفيش if خالص

الكود ده بيمشي في 2,100ms على نفس الـ CPU بغض النظر عن ترتيب البيانات. الـ compiler الحديث (GCC 13 مع -O3) بيعمل نفس التحويل تلقائيًا باستخدام تعليمة cmov الـ conditional move، فلو شغّلت الـ optimizations الفرق بين sorted و unsorted ممكن يختفي تمامًا — وده طريقة سريعة تتأكد إن المشكلة فعلاً branch prediction وليس حاجة تانية.

الـ Trade-offs اللي لازم تعرفها

• Branchless بيكسب 5–6× في hot loops، لكن بيخسر قابلية القراءة. مهندس Junior ممكن يقعد ربع ساعة يفهم الـ bit trick.
• الفرز قبل الـ loop بياخد O(n log n). لو هتمر على البيانات مرة واحدة بس، الفرز نفسه أغلى من كل الـ branch misses مجتمعة.
• تعليمات Hint زي __builtin_expect في GCC/Clang بتدّي إشارة للـ predictor، لكن أثرها محدود لأن TAGE الحديث أذكى من أي تخمين يدوي في 90% من الحالات.
• Spectre و Meltdown استغلوا speculative execution نفسه. أي mitigation للـ branch prediction (مثل retpoline) بتكلّف 5–30% perf على workloads معينة، خصوصًا في الـ syscalls.

سيناريو واقعي

لو عندك خدمة بتحلّل لوجات JSON بمعدّل 80 ألف سطر/ثانية، وفيها if (record.level == "ERROR") داخل الـ hot path، ولوجاتك العادية فيها 0.5% أخطاء فقط، الـ predictor هيوصل دقة 99.5% طبيعي وأنت مش محتاج تعمل حاجة. لكن لو فجأة ضربتك موجة أخطاء 50% (incident)، نفس الـ if ده هيبدأ يكلّفك ضعف زمن المعالجة في أسوأ توقيت ممكن. ده درس عملي: branch prediction بتاع الكود بيعتمد على شكل البيانات الإنتاجية، مش على شكلها في الـ benchmark.

متى لا تستخدم هذه الأفكار

أغلب الكود مش حساس للـ branch prediction. لو الـ profiler بيقولك إن الـ bottleneck في DB query أو network call، تجاهل الموضوع كله. branchless tricks مكانها في الـ hot loops اللي بتتنفّذ بلايين المرات: ضغط فيديو، DSP، game engines، interpreters، crypto، database scans. لو الكود بتاعك بيمشي مرة كل ثانية، الفرق بين 2ms و 12ms مش هيظهر لمستخدمك أبدًا، والوقت اللي هتضيّعه في فهم الـ bit tricks أغلى من أي مكسب.

الخطوة التالية

افتح أحرّ loop عندك، ولفّه بـ perf stat -e branches,branch-misses على لينكس أو Instruments > Counters على macOS. لو نسبة الـ misses أعلى من 5%، عندك مساحة تحسين فعلية. ابدأ بمحاولة فرز البيانات لو طبيعتها تسمح، وبعدها فكّر في branchless فقط لو الفرز نفسه أغلى من المكسب.

المصادر

• Mysticial, "Why is processing a sorted array faster than processing an unsorted array?", Stack Overflow, 2012 — stackoverflow.com/questions/11227809
• Agner Fog, "The microarchitecture of Intel, AMD and VIA CPUs", 2024 edition — agner.org/optimize/microarchitecture.pdf
• Seznec & Michaud, "A case for (partially) TAgged GEometric history length branch prediction", JILP 2006.
• Intel® 64 and IA-32 Architectures Optimization Reference Manual, Section 3.4.1 — Branch Prediction.
• Linux perf documentation — counters branch-misses و branches.
• Kocher et al., "Spectre Attacks: Exploiting Speculative Execution", IEEE S&P 2019.