لماذا يتم معالجة المصفوفة المرتبة بشكل أسرع في C++؟ سر التنبؤ بالتفرع (Branch Prediction)

مقدمة: أحد أكثر الأسئلة غير المتوقعة في عالم C++

تخيل موقفًا: تكتب حلقة بسيطة بلغة C++ تقوم بجمع عناصر مصفوفة كبيرة، ولكن فقط تلك التي تتجاوز حدًا معينًا. تقوم بتشغيل الكود، ويعمل... بشكل طبيعي. ثم تقرر ترتيب المصفوفة مسبقًا وتشغيلها مرة أخرى. وفجأة تلاحظ أن الكود يعمل بشكل أسرع بمقدار 2-3 مرات أسرع! أين الخدعة؟ سحر المترجم؟ خطأ في اختبار الأداء؟

هذا السؤال، الذي طُرح على Stack Overflow منذ أكثر من عشر سنوات، حصد آلاف المشاهدات ولا يزال يثير جدلاً حادًا. اليوم على PythonLib سنقوم بتحليله بدقة، مع أمثلة حقيقية بلغة C++ وغوص عميق في بنية المعالجات الحديثة. ستتعلم ليس فقط لماذا يحدث هذا، ولكن أيضًا كيفية استخدام هذا التأثير لتسريع الكود الخاص بك.

1. إعادة إنتاج الظاهرة: الكود الذي يثير الدهشة

لنكتب برنامجًا بسيطًا يوضح هذا التأثير بوضوح. سنحتاج إلى مصفوفة من 100,000 عدد صحيح. سنملؤها بقيم عشوائية، ثم نقيس وقت جمع جميع العناصر التي تتجاوز 128.

#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <chrono>\n#include <random>\n\nint main() {\n    const int SIZE = 100000;\n    const int THRESHOLD = 128;\n    \n    // إنشاء مصفوفة غير مرتبة\n    std::vector<int> data(SIZE);\n    std::mt19937 rng(42);\n    std::uniform_int_distribution<int> dist(0, 255);\n    for (auto& val : data) {\n        val = dist(rng);\n    }\n\n    // الجمع للمصفوفة غير المرتبة\n    auto start = std::chrono::high_resolution_clock::now();\n    long long sum_unsorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_unsorted += data[i];\n        }\n    }\n    auto end = std::chrono::high_resolution_clock::now();\n    auto time_unsorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "المصفوفة غير المرتبة: " << time_unsorted << " ميكروثانية، المجموع = " << sum_unsorted << std::endl;\n\n    // ترتيب المصفوفة\n    std::sort(data.begin(), data.end());\n\n    // الجمع للمصفوفة المرتبة\n    start = std::chrono::high_resolution_clock::now();\n    long long sum_sorted = 0;\n    for (int i = 0; i < SIZE; ++i) {\n        if (data[i] >= THRESHOLD) {\n            sum_sorted += data[i];\n        }\n    }\n    end = std::chrono::high_resolution_clock::now();\n    auto time_sorted = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();\n    std::cout << "المصفوفة المرتبة: " << time_sorted << " ميكروثانية، المجموع = " << sum_sorted << std::endl;\n\n    std::cout << "التسريع: " << (double)time_unsorted / time_sorted << "x" << std::endl;\n    return 0;\n}

عند الترجمة بدون تحسينات (العلم -O0) سيكون الفرق صغيرًا، ولكن إذا قمت بتفعيل -O2 أو -O3 في GCC/Clang، ستحصل على نتيجة مذهلة: المصفوفة المرتبة تتم معالجتها بشكل أسرع بمقدار 3-6 مرات.

2. تشريح المعالج: من أين يأتي الفرق؟

مفتاح الحل هو آلية تسمى التنبؤ بالتفرع (Branch Prediction). المعالجات الحديثة هي آلات خط أنابيب. فهي لا تنفذ التعليمات واحدة تلو الأخرى، بل تقسمها إلى مراحل (جلب، فك تشفير، تنفيذ، كتابة النتيجة). لمنع توقف خط الأنابيب، يحاول المعالج تخمين أي فرع من الكود (if أو else) سيتم تنفيذه بعد ذلك، ويبدأ في تحميل التعليمات مسبقًا.

في مثالنا، الشرط if (data[i] >= THRESHOLD) هو نقطة تفرع. بالنسبة للمصفوفة المرتبة، يعمل التنبؤ