هذا المقال يتطلب مستوى: متوسط

Branch Prediction: ليه ترتيب البيانات بيخلي نفس الكود أسرع 6 مرات

لو عندك حلقة بتمر على مصفوفة وفيها شرط if، ترتيب البيانات لوحده ممكن يخلي الكود أسرع حوالي 6 مرات. نفس الكود، نفس البيانات، نفس عددها، نفس المعالج. الفرق الوحيد إن المصفوفة مرتّبة. السبب اسمه Branch Prediction، وهنا هتقيسه بنفسك وتعرف تتعامل معه.

المشكلة باختصار

عندك مصفوفة فيها 32 ألف رقم عشوائي بين 0 و255. بتمر عليها في حلقة وتجمع كل رقم أكبر من أو يساوي 128. تكرر العملية 100 ألف مرة عشان الزمن يبقى واضح. لما تشغّل الكود على مصفوفة غير مرتّبة بياخد حوالي 11.5 ثانية. ترتّب نفس المصفوفة قبل الحلقة، فيهبط الزمن لحوالي 1.9 ثانية. الافتراض هنا إن الأرقام دي من تجربة شهيرة على معالج Intel Core i7، وهتختلف عندك حسب جهازك، لكن النسبة هتفضل ضخمة.

مثال يقرّب الفكرة (لو دي أول مرة تسمع عنها)

تخيّل موظف على بوابة حدود. كل سيارة بتوصل، لازم يقرر يفتح الحاجز أو يقفله. لو السيارات بتيجي بترتيب عشوائي تماماً، هو ميقدرش يخمّن، فبيستنى السيارة توصل بالظبط وبعدين يتحرك. كل سيارة بتتأخر.

دلوقتي تخيّل إن السيارات بتيجي مرتّبة: عشر سيارات بيضا ورا بعض، بعدين عشرين سيارة سودا ورا بعض. بعد أول سيارة بيضا، الموظف بيخمّن إن اللي جاية كمان بيضا وبيجهّز الحاجز قبل ما توصل. تخمينه بيطلع صح في كل مرة تقريباً، فالطابور بيمشي بسرعة. أول ما اللون يتغيّر بيتفاجأ مرة واحدة بس، وبعدها يرجع يخمّن صح. ده بالظبط اللي المعالج بيعمله مع شرط if.

اللي بيحصل فعلاً جوه المعالج

المعالج الحديث مبيخلّصش تعليمة قبل ما يبدأ اللي بعدها. بيشتغل بنظام خط أنابيب (pipeline): كذا تعليمة بتكون في مراحل مختلفة في نفس اللحظة. المشكلة عند الـ if: المعالج لازم يعرف هيكمّل في أي فرع قبل ما تتحسب نتيجة الشرط فعلاً.

عشان ميقفش ينتظر، بيستخدم وحدة Branch Predictor. دي بتخمّن نتيجة الشرط بناءً على تاريخ القرارات السابقة، والمعالج يبدأ ينفّذ الفرع المتوقّع تخمينياً (speculative execution). لو التخمين صح، مفيش وقت ضايع. لو غلط، المعالج بيرمي كل الشغل اللي عمله في الأنبوب ويبدأ من الأول من الفرع الصح. الرمية دي ثمنها حوالي 15 إلى 20 دورة معالج في المعمارية الحديثة.

مع المصفوفة المرتّبة، الشرط بيفضل خطأ لمدة طويلة ثم صح لمدة طويلة، فالتخمين بيطلع صح شبه دايماً. مع المصفوفة العشوائية، الشرط بيتقلّب بنسبة حوالي النص، فالتوقّع بيغلط في نص الحالات تقريباً، وكل غلطة بتكلّف العشرين دورة دول.

الكود اللي يوريك الفرق

جرّب الكود ده بنفسك. شغّله مرة والسطر بتاع الترتيب متعلّق عليه كومنت، ومرة وهو شغّال، وقارن الزمن.

#include <algorithm>
#include <cstdlib>
#include <chrono>
#include <iostream>

int main() {
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // std::sort(data, data + arraySize);   // علّق/فعّل السطر ده وقارن

    long long sum = 0;
    auto start = std::chrono::steady_clock::now();

    for (unsigned i = 0; i < 100000; ++i)
        for (unsigned c = 0; c < arraySize; ++c)
            if (data[c] >= 128)
                sum += data[c];

    auto end = std::chrono::steady_clock::now();
    std::chrono::duration<double> elapsed = end - start;

    std::cout << sum << "\n";
    std::cout << elapsed.count() << " s\n";
}

الفرق اللي هتشوفه بين الحالتين هو ثمن التوقّع الخاطئ متراكم على مليارات المرات اللي الشرط اتنفّذ فيها.

إزاي تتعامل معاها

1. رتّب البيانات لو منطقي. لو هتمر على نفس البيانات كذا مرة، الترتيب مرة واحدة بيخلّي التوقّع يطلع صح بعدها.
2. شيل الفرع من أصله (branchless). بدّل الـ if بعملية حسابية متعتمدش على توقّع. مثلاً:

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

الكود ده بيدّي نفس النتيجة من غير أي فرع، فالمعالج مبيحتاجش يخمّن حاجة. هنا الحل غالباً بيقرّب زمن الحالة العشوائية من زمن الحالة المرتّبة.

الـ trade-offs

الترتيب نفسه ثمنه يتناسب مع n log n، فلو هتمر على البيانات مرة واحدة بس، تكلفة الترتيب أكبر من اللي هتوفره. بتكسب توقّع شبه مثالي، بتخسر زمن الترتيب وذاكرة لو نسخت البيانات.

الكود الـ branchless بيكسب ثبات في الزمن بغض النظر عن البيانات، بس بيخسر في القراءة والصيانة. أي حد بيقرأ ~t & data[c] هيحتاج كومنت يفهمه. وكمان المترجمات الحديثة أحياناً بتحوّل الـ if لكود بلا فروع لوحدها، فممكن تتعب على الفاضي.

متى متشغلش بالك بالموضوع ده

لو الشرط بتاعك متوقّع أصلاً (بيرجع نفس النتيجة غالباً)، التوقّع بيطلع صح من غير أي تدخّل منك. ولو الحلقة بتتنفّذ آلاف قليلة من المرات مش مليارات، الفرق هيبقى أصغر من إنك تحس بيه. التحسين ده يستاهل بس في الكود الساخن (hot path) اللي بيتنفّذ ملايين أو مليارات المرات على بيانات غير متوقّعة. قبل ما تعقّد كودك، قيس الأول.

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

افتح أي حلقة ساخنة عندك فيها if جوه تكرار كبير على بيانات عشوائية. انسخ كود القياس فوق وطبّقه على حالتك مرة بترتيب ومرة من غير. لو الفرق كبير، فكّر في الترتيب أو الحل الـ branchless. لو مفيش فرق ملموس، سيبه زي ما هو وركّز على حاجة تانية.

مصادر

• السؤال الشهير على Stack Overflow: Why is processing a sorted array faster than processing an unsorted array? (منه الأرقام 11.5 و1.9 ثانية).
• توثيق Branch predictor على Wikipedia: Branch predictor.
• أدلة تحسين الأداء لـ Agner Fog عن خط الأنابيب وثمن التوقّع الخاطئ: agner.org/optimize.
• التنفيذ التخميني (Speculative execution) على Wikipedia: Speculative execution.