مستوى المقال: محترف. الافتراض إنك مرتاح مع C/C++ وفاهم الحلقات والمصفوفات، وسمعت قبل كده عن خط أنابيب المعالج ولو من بعيد.

ليه فرز المصفوفة بيخلّي نفس الحلقة أسرع 6 مرات؟ توقّع التفرّع

نفس الكود، نفس البيانات، نفس عدد العناصر. تفرز المصفوفة مرة واحدة قبل الحلقة، فالحلقة تطلع أسرع 6 مرات. مفيش سطر اتغيّر جوّه الحلقة. السبب مش في الذاكرة ولا في الكاش بالدرجة الأولى — السبب اسمه توقّع التفرّع (Branch Prediction).

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

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

الفكرة بمثال بسيط: عامل التحويلة على السكة

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

المعالج بيعمل نفس الحكاية بالظبط. الـ if هو التحويلة، والمعالج بيخمّن نتيجتها قبل ما يحسبها فعلاً، ويكمّل شغل على أساس التخمين. ده اللي بيحصل فعلاً جوّه السيليكون، واسمه العلمي التنفيذ التخميني (speculative execution).

التشريح العلمي: خط الأنابيب والتنفيذ التخميني

المعالج الحديث مش بينفّذ تعليمة ويستنّاها تخلص قبل ما يبدأ اللي بعدها. بينفّذ على خط أنابيب (pipeline) من مراحل: جلب، فك تشفير، تنفيذ، وصول للذاكرة، كتابة النتيجة. في أي لحظة فيه 15 لـ 20 تعليمة "طايرة" في الأنبوب على مراحل مختلفة في نفس الوقت.

لمّا يوصل لـ if، هو مش عارف نتيجته لحد ما تتحسب المقارنة في مرحلة متأخرة. لكنه مش بيستنى. بيسأل وحدة توقّع التفرّع: الشرط ده هيطلع صح ولا غلط؟ وياخد بالإجابة ويبدأ ينفّذ التعليمات اللي بعده تخمينًا. لو التخمين طلع صح، مفيش وقت ضائع خالص. لو غلط، لازم يرمي كل الشغل التخميني، يفضّي الأنبوب (pipeline flush)، ويبدأ من الفرع الصح. التكلفة على معالجات x86 الحديثة حوالي 15 لـ 20 دورة لكل غلطة توقّع، حسب دليل Agner Fog لبنية المعالجات.

إزاي المعالج بيتعلّم يخمّن؟

أبسط متنبّئ عملي هو عدّاد التشبّع ثنائي البت (2-bit saturating counter). لكل فرع عنده حالة من أربعة: مأخوذ بقوة، مأخوذ بضعف، غير مأخوذ بضعف، غير مأخوذ بقوة. كل مرة الفرع بيتاخد، الحالة بتزحف ناحية "مأخوذ"، ولو مااتخدش بتزحف للعكس. القرار بيتاخد حسب الحالة الحالية. الميزة إن غلطة واحدة شاذّة مابتقلبش التوقّع فورًا، فالنمط المنتظم بيفضل متوقَّع صح.

على بيانات مرتّبة، الشرط data[i] >= 128 بيفضل غلط لفترة طويلة (النصف الأصغر) ثم صح لفترة طويلة (النصف الأكبر). ده نمط منتظم، فالمتنبّئ بيوصل لدقة أعلى من 98%. على بيانات عشوائية، النتيجة بتتقلّب زي رمي عملة، فالدقة بتنزل لحوالي 50% — أسوأ حالة ممكنة تمامًا.

القياس الفعلي: فرق 6 مرات

ده الكود الكلاسيكي (مأخوذ من أشهر سؤال على Stack Overflow في الموضوع ده). بنجمع القيم الأكبر من 128 في حلقة بتتكرر 100 ألف مرة على مصفوفة 32768 عنصر:

#include <algorithm>
#include <ctime>
#include <cstdio>

int main() {
    const int N = 32768;
    int data[N];
    for (int i = 0; i < N; ++i) data[i] = rand() % 256;

    // std::sort(data, data + N);   // جرّبها مرة بالسطر ده ومرة من غيره

    long long sum = 0;
    clock_t start = clock();
    for (int pass = 0; pass < 100000; ++pass)
        for (int i = 0; i < N; ++i)
            if (data[i] >= 128)      // الشرط اللي بيقرّر السرعة
                sum += data[i];

    double t = (double)(clock() - start) / CLOCKS_PER_SEC;
    printf("time = %.2f s, sum = %lld\n", t, sum);
}

