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 फ्लैग) के संकलन करने पर अंतर छोटा होगा, लेकिन यदि आप GCC/Clang में -O2 या -O3 चालू करते हैं, तो आपको एक प्रभावशाली परिणाम मिलेगा: सॉर्ट किया गया ऐरे 3-6 गुना तेज़ी से प्रोसेस होता है।

2. प्रोसेसर की शारीरिक रचना: अंतर कहाँ से आता है?

इस रहस्य की कुंजी एक तंत्र है जिसे Branch Prediction (शाखा पूर्वानुमान) कहा जाता है। आधुनिक प्रोसेसर पाइपलाइन मशीनें हैं। वे निर्देशों को एक-एक करके नहीं, बल्कि चरणों (फ़ेच, डिकोड, निष्पादन, परिणाम लिखना) में विभाजित करके निष्पादित करते हैं। पाइपलाइन को निष्क्रिय होने से बचाने के लिए, प्रोसेसर यह अनुमान लगाने का प्रयास करता है कि कोड की कौन सी शाखा (if या else) आगे निष्पादित होगी, और पहले से ही निर्देशों को लोड करना शुरू कर देता है।

हमारे उदाहरण में, शर्त if (data[i] >= THRESHOLD) एक शाखा बिंदु है। सॉर्ट किए गए ऐरे के लिए, पूर्वानुमान काम करता है