दो लूपों में ऐरे जोड़ना एक लूप से तेज़ क्यों है: C++ त्रुटियों का विश्लेषण

दो लूपों में ऐरे जोड़ना एक लूप से तेज़ क्यों है? C++ की प्रसिद्ध त्रुटि का विश्लेषण

क्या आपने कभी ऐसा कोड लिखा है जो सहज रूप से सही लगता था, लेकिन धीमा चलता था? और फिर, गलती से एक लूप को दो में विभाजित करने पर, 2-3 गुना तेज़ी मिली? यह एक परिचित दर्द है। Stack Overflow पर एक पौराणिक प्रश्न है, जिसने हज़ारों व्यूज़ और सैकड़ों टिप्पणियाँ एकत्रित की हैं: «Why are elementwise additions much faster in separate loops than in a combined loop?»। आज हम इस घटना को सरल भाषा में, C++ कोड उदाहरणों के साथ और बिना कठिन सिद्धांतों के समझेंगे।

यह जादू नहीं है। यह कैश-मिस (cache misses) है और प्रोसेसर वास्तव में मेमोरी तक कैसे पहुँचता है। यदि आप C++ में कोड लिखते हैं और चाहते हैं कि आपका कोड तेज़ चले — तो ध्यान से पढ़ें। लेख के अंत में — विशिष्ट कार्य सूची (action items) दी गई है जिन्हें अभी लागू किया जा सकता है।

समस्या का सार: दो लूप बनाम एक लूप

कल्पना करें कि हमारे पास दो बड़े ऐरे a और b हैं, और हम प्रत्येक एलिमेंट का जोड़ और फिर गुणा करना चाहते हैं। सहज ज्ञान कहता है: «चलो एक लूप बनाते हैं, ताकि प्रोसेसर को इधर-उधर न भागना पड़े!»।

यह है संयुक्त लूप:

const int N = 1000000;\nfloat a[N], b[N];\n\n// एक लूप — सब कुछ एक साथ करें\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];  // जोड़\n    a[i] = a[i] * 2.0f;  // गुणा\n}

और यह है दो अलग-अलग लूप:

// पहला लूप — केवल जोड़\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] + b[i];\n}\n\n// दूसरा लूप — केवल गुणा\nfor (int i = 0; i < N; ++i) {\n    a[i] = a[i] * 2.0f;\n}

यह मानना तर्कसंगत है कि पहला विकल्प तेज़ होगा: लूप के आयोजन पर कम ओवरहेड। लेकिन व्यवहार में, इसका उल्टा होता है — दूसरा विकल्प अक्सर 2-3 गुना तेज़ होता है। क्यों? कैश-पदानुक्रम की दुनिया में आपका स्वागत है।

कैश-मिस: प्रदर्शन का मुख्य दुश्मन

आधुनिक प्रोसेसर हर बार सीधे RAM तक नहीं पहुँचते। वे कैश का उपयोग करते हैं — एक तेज़ मेमोरी जो सीधे चिप पर स्थित होती है। कैश कई स्तरों (L1, L2, L3) में आता है, और प्रत्येक अगला स्तर धीमा लेकिन बड़ा होता है।

जब आपका कोड डेटा पढ़ता या लिखता है, प्रोसेसर एक पूरा ब्लॉक (cache line) कैश में लोड करता है — आमतौर पर 64 बाइट्स। यदि अगला अनुरोध उसी ब्लॉक में आता है — यह hit (हिट) है। यदि नहीं — miss (मिस), और प्रोसेसर को धीमी RAM से डेटा की प्रतीक्षा करनी पड़ती है। एक मिस की कीमत सैकड़ों क्लॉक साइकिल हो सकती है।

अब हमारे उदाहरण पर वापस आते हैं। संयुक्त लूप में, हम प्रत्येक पुनरावृत्ति पर a[i] और b[i] तक दो बार पहुँचते हैं: पहले पढ़ने के लिए, फिर लिखने के लिए। जब हम a[0] और b[0] के साथ काम कर रहे होते हैं, कैश उनकी cache lines को खींच लाता है। लेकिन अगली पुनरावृत्ति पर, हम a[1] और b[1] पर जाते हैं — यदि डेटा कैश की अलग-अलग पंक्तियों में है, तो मिस हो सकता है। परिणामस्वरूप, हम लगातार मेमोरी को «खींचते» रहते हैं, जिससे कैश को बार-बार रीलोड होना पड़ता है।

दो अलग-अलग लूपों में, सब कुछ अलग है। पहला लूप क्रमिक रूप से a[i] और b[i] को पढ़ता है और परिणाम वापस लिखता है। डेटा रैखिक रूप से जाता है — कैश पूर्वानुमानित है और पूरी तरह से काम करता है (स्थानिक स्थानीयता)। दूसरा लूप फिर से उसी ऐरे a पर जाता है — डेटा पहले से ही L1 कैश में गर्म (hot) है। लगभग कोई मिस नहीं होता।

शीर्ष त्रुटियाँ जो प्रदर्शन को मार देती हैं

त्रुटि #1 — एक लूप में विभिन्न ऐरे के साथ संचालन को मिलाना। यदि आप तर्क को दो पासों में विभाजित कर सकते हैं (विशेषकर यदि डेटा बड़ा है) — तो ऐसा करें। कैश आपको धन्यवाद देगा।

त्रुटि #2 — cache line के आकार को अनदेखा करना। 64 बाइट्स लगभग 16 float या 8 double के बराबर है। यदि आपके ऐरे में अजीब कदम (strides) हैं या आप क्रमिक रूप से इंडेक्स पर नहीं जा रहे हैं, तो आपको निश्चित रूप से कैश-मिस मिलेंगे।

त्रुटि #3