على معالج Core i7 وترجمة بـ -O2، النتيجة النموذجية: مصفوفة غير مرتّبة حوالي 11.54 ثانية، ومصفوفة مرتّبة حوالي 1.93 ثانية. نفس الحلقة، نفس البيانات، فرق 6 مرات تقريبًا — كله جاي من فشل التوقّع مش من أي حاجة تانية.

الحل من غير فرز: شيل الفرع نفسه (branchless)

الفرز مش دايمًا متاح ولا رخيص. بدل ما تفرز، ممكن تشيل الـ if خالص وتحسب النتيجة بعمليات حسابية من غير تفرّع:

for (int i = 0; i < N; ++i) {
    int t = (data[i] - 128) >> 31;   // -1 لو data[i] أصغر من 128، وإلا 0
    sum += ~t & data[i];             // بيجمع من غير أي if
}

هنا مفيش فرع أصلاً يتخمّن، يبقى مفيش فشل توقّع أصلاً. الزمن بيبقى ثابت (حوالي 1.85 ثانية) سواء البيانات مرتّبة أو لأ. المترجمات الحديثة على -O3 بتعمل نفس الحيلة لوحدها بتعليمة cmov أو بالـ vectorization، فياريت تبصّ على الـ assembly في godbolt قبل ما تكتبها بإيدك، عشان ماتتعبش في حاجة المترجم عاملها خلاص.

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

لو عندك حلقة ساخنة بتمر على 200 مليون صف وبتطبّق فلتر قيمته بتعتمد على الداتا (مثلاً عدّ العناصر فوق حد معيّن في محرك تحليلات)، ونسبة فشل التوقّع عندك حوالي 45%، ممكن تكسب من الترتيب أو من الـ branchless تحسّن بين 2x و6x حسب باقي الشغل جوّه الحلقة. القياس عندك هو الحَكَم، مش الرقم النظري.

الـ trade-offs بصراحة

• الفرز: بتكسب توقّع شبه مثالي، بتخسر تكلفة الفرز نفسها O(n log n). مايستحقّش إلا لو الحلقة هتتكرر كتير على نفس البيانات المرتّبة.
• الـ branchless: بتكسب زمن ثابت بلا فشل توقّع، بتخسر إنك بتنفّذ الشغل على كل عنصر من غير تخطّي، وبتخسر شوية من وضوح الكود. لو الفرع أصلاً منتظم (توقّع فوق 95%)، الـ branchless ممكن يطلع أبطأ.
• الاعتماد على المترجم: على -O3 المترجم غالبًا بيحوّلها لـ cmov لوحده. تدخّلك اليدوي ممكن يبقى بلا فايدة أو يمنع تحسين أذكى منك.

متى متشغلش بالك بالكلام ده

لو الفرع منتظم أصلاً (بيروح ناحية واحدة أغلب الوقت)، المتنبّئ بيتعامل معاه بدقة عالية ومفيش مشكلة من الأساس. لو الحلقة باردة (بتتنفّذ مرّات قليلة) أو N صغيّر، الفرق مش هيبان. ولو لسه ماقستش بـ perf وشوفت نسبة فشل توقّع عالية فعلاً، فأي تعديل هنا تحسين أعمى. ابدأ بالقياس دايمًا قبل ما تلمس الكود.

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

شغّل على حلقتك الساخنة الأمر ده وبصّ لنسبة branch-misses:

perf stat -e branches,branch-misses ./your_program

لو النسبة طلعت فوق 5 لـ 10% على حلقة ساخنة، جرّب الترتيب لو ممكن، وإلا حوّلها branchless وقِس تاني. لو النسبة أصلاً أقل من 1%، سيب الحلقة زي ماهي ودوّر على عنق الزجاجة في حتة تانية خالص.

المصادر

• Stack Overflow — Why is processing a sorted array faster than processing an unsorted array? — stackoverflow.com/q/11227809
• Agner Fog — The microarchitecture of Intel, AMD and VIA CPUs — agner.org/optimize
• Wikipedia — Branch predictor — en.wikipedia.org/wiki/Branch_predictor
• Intel 64 and IA-32 Architectures Optimization Reference Manual — intel.com
• Linux perf — perf stat — perfwiki.github.io
• Compiler Explorer (godbolt) للتحقق من توليد cmov — godbolt.org
• مصدر الصور: Wikimedia Commons برخصة CC BY-SA — مخطط خط الأنابيب رباعي المراحل وعدّاد التشبّع ثنائي البت