C++ में कैश-फ्रेंडली कोड: यह क्या है और गति के लिए यह क्यों महत्वपूर्ण है

आपका कोड धीमा चल रहा है, हालाँकि एल्गोरिदम आदर्श है? हो सकता है, वह कैश के साथ "दोस्ताना" नहीं है

क्या आपने कभी C++ में ऐसा कोड लिखा है जो सिद्धांत रूप में बिजली की गति से काम करना चाहिए, लेकिन व्यवहार में धीमा चलता है? या क्या आपने देखा है कि द्वि-आयामी ऐरे को पंक्तियों और स्तंभों में ट्रैवर्स करने पर अलग-अलग गति मिलती है, हालाँकि एल्गोरिदम की जटिलता समान है? यदि हाँ, तो आप cache-friendly (कैश-फ्रेंडली) और इसके विपरीत cache-unfriendly कोड से रूबरू हुए हैं।

आज हम समझेंगे कि हार्डवेयर स्तर पर इसका क्या अर्थ है, कैश केवल "एक और मेमोरी" क्यों नहीं है, बल्कि प्रदर्शन की कुंजी है, और ऐसा कोड कैसे लिखें जिसे प्रोसेसर "पसंद" करे। कोई जटिल अमूर्तता नहीं - केवल C++ और स्पष्ट उदाहरण।

प्रोसेसर सीधे RAM से क्यों नहीं पढ़ सकता?

पिछले कुछ दशकों में प्रोसेसर की गति हजारों गुना बढ़ गई है, जबकि RAM (DRAM) की गति केवल दसियों गुना। एक फॉर्मूला-1 रेसर (प्रोसेसर) की कल्पना करें, जिसे हर सेकंड 30 किमी/घंटा की गति से चलने वाले ट्रक (RAM) से ईंधन (डेटा) लेने के लिए रुकना पड़ता है। दुखद और धीमा।

समाधान है प्रोसेसर कैश: एक छोटी लेकिन बहुत तेज़ मेमोरी, जो सीधे चिप में बनी होती है। यह अक्सर उपयोग किए जाने वाले डेटा की प्रतियां संग्रहीत करता है। जब प्रोसेसर को डेटा की आवश्यकता होती है, तो वह पहले कैश (L1 - सबसे तेज़, फिर L2, L3) की जाँच करता है। केवल अगर डेटा वहाँ नहीं है (cache miss, कैश मिस), तो वह धीमी RAM में जाता है।

यहाँ अनुमानित विलंबता (प्रोसेसर चक्रों में) दी गई है:

\n
• L1 कैश: ~3-5 चक्र
\n
• L2 कैश: ~10-20 चक्र
\n
• L3 कैश: ~30-50 चक्र
\n
• RAM: ~100-300 चक्र
\n

L1 और RAM के बीच का अंतर 50-100 गुना है। यही कारण है कि C++ में cache-friendly कोड "अमित्र" समकक्ष की तुलना में कई गुना तेज़ हो सकता है।

लोकैलिटी का सिद्धांत: कैश कैसे तय करता है कि क्या संग्रहीत करना है

कैश एक बाइट कॉपी नहीं करता - यह ब्लॉक (cache lines) में काम करता है, आमतौर पर 64 बाइट्स का। जब आप एक वेरिएबल पढ़ते हैं, तो प्रोसेसर उस वेरिएबल वाले पूरे ब्लॉक को लोड करता है। और वह दो सिद्धांतों पर दांव लगाता है:

\n
• स्पेशियल लोकैलिटी (Spatial locality): यदि आप ऐरे का एक एलिमेंट arr[i] पढ़ते हैं, तो संभवतः आपको जल्द ही arr[i+1] की आवश्यकता होगी।
\n
• टेम्पोरल लोकैलिटी (Temporal locality): यदि आपने अभी डेटा पढ़ा है, तो संभवतः आप निकट भविष्य में फिर से उसी डेटा का उपयोग करेंगे।
\n

Cache-friendly कोड वह कोड है जो इन सिद्धांतों का अधिकतम उपयोग करता है। आइए देखें कि व्यवहार में यह कैसा दिखता है।

उदाहरण 1: द्वि-आयामी ऐरे का ट्रैवर्सल - शैली का क्लासिक

Cache-unfriendly (खराब कोड)

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// स्तंभों के अनुसार ट्रैवर्सल (column-major)\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

C++ में, ऐरे row-major order (पंक्तियों के अनुसार) में संग्रहीत होते हैं। अर्थात, पंक्ति matrix[0][0], matrix[0][1], matrix[0][2]... के एलिमेंट मेमोरी में क्रमिक रूप से स्थित होते हैं। j (स्तंभों) पर बाहरी लूप प्रोसेसर को हर कदम पर पूरी पंक्ति में कूदने के लिए मजबूर करता है - matrix[i][j] तक प्रत्येक पहुँच, सबसे अधिक संभावना है, cache miss है। प्रोसेसर नए ब्लॉक लोड करने में समय बर्बाद करता है, और कैश से पिछला डेटा हटा दिया जाता है।

Cache-friendly (अच्छा कोड)

// पंक्तियों के अनुसार ट्रैवर्सल (row-major)\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

अब हम मेमोरी में क्रमिक रूप से चलते हैं। जैसे ही हमने matrix[0][0] वाला ब्लॉक लोड किया, अगले 15 एलिमेंट (4-बाइट int के साथ) पहले से ही कैश में हैं! इससे गति में 5-10 गुना वृद्धि होती है