مستوى المقال: محترف. الافتراض إنك مرتاح مع 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% — أسوأ حالة ممكنة تمامًا.