Branch Prediction للمتوسط: ليه معالجة مصفوفة مرتّبة أسرع 6 مرات من غير المرتّبة

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

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";
}