बिटसेट के बारे में सवाल करने के लिए

"क्या यह समय नहीं है, मेरे दोस्तों, हमारे लिए विलियम पर झूलने के लिए, आप देखते हैं, हमारे शेक्सपियर? "।

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

आवश्यक नोट - मुझे 4 कीबोर्ड कार्यान्वयन परतें दिखाई देती हैं: 0 - घटना का पता लगाने, 1 - डेटा रीडिंग, 2 - डेटा सफाई और भंडारण, 3 - संदेश पीढ़ी, 4 - ट्रांसकोडिंग, आदि। परत 1 और इसके साथ जुड़ी परत 0 के लिए सबसे आशाजनक मुझे एमके पिन (लोकी वर्ग के आधार पर) के साथ काम करने के लिए एंटोन चिज़ोव टेम्पलेट्स का उपयोग लगता है और, शायद, किसी दिन, परिणामी परिणाम साझा करने में शर्म नहीं आएगी, लेकिन निश्चित रूप से आज नहीं। अब मैं लेयर 2 के बारे में सोच रहा हूं।

आइए हम समस्या को तैयार करते हैं - स्विच के एक निश्चित सेट के बारे में जानकारी संग्रहीत करना आवश्यक है जो दो पूर्वनिर्धारित मूल्यों में से एक लेते हैं - "बंद" और "बंद नहीं"। एक सेट को स्टोर करने के तरीके के रूप में सबसे प्राकृतिक उम्मीदवार बूलियन चर और बिटसेट लाइब्रेरी हैं। चूंकि दक्षता की आवश्यकता एक स्पष्ट अनिवार्यता है, इसलिए इस दृष्टिकोण से मॉड्यूल के कार्यान्वयन का मूल्यांकन करना वांछनीय है।

मेरा पहला विचार स्रोत कोड को देखना था और सब कुछ तुरंत स्पष्ट हो गया, लेकिन उनके साथ एक संक्षिप्त परिचय के बाद, मैंने महसूस किया कि अन्य लोगों के टेम्पलेट्स के बारे में सीखना बहुत दिलचस्प नहीं था (और बहुत उत्पादक नहीं था)। इसके अलावा, स्रोत कार्यान्वयन की प्रभावशीलता का सटीक मूल्यांकन नहीं देते हैं, क्योंकि यह सीधे संकलक के लिए बंद है। वास्तव में, स्रोत पाठ का अभी भी अध्ययन किया जाना था, अन्यथा इसमें परिवर्तन करना एक बहुत लंबी प्रक्रिया बन जाती है (जब तक कि निश्चित रूप से, हम एक निश्चित परिणाम प्राप्त करने में रुचि रखते हैं), लेकिन यह एक अलग पोस्ट के लिए एक विषय है।

इसलिए, "ब्लैक बॉक्स" का अध्ययन करने की तकनीक को अपनाया जाता है - हम इनपुट को कोड के विभिन्न टुकड़े खिलाते हैं और उत्पन्न कोडर पर विचार करते हैं। दुर्भाग्य से, परिचित एवीआर वास्तुकला के लिए पसंदीदा गॉडबॉल्ट साइट का उपयोग करना संभव नहीं है, क्योंकि इस कार्यान्वयन में अध्ययन के तहत कोई पुस्तकालय नहीं है। आप निश्चित रूप से इसे पेन से खींच सकते हैं, लेकिन इस बात की कोई गारंटी नहीं है कि यह सही स्रोत कोड होगा।

इसलिए, हम एक अलग वास्तुकला को देखेंगे। x51 को gcc कंपाइलर के लिए प्रस्तुत नहीं किया गया है, मुझे x86 कभी पसंद नहीं आया, ARM में बहुत सुविधाजनक नहीं है (एक व्यक्ति के लिए) और समझने योग्य असेंबलर, MIPS बहुत विशिष्ट है और बहुत सामान्य नहीं है, सभी प्रकार के SPARCs और भी बदतर हैं (अच्छी तरह से, ठीक है, मैं आपके पसंदीदा आर्किटेक्चर के साथ किसी को भी नहीं जीत सकता हूं) बेहतर नहीं), लेकिन एक महान उम्मीदवार MSP430 है, जो पीडीपी और टीआई के क्रिस्टल स्पष्ट और सुरुचिपूर्ण वास्तुकला पर आधारित था, लेकिन इसे बहुत खराब नहीं किया जा सकता था (हालांकि लोगों ने कोशिश की)। इस वास्तुकला के लिए कई बिट्स का एक पुस्तकालय प्रस्तुत किया गया है, जिससे आप अध्ययन शुरू कर सकते हैं।

