HI
RU
EN
ES
ZH
FR
DE
PT
AR
परिचय: जादुई संख्या 8192 और आपका धीमा होता कोड
\nक्या आपने कभी देखा है कि आपका C++ कोड, जो 1000 या 10000 तत्वों पर पूरी तरह से काम करता था, अचानक ठीक 8192 पर धीमा होने लगता है? नहीं, यह कंपाइलर का बग नहीं है और न ही प्राचीन प्रोग्रामरों का अभिशाप। यह एक उत्कृष्ट उदाहरण है कि कैसे प्रोसेसर आर्किटेक्चर आपके तेज़ एल्गोरिदम को कछुआ बना सकता है।
\nयह कहानी Stack Overflow पर एक पौराणिक प्रश्न से शुरू हुई: "मेरा प्रोग्राम ठीक 8192 तत्वों पर लूप करते समय धीमा क्यों है?", जिसने हज़ारों व्यूज़ प्राप्त किए और High Performance Computing की दुनिया में एक मीम बन गया। आज, 2025 में, जब प्रोसेसर और भी जटिल हो गए हैं, इस समस्या को समझना सिर्फ एक मज़ेदार तथ्य नहीं है, बल्कि एक वास्तविक कौशल है जो जूनियर डेवलपर को तेज़ कोड लिखने वाले इंजीनियर से अलग करता है।
\nइस लेख में, हम विश्लेषण करेंगे कि आपके प्रोसेसर के अंदर क्या होता है, क्यों आकार 8192 (और इसके गुणज) "रेड ज़ोन" हैं, और ऐसा कोड कैसे लिखें जो किसी भी डेटा पर स्थिर रूप से तेज़ हो। चलिए शुरू करते हैं!
\n\n1. समस्या की शारीरिक रचना: कैश मिस और एसोसिएटिविटी
\nबुराई की जड़ को समझने के लिए, आधुनिक प्रोसेसर की संरचना में झाँकना होगा। सबसे धीमा ऑपरेशन रैंडम एक्सेस मेमोरी (RAM) तक पहुँचना है। पहुँच को तेज़ करने के लिए, प्रोसेसर कैश का उपयोग करता है - एक छोटी लेकिन बहुत तेज़ मेमोरी, जो सीधे चिप पर स्थित होती है।
\n1.1. कैश कैसे काम करता है (बहुत संक्षेप में)
\n- \n
- L1 कैश: सबसे तेज़ और सबसे छोटा (~32 KB प्रति कोर)। \n
- L2 कैश: थोड़ा धीमा, लेकिन बड़ा (~256-512 KB)। \n
- L3 कैश: सभी कोर के लिए साझा, सबसे बड़ा (कई MB)। \n
कैश में डेटा एक बाइट से नहीं, बल्कि ब्लॉकों में लोड होता है - कैश-लाइनें (आमतौर पर 64 बाइट्स)। यदि प्रोसेसर ऐसे डेटा का अनुरोध करता है जो कैश में नहीं है, तो कैश मिस होता है, और उसे RAM से लोड होने तक प्रतीक्षा करनी पड़ती है। इसमें सैकड़ों क्लॉक साइकिल लग सकती हैं।
\n\n1.2. 8192 का अभिशाप: कैश की एसोसिएटिविटी
\nकैश सिर्फ एक बड़ी टोकरी नहीं है। इसे सेट में व्यवस्थित किया जाता है। प्रत्येक मेमोरी एड्रेस को इनमें से केवल एक सेट में रखा जा सकता है। इसे सेट-एसोसिएटिव कैश कहा जाता है।
\nएक पार्किंग की कल्पना करें जहाँ स्थानों को पंक्तियों में समूहित किया गया है। आपकी कार (मेमोरी एड्रेस) केवल एक विशिष्ट पंक्ति (सेट) में पार्क की जा सकती है। यदि उस पंक्ति के सभी स्थान भरे हुए हैं, तो आपको जगह खाली करने के लिए एक कार को बाहर निकालना होगा (कैश-लाइन को हटाना)।
\nकई आधुनिक प्रोसेसरों के लिए, L1 और L2 कैश 8-वे सेट-एसोसिएटिव होते हैं। इसका मतलब है कि प्रत्येक सेट में 8 कैश-लाइनें हो सकती हैं।
\nअब मुख्य बिंदु: कैश-लाइन का आकार 64 बाइट्स (512 बिट) है। यदि आप int (4 बाइट्स) की एक सरणी के साथ काम कर रहे हैं, तो एक कैश-लाइन में 16 तत्व होते हैं।
जब आप दो की घात के बराबर कदम के साथ एक सरणी पर चलते हैं, तो आप जिन तत्वों तक पहुँच रहे हैं, वे सभी कैश के एक ही सेट पर मैप हो सकते हैं। उदाहरण के लिए, यदि आप हर 16वाँ तत्व लेते हैं, तो वे सभी सेट में समान 8 स्लॉट के लिए प्रतिस्पर्धा करेंगे। जब तत्वों की संख्या स्लॉट से अधिक हो जाती है (उदाहरण के लिए, जब आप 8192 तत्वों की सरणी पर चलते हैं, जो एक सेट पर मैप होते हैं), तो कैश लगातार पुराने डेटा को "बाहर फेंकना" और नया डेटा लोड करना शुरू कर देता है। इसे कैश थ्रैशिंग कहा जाता है।
\n8192 = 2^13 है। मेमोरी में डेटा के एक निश्चित लेआउट पर, तत्वों की यह संख्या विशिष्ट L1 कैश (32 KB / 64 बाइट्स = 512 सेट, और 8192 / 16 = 512, जो प्रत्येक सेट पर पूरी तरह से फिट बैठता है) की एसोसिएटिविटी सीमाओं को पूरी तरह से "हिट" करती है।
\n\n2. C++ में समस्या का प्रदर्शन
\nआइए उस कोड को देखें जो इस समस्या को पुन: उत्पन्न करता है। हम विभिन्न चरणों के साथ द्वि-आयामी सरणी को पार करने के समय को मापेंगे।
\n\n#include <iostream>\n#include <vector>\n#include <chrono>\n\nconst int SIZE 
