लूप में 64-बिट काउंटर क्यों तोड़ता है _mm_popcnt_u64 का प्रदर्शन

प्रसिद्ध बग जो आज भी C++ डेवलपर्स को परेशान करता है

2013 में Stack Overflow पर एक प्रश्न आया, जिसने सैकड़ों हज़ारों व्यूज़ प्राप्त किए और C++ ऑप्टिमाइज़रों के बीच एक वास्तविक पंथ को जन्म दिया। यह कुछ इस तरह था: "मैंने लूप काउंटर में int को uint64_t से बदल दिया - और प्रदर्शन 10 गुना गिर गया। क्यों?" इसका उत्तर जादू में नहीं, बल्कि Intel प्रोसेसर के माइक्रोआर्किटेक्चर में छिपा था। 2025 में यह समस्या कहीं नहीं गई है: आधुनिक चिप्स अभी भी डेटा प्रकार के प्रतीत होने वाले हानिरहित प्रतिस्थापन पर "लड़खड़ा" सकते हैं।

आज हम इस विरोधाभास को _mm_popcnt_u64 निर्देश (64-बिट शब्द में एकल बिट्स की गणना) के उदाहरण के साथ समझेंगे, वास्तविक कोड दिखाएंगे जो इस विसंगति से ग्रस्त है, और 2025 में तेज़ और पूर्वानुमानित C++ कोड लिखने के लिए स्पष्ट सिफारिशें देंगे।

समस्या का सार: 32-बिट बनाम 64-बिट काउंटर

एक सरल लूप की कल्पना करें जो 64-बिट पूर्णांकों की एक सरणी में एकल बिट्स (popcount) की संख्या का योग करता है। हम SSE4.2 सेट से इंट्रिन्सिक _mm_popcnt_u64 का उपयोग करते हैं। यहाँ कोड के दो संस्करण हैं - पहला 32-बिट काउंटर के साथ, दूसरा 64-बिट काउंटर के साथ:

#include <cstdint>\n#include <vector>\n#include <nmmintrin.h> // _mm_popcnt_u64 के लिए\n\n// विकल्प 1: 32-बिट काउंटर (तेज़)\nuint64_t popcnt_32bit(const std::vector<uint64_t>& data) {\n    uint64_t result = 0;\n    for (int i = 0; i < data.size(); ++i) {   // int — 32 बिट\n        result += _mm_popcnt_u64(data[i]);\n    }\n    return result;\n}\n\n// विकल्प 2: 64-बिट काउंटर (धीमा)\nuint64_t popcnt_64bit(const std::vector<uint64_t>& data) {\n    uint64_t result = 0;\n    for (uint64_t i = 0; i < data.size(); ++i) { // uint64_t — 64 बिट\n        result += _mm_popcnt_u64(data[i]);\n    }\n    return result;\n}\n

यदि आप Intel प्रोसेसर (जैसे Core i7-13700K या पुराने Haswell पर भी) पर गति मापते हैं, तो अंतर चौंकाने वाला होगा: दूसरा विकल्प 3–10 गुना धीमा हो सकता है। जबकि AMD Ryzen पर ऐसी कोई विसंगति नहीं है - वहाँ दोनों विकल्प समान रूप से तेज़ चलते हैं।

ऐसा क्यों होता है? बुराई की जड़ - झूठी निर्भरता

Intel प्रोसेसर (सबसे आधुनिक तक) पर POPCNT निर्देश में गंतव्य रजिस्टर पर झूठी निर्भरता (false dependency) होती है। औपचारिक रूप से POPCNT आउटपुट रजिस्टर को पूरी तरह से ओवरराइट करता है, लेकिन माइक्रोआर्किटेक्चरल रूप से प्रोसेसर ऐसा व्यवहार करता है जैसे वह लिखने से पहले पुराने परिणाम को पढ़ता है। यह Intel में कार्यान्वयन में एक बग (या विशेषता) है।

अब 64-बिट काउंटर i वाले लूप को देखें। कंपाइलर को काउंटर और POPCNT के मध्यवर्ती परिणामों दोनों को संग्रहीत करने के लिए एक ही रजिस्टर (जैसे, rax) का उपयोग करने के लिए मजबूर किया जाता है। प्रत्येक पुनरावृत्ति निर्भरताओं की एक श्रृंखला बनाती है: अगला POPCNT तब तक शुरू नहीं हो सकता जब तक पिछला पूरा न हो जाए, क्योंकि प्रोसेसर "सोचता है" कि उसे पुराने परिणाम की आवश्यकता है। यह पाइपलाइन को मार देता है।

32-बिट काउंटर के साथ, कंपाइलर विभिन्न रजिस्टरों का उपयोग करता है (जैसे, काउंटर के लिए ecx और परिणाम संचय के लिए rax), और झूठी निर्भरता उत्पन्न नहीं होती है - POPCNT समानांतर में निष्पादित होते हैं।

असेंबली पर विस्तृत विश्लेषण

इसे सत्यापित करने के लिए, आइए देखें कि प्रत्येक संस्करण किसमें संकलित होता है (GCC 13, फ़्लैग -O3 -march=native):

32-बिट काउंटर (तेज़):

.L3:\n    popcnt rcx, QWORD PTR [rdx]   ; rcx में popcnt (स्वतंत्र रजिस्टर)\n    add    rax, rcx                ; संचायक के साथ जोड़ें\n    add    rdx, 8                  ; पॉइंटर शिफ्ट\n    cmp    rdi, rdx                ; तुलना\n    jne    .L3\n

64-बिट काउंटर (धीमा):

.L7:\n    popcnt rax, QWORD PTR [rdx]   ; rax में popcnt — वही जो संचायक के लिए है