आइए शुरू करते हैं, क्योंकि यह शुरुआत से ही तुच्छ नहीं लगता है, जो कि भीड़ की घोषणा के साथ है। तुरंत हम देखेंगे कि भंडारण के लिए मेमोरी को चार-बाइट शब्दों में आवंटित किया गया है, इस तथ्य के बावजूद कि इस वास्तुकला में प्राकृतिक इकाई एक दो-बाइट शब्द है, और बाइट्स के साथ काफी सुविधाजनक और कुशल काम प्रदान किया जाता है, जिससे अजीब घटनाएं होती हैं। आप लेखक को समझ सकते हैं, एक 32-बिट संख्या का कार्यान्वयन हर जगह होना चाहिए और इस पर स्वाभाविक रूप से भरोसा करना चाहिए, लेकिन इस मामले में, 8-बिट बेहतर होगा, और AVR के लिए, 8-बिट एकमात्र उचित समाधान होगा।

एक दिलचस्प सवाल है, लेकिन आप संकलन प्रक्रिया के दौरान वास्तुकला की थोड़ी गहराई कैसे निर्धारित कर सकते हैं, आपको uint8_t_fast के माध्यम से प्रयास करना होगा। हम एक संभावित अनुकूलन पर ध्यान देते हैं और आगे बढ़ते हैं।

स्मृति को आवंटित करने के अलावा, आरंभीकरण ब्याज का है - वैश्विक सेटों के लिए यह मानक तरीके से किया जाता है - मुख्य कॉल करने से पहले शून्य करना, स्थानीय सेटों के लिए भी यह मानक तरीके से किया जाता है, अर्थात, यदि प्रारंभिक मूल्य स्पष्ट नहीं है तो किसी भी तरह से निर्दिष्ट नहीं किया जाता है। खैर, और, हमेशा की तरह, यदि फ़ंक्शन के बाहर एक प्रारंभिक मूल्य के साथ एक स्थिर सेट का वर्णन करना संभव है, तो इसका उपयोग किया जाना चाहिए ताकि अनावश्यक झंडे को चालू न करें और उन पर निष्पादन समय खर्च न करें। लेकिन यहां हमें किसी खुलासे की उम्मीद नहीं थी, हमने सिर्फ सामान्य नियमों की जांच की।

आइए सेट को संशोधित करने के साथ काम करना शुरू करें, जिसके लिए हमने वर्ग कोष्ठक और सेट और रीसेट विधियों को छोड़ दिया है। हम सेट M में तत्व n को सेट करने के लिए इस तरह से कुछ देखने की उम्मीद कर सकते हैं:

M[n / w] |= (1<<(n % w)) 

जहां w आधार तत्व में बिट्स की संख्या है, जो किसी दिए गए आर्किटेक्चर के लिए, सांख्यिकीय रूप से परिभाषित n (उदाहरण के लिए, 4) और शामिल ऑप्टिमाइज़ेशन फॉर्म के कोड की ओर जाता है:

 bis.w #0x0010, m 

वास्तव में, हम खिड़की के ठीक आधे हिस्से में इस तरह के एक कोड को देखते हैं, और यह संभावना नहीं है कि कोई भी गंभीर रूप से यह कहते हुए जोखिम उठाएगा कि एक अधिक प्रभावी समाधान संभव है। लेकिन यह केवल संकेतित स्थितियों के लिए है, एक मनमाने ढंग से n के लिए तस्वीर पूरी तरह से बदल जाती है, तरीकों के लिए हम इसी अपवाद की पीढ़ी के साथ स्वीकार्यता के लिए तर्क की मान्यता का निरीक्षण करते हैं, और कोष्ठक के लिए हम पूरी तरह से अनुमानित अपरिभाषित व्यवहार के साथ अनुमेय सीमा के एक बिट मुखौटा के साथ तर्क के प्रतिबंध को देखते हैं, दोनों ही मामले प्रलेखन के अनुरूप हैं। नकारात्मक मानों को काफी सही तरीके से संसाधित किया जाता है, क्योंकि अनुक्रमित को अहस्ताक्षरित संख्या के रूप में माना जाता है।

हम इस तथ्य पर ध्यान आकर्षित करते हैं कि एक सेट के एक तत्व के लिए निर्दिष्ट मूल्य न केवल 0 और 1 हो सकता है, जैसा कि कोई भी उम्मीद कर सकता है, लेकिन यह भी पूर्णांक है कि कौन सा नियम "इकाई क्या है?" शून्य नहीं ”, यह काफी तार्किक है, लेकिन प्रलेखन में खराब रूप से परिलक्षित होता है। थोड़ा अजीब तरह से किया गया, फिर भी बूलियन मूल्य अधिक प्राकृतिक होंगे, बंद करें और आगे बढ़ें।

सेट के सांख्यिकीय रूप से अनिश्चित तत्व संख्या के मामले के लिए उत्पन्न कोड की तुलना से पता चलता है कि दोनों मामलों में कोड की दक्षता ([] और तरीके) बहुत करीब और छोटी है, क्योंकि मानक पुस्तकालय से एक सबरूटीन को गणना करने के लिए कहा जाता है (1 << n), और यह सबरूटीन शिफ्ट्स 32-बिट नंबर 0x00000001, दो रजिस्टरों में रखा गया। हम इसके स्रोत पाठ को नहीं देख सकते हैं, लेकिन कॉल का बहुत तथ्य दुखद विचारों की ओर जाता है। तथ्य यह है कि विचाराधीन वास्तुकला में पदों की एक मनमानी संख्या के द्वारा बाईं ओर (और कोई अधिकार नहीं है) भी है, जैसा कि सभी (कई) प्यारे एआरएम में है। 1 स्थिति से एक बदलाव होता है (यह अजीब होगा यदि यह बिल्कुल मौजूद नहीं था), 2,3,4 पदों पर शिफ्ट है (लेकिन कमांड में एक संख्या द्वारा सख्ती से तय की गई है, एक पैरामीटर द्वारा नहीं), एक REPT उपसर्ग है (लेकिन निष्पादन गति छोड़ देता है) शुभकामना के लिए)। आप सबसे छोटी इकाई (यह महत्वपूर्ण है, केवल एक इकाई) की पारी को लागू कर सकते हैं, अर्थात्, अपेक्षाकृत कम समय में बिट संख्या से थोड़ा सा मुखौटा प्राप्त कर सकते हैं जैसे कि टेट्रोड का आदान-प्रदान करना, लेकिन यह एक बहुत ही निर्भर हिस्सा होगा और, सामान्य मामले में, यह बेहतर है कि ऐसा न करें।

इसलिए, एक सार्वभौमिक और त्वरित विधि एक सरणी और सूचकांक में बिट मास्क स्टोर करने के लिए होगी, और इस वास्तुकला पर यह बहुत कुशल भी है, कोड फिर इस तरह दिखता है:

 M[n/w] |= BitArray[n %w] 

कोडांतरक प्राप्त करना:

  bis.b BitArray(r0),M(r1) 

चूंकि हम पैटर्न के बारे में बात कर रहे हैं और डब्ल्यू एक बाइट के आकार का एक से अधिक है, इसलिए विभाजन के संचालन को यहां बहुत कुशलता से लागू किया जाता है। हम एक न्यूनतम कार्यान्वित भंडारण तत्व के स्पष्ट लाभ पर ध्यान देते हैं: एक बाइट के लिए, एक बाइट के लिए 8-बाइट सरणी की आवश्यकता होती है, शब्द संगठन के लिए -2 * 16 = 32 बाइट्स, और सभी आवश्यक को संग्रहीत करने के लिए 32 बिट्स के लंबे शब्द के लिए 4 * 32 = 128 बाइट्स। मास्क, यदि परिणाम नहीं बदलता है तो अधिक भुगतान क्यों करें। आइए एक और संभावित अनुकूलन को याद रखें और आगे बढ़ें।

हम एक और तथ्य पर ध्यान देते हैं - एक निर्धारित तत्व के साथ संचालन के बहुत अधिक कुशल कार्यान्वयन संभव हैं यदि लक्ष्य वास्तुकला में एक बिट-चिह्नित मेमोरी क्षेत्र है (यहां फिर से, एआरएम को पहले से खारिज कर दिया गया है), जहां तत्व स्थापना ऑपरेशन आम तौर पर बिटसेटेटर [n] = कद्दू में बदल जाता है 1, जो निरंतर n के लिए एक कोडांतरक कमांड में अनुवाद करता है, लेकिन वहां पहले से ही पर्याप्त प्रभावी बदलाव हैं, इसलिए ऐसा अनुकूलन अधिक अनावश्यक होगा, विशेष रूप से इसकी सीमाओं को ध्यान में रखते हुए। सिद्धांत रूप में, x51 और AVR दोनों में एक समान बिट-एड्रेसिंग क्षेत्र है, लेकिन केवल निरंतर तत्व संख्याओं के लिए प्रभावी कमांड हैं, और सामान्य मामले के साथ, सब कुछ इतना अच्छा नहीं है (स्पष्ट रूप से बुरा)।

ठीक है, अब परिणामी कोड पर एक करीब से नज़र डालें और ध्यान दें कि हम दोहरे शब्दों में सेट को संग्रहीत करने से जुड़ी कलाकृतियों का निरीक्षण करते हैं। एक सेट के एक तत्व को संशोधित करने के संचालन के लिए कंपाइलर कमांड का एक क्रम उत्पन्न करता है जो मेमोरी से संबंधित डबल शब्द को 2 रजिस्टरों में पढ़ता है (मुझे याद है कि हमारे पास 16-बिट रजिस्टर हैं), उन्हें संशोधित करता है और परिणाम वापस मेमोरी में भेजता है। यदि हम केवल एक तत्व को बदलते हैं, तो ऑपरेशन मास्क में 32 संभव में से एक इकाई होगी, शेष शून्य। जब हम एक सांख्यिकीय रूप से परिभाषित तत्व संख्या लागू करते हैं, तो परिणाम को बदलने वाले संचालन को अनुकूलन चरण में बाहर नहीं किया जाना चाहिए। एक नियम के रूप में, ऐसा होता है, लेकिन विभिन्न ऑपरेंड्स के लिए कुछ गलत हो जाता है और फॉर्म का आर्टिफिशियल अंतिम कोड में लीक हो जाता है:

 bic #0,r0 

जो विशेष रूप से मज़ेदार लगता है यदि आप देखते हैं कि रजिस्टर मेमोरी में वापस नहीं लिखा गया है, हालांकि यह पढ़ा गया है। कड़ाई से बोलते हुए, अनुकूलन के परिणाम कहीं भी विनियमित नहीं होते हैं, इसलिए वे कुछ भी हो सकते हैं, और इससे नाराज होने की कोई बात नहीं है, लेकिन वैसे भी, "यह साफ नहीं है कि यह कैसे काम करता है।" यदि हम संकलक के स्रोत कोड पर गंभीरता से विचार नहीं करते हैं तो हम इस प्रक्रिया को सीधे प्रभावित नहीं कर सकते हैं, तो चलिए इसे दरकिनार करते हैं - हम आशावादी को उसके कार्य को सरल बनाने में मदद करेंगे।

वैसे, मैं अभी भी प्रश्न का उत्तर नहीं पा रहा हूं - क्या यह एक स्थैतिक या अपरिभाषित पैरामीटर के खिलाफ संकलन चरण में एक अलग कार्यान्वयन को परिभाषित करने के लिए मैक्रो या टेम्पलेट स्तर पर C ++ में संभव है। अगर किसी को समुराई का तरीका पता है, तो मुझे टिप्पणियों में बताएं, मैंने विवशता की कोशिश की, यह काम नहीं किया।

हम अपना शोध जारी रखते हैं और पाते हैं कि कंपाइलर सेट पर अनियंत्रित रूप से कॉल का अनुकूलन कर रहा है (बेशक, यदि अनुकूलन चालू है), अर्थात, विभिन्न तत्वों की स्थापना / सफाई के आदेश की पूरी तरह से गारंटी नहीं है और स्रोत कोड ऑपरेटरों के आदेश के साथ किसी भी तरह से जुड़ा नहीं है। लेकिन मैं एक अस्थिर सेट बनाने में विफल रहा, शायद मैं कुछ गलत कर रहा हूं? किसी भी स्थानीय अनुकूलन के मामले में, बाहरी फ़ंक्शन के लिए कॉल कंपाइलर को वैश्विक सरणी के लिए सभी तैयार किए गए कार्यों को बाध्य करने के लिए मजबूर करता है, लेकिन यह बहुत मजबूत समाधान है और स्थानीय लोगों के साथ मदद नहीं करता है। ठीक है, वहाँ शायद कुछ भी नहीं है, और आपको बस एक समान सुविधा को ध्यान में रखना है और धारावाहिक इंटरफेस का उपयोग करके धाराओं के बीच जानकारी स्थानांतरित करने के लिए सेट का उपयोग नहीं करना है (अर्थात, उनके सॉफ्टवेयर समकक्षों)।

एक सामान्य निष्कर्ष बनाया जा सकता है: सीमित संसाधनों के साथ आर्किटेक्चर के लिए अपने वर्तमान रूप में बिटसेट का उपयोग स्मृति और रनटाइम दोनों में अत्यधिक लागत के कारण अनुशंसित नहीं किया जा सकता है। एक संभावित संशोधन, जो टिप्पणी के पाठ पर सभी डेटा को ध्यान में रखता है, गितुब पर निहित है, हर कोई इसका उपयोग कर सकता है। इस मॉड के निर्माण का इतिहास जल्द ही हैबे पर पोस्ट किया जाएगा, वहाँ अजीब क्षण थे।

अंत में, एक छोटी सी टिप्पणी - डेटा वेयरहाउस के कार्यान्वयन "हेड-ऑन", यहां तक ​​कि सेट के अनुकूलित संस्करण पर, डेटा मेमोरी के एन / 8 बाइट्स की आवश्यकता होगी (128 स्विच के लिए 16 बाइट्स की आवश्यकता होगी) और हालांकि संचालन के लिए ओ (1) समय की आवश्यकता होगी, गुणक कई इकाइयां होंगी ( और यहां तक ​​कि एमके के 10 या अधिक) चक्र। इसलिए, समस्या की आवश्यकताओं को ध्यान में रखते हुए और कुछ प्रतिबंधों को लागू करते हुए, हम डेटा भंडारण के वैकल्पिक कार्यान्वयन की पेशकश कर सकते हैं।

यदि हम मानते हैं कि किसी भी समय एक से अधिक स्विच बंद नहीं किए जा सकते हैं (जब तक कि बटन को दबाया नहीं जाता है तब तक हम अन्य सभी को अनदेखा करते हैं), तो हम एक बाइट को बायपास कर सकते हैं (बशर्ते कि कोई 256 से अधिक स्विच न हों) और लिखने / पढ़ने में O (1) प्रोसेसर चक्र लगेगा, और गुणक काफी मामूली होगा।

यह दृष्टिकोण एक साथ बंद किए गए n स्विच के बारे में जानकारी का विस्तार और संग्रह करना आसान है, लेकिन आपको n को बहुत बड़ा नहीं बनाना चाहिए, क्योंकि मेमोरी की आवश्यक मात्रा बढ़ जाती है, और उलटा संचालन करने का समय सेट में तत्वों की संख्या में वृद्धि के साथ रैखिक रूप से बढ़ जाता है, हालांकि O (1) द्वारा रहता है स्विच की संख्या के संबंध में। बाइनरी ट्री को O (loq2 (n)) के त्रिकोणीय कार्यान्वयन का उपयोग करके समय में संकेतित वृद्धि को काफी कम किया जा सकता है, लेकिन छोटे n के लिए यह इतना महत्वपूर्ण नहीं है। हां, और यह संदिग्ध है कि खोज के दौरान अगले सूचकांक की गणना की जटिलता सरल पुनरावृत्तियों की संख्या में कमी के लिए क्षतिपूर्ति करेगी। इस कार्यान्वयन के नुकसान में सेट के तत्व को रिकॉर्ड करने में एक संभावित विफलता शामिल है, जिसे कॉलिंग प्रोग्राम में संसाधित किया जाना चाहिए (हम तुरंत बदलते बफर आकार के साथ विकल्प को अस्वीकार करते हैं और आक्रोश के साथ - यह एम्बेडेड समाधानों के लिए नहीं है)।

इस दृष्टिकोण का कार्यान्वयन वहाँ दिया जाएगा।