शेयर, मछली, जल्दी और पूरी तरह से

डिवीजन आधुनिक प्रोसेसर में सबसे महंगा संचालन में से एक है। आपको प्रमाण के लिए बहुत दूर नहीं जाना पड़ेगा: एग्नर फॉग [ 1 ] का प्रसारण है कि इंटेल / एएमडी प्रोसेसर पर हम आसानी से 25-119 घड़ी चक्रों में लेटेंसी प्राप्त कर सकते हैं, और पारस्परिक थ्रूपुट - 25-120। रूसी में अनुवादित - धीमी ! फिर भी, आपके कोड में विभाजन निर्देश से बचने का एक अवसर है। और इस लेख में, मैं आपको बताता हूं कि यह कैसे काम करता है, विशेष रूप से आधुनिक संकलक में (वे पहले से ही 20 साल से ऐसा करने में सक्षम हैं), और मैं यह भी बताऊंगा कि कैसे प्राप्त ज्ञान का उपयोग कोड को बेहतर, तेज, अधिक शक्तिशाली बनाने के लिए किया जा सकता है।

वास्तव में, मैं इस बारे में बात कर रहा हूं: यदि विभाजक को संकलन चरण में जाना जाता है, तो पूर्णांक विभाजन को गुणा और दाईं ओर एक तार्किक बदलाव के साथ बदलना संभव है (और कभी-कभी आप इसके बिना भी कर सकते हैं - मैं निश्चित रूप से प्रोग्रामिंग भाषा में कार्यान्वयन के बारे में बात कर रहा हूं)। यह बहुत उत्साहजनक लगता है: पूर्णांक गुणन के संचालन और दाईं ओर एक बदलाव, उदाहरण के लिए, इंटेल हैसवेल 5 से अधिक घड़ी चक्र नहीं लेगा। यह केवल यह समझने के लिए बना हुआ है कि, उदाहरण के लिए, पूर्णांक विभाजन को 10 से करके, पूर्णांक गुणन द्वारा समान परिणाम प्राप्त करने के लिए और दाईं ओर एक तार्किक बदलाव कैसे किया जाए? इस सवाल का जवाब समझ के माध्यम से है ... फिक्स्ड प्वाइंट अंकगणित (इसके बाद एफपीए)। थोड़ी सी मूल बातें।

एफपी का उपयोग करते समय, प्रतिपादक (घातांक 2 => संख्या के द्विआधारी प्रतिनिधित्व में बिंदु की स्थिति) को संख्या में नहीं बचाया जाता है (अस्थायी बिंदु अंकगणित के विपरीत, IEE754 देखें), लेकिन इसे कुछ ऐसे माना जाता है जो प्रोग्रामर को ज्ञात मात्रा के लिए सहमत हैं। केवल मंटिसा (दशमलव बिंदु के बाद जो आता है) बरकरार रखा जाता है। एक उदाहरण:

$$

$$0.1 = .0001 1001 1001 1001 (1001) ... एफपी, एक्सप = 0$$

0.1 - बाइनरी नोटेशन में इसका 'अनंत प्रतिनिधित्व' है, जो ऊपर के उदाहरण में कोष्ठक द्वारा इंगित किया गया है - यह हिस्सा समय-समय पर दोहराया जाएगा, 0.1 के बाइनरी एफपी नोटेशन में एक दूसरे का अनुसरण करते हुए।

ऊपर दिए गए उदाहरण में, यदि हम FP नंबर संचय के लिए 16-बिट रजिस्टर का उपयोग करते हैं, तो हम सटीकता खोए बिना ऐसे रजिस्टर में नंबर 0.1 के FP प्रतिनिधित्व को फिट नहीं कर सकते हैं, और यह बदले में उन सभी आगे की गणना के परिणाम को प्रभावित करेगा जिसमें इस रजिस्टर का मूल्य शामिल है।

मान लीजिए कि हमें 16-बिट पूर्णांक A और B का 16-बिट अंश भाग दिया जाता है। A द्वारा B का गुणनफल पूर्णांक वाले भाग में 16 बिट्स के साथ और आंशिक बिट्स में 16 बिट्स के साथ आता है। केवल पूर्णांक भाग प्राप्त करने के लिए, जाहिर है, आपको परिणाम को 16 बिट्स द्वारा दाईं ओर स्थानांतरित करने की आवश्यकता है।

बधाई हो, एफपीए से परिचय समाप्त हो गया है।

हम निम्नलिखित परिकल्पना का निर्माण करते हैं: एक पूर्णांक विभाजन को 10 से करने के लिए, हमें विभाज्य संख्या को 0.1 की संख्या के एफपी प्रतिनिधित्व से गुणा करना होगा, पूर्णांक भाग और द्रव्य को हैट में लेना होगा ... एक मिनट प्रतीक्षा करें ... लेकिन क्या परिणाम सही होगा, और अधिक सटीक रूप से इसका पूर्णांक भाग? - आखिरकार, जैसा कि हम याद करते हैं, हमारी स्मृति में केवल संख्या 0.1 का अनुमानित संस्करण संग्रहीत है। नीचे मैंने नंबर 0.1 के तीन अलग-अलग प्रतिनिधित्व लिखे: नंबर 0.1 का एक असीम रूप से सटीक प्रतिनिधित्व, बिना राउंडिंग के 16 वीं बिट के बाद छंटनी, नंबर 0.1 का प्रतिनिधित्व, और राउंडिंग के साथ 16 वें बिट के बाद छंटनी, नंबर 0.1 का प्रतिनिधित्व।

$$

$$0001 \: 1001 \: 1001 \: 1001 \:। \: 1001 \: 1001 .... - अनंत \: परिशुद्धता \: \: \: \: \: \: \: \: \: \: \: \: \: \। : \: \: \: \: \: \: \: \: \: \: \: \\ ००:०१ \ _: १००१ \: १००१ \: १००१ \: | १: ०० \ _: ०००० .... - truncating \ "| बिना \: गोलाई \ _ 0001 \: 1001 \: 1001 \: 1010 \: = \: 0000 \: 0000 .... - ट्रंकटिंग \: के साथ \: गोलाई \: अप \:$$

आइए हम अनुमान लगाते हैं कि संख्या 0.1 के निरूपण की त्रुटियां:

$$

$$infinity \: परिशुद्धता - truncating \: without \: rounding = 0.6 * 2 ^ {- 16} \\ truncating \: with: \: rounding \: up - infinity \: परिशुद्धता = 0.1 * 2 ^ {14}$$

0.1 के अनुमान द्वारा पूर्णांक भाग को गुणा करने के परिणाम के लिए सटीक पूर्णांक भाग देने के लिए, हमें यह करने की आवश्यकता है:

$$

$$IntegerPart (A * 0.1) = IntegerPart (A * (0.1 + 0.1 * 2 ^ {- 14}),$$

या

$$

$$IntegerPart (A * 0.1) = IntegerPart (A * (0.1 + 0.6 * 2 ^ {- 16})$$

पहली अभिव्यक्ति का उपयोग करना अधिक सुविधाजनक है: जब $$$0.1 * 2 ^ {-14} * ए <0.1$ हमें हमेशा पहचान मिलती है (लेकिन, आपको ध्यान में रखते हुए, इस समस्या के ढांचे में सभी निर्णय पर्याप्त से अधिक नहीं हैं)। हल, हम प्राप्त करते हैं $$$A <2 ^ {14}$ । यही है, किसी भी 14-बिट संख्या ए को गुणा करके, 0.1 के प्रतिनिधित्व को गोल करके, हमें हमेशा सटीक पूर्णांक भाग मिलता है, जो कि हम असीम रूप से 0.1 से ए से गुणा करके प्राप्त करेंगे। लेकिन, कन्वेंशन द्वारा, हम 16-बिट संख्या को गुणा कर रहे हैं, जिसका अर्थ है , हमारे मामले में उत्तर गलत होगा और हम 0.1 गुणा करके सरल गुणा पर भरोसा नहीं कर सकते। अब, अगर हम संख्या में 0.1 के 16 बिट्स के एफपी प्रतिनिधित्व को बचा सकते हैं, लेकिन, कहते हैं, 19, 20, तो सब कुछ ठीक होगा। और आखिर हम कर सकते हैं!
हम बाइनरी प्रतिनिधित्व को ध्यान से देखते हैं - 0.1 राउंडिंग के साथ ट्रंकटिंग: उच्चतम तीन बिट्स शून्य हैं, जिसका अर्थ है कि वे गुणा परिणाम (नए बिट्स) में कोई योगदान नहीं करते हैं।
नतीजतन, हम अपने नंबर को बाईं ओर तीन बिट्स, राउंड अप और दाईं ओर गुणन और तार्किक शिफ्ट करने के बाद, पहले 16 से और फिर 3 (यानी, आमतौर पर 19 से एक बार में बोलकर) कर सकते हैं - हमें वांछित, सटीक पूर्णांक भाग मिलता है। । इस तरह के '19' बिट गुणा की शुद्धता का प्रमाण पिछले एक के समान है, एकमात्र अंतर यह है कि यह 16-बिट संख्याओं के लिए सही ढंग से काम करता है। इसी तरह की तर्क भी अधिक क्षमता की संख्या के लिए सच है, और न केवल 10 से विभाजन के लिए।

इससे पहले, मैंने लिखा है कि, आम तौर पर बोलते हुए, आप बिना किसी बदलाव के खुद को गुणा करने के लिए सीमित कर सकते हैं। कैसे? असेम्बलर x86 / x64 ड्रम पर:
आधुनिक प्रोसेसर में, एक MUL कमांड होता है (IMUL, MULX - BMI2 के भी एनालॉग होते हैं), जो कि एक, 32/64-बिट पैरामीटर कहता है, 64/128 बिट गुणा करने में सक्षम है, जिसके परिणामस्वरूप दो रजिस्टरों में भागों की बचत होती है (उच्च 32/64 बिट्स) और युवा, क्रमशः):

MUL RCX ;  RCX  RAX,   (128 )   RDX:RAX 

कुछ पूर्णांक 62-बिट A को RCX रजिस्टर में संग्रहित किया जाए, और 64-बिट FA प्रतिनिधित्व को राउंडिंग नंबर 0.1 से राउंडिंग करते हुए RAX रजिस्टर (सूचना में कोई बदलाव नहीं होने पर) संग्रहीत किया जाए। 64-बिट गुणन पूरा करने के बाद, हम पाते हैं कि परिणाम के उच्चतम 64 बिट्स को आरडीएक्स रजिस्टर में संग्रहीत किया जाता है, या, अधिक सटीक रूप से, पूर्णांक भाग, जो 62 बिट संख्या के लिए सटीक होगा। यही है, दाईं ओर शिफ्ट (SHR, SHRX) की जरूरत नहीं है। इस तरह की पारी की उपस्थिति प्रोसेसर की पाइपलाइन को लोड करती है, भले ही यह OOOE का समर्थन करता है या नहीं: कम से कम इस तरह की निर्भरता (उर्फ निर्भरता श्रृंखला) की सबसे अधिक संभावना पहले से ही लंबी श्रृंखला में एक अतिरिक्त निर्भरता है। और यहाँ, यह उल्लेख करना बहुत महत्वपूर्ण है कि आधुनिक संकलक, फॉर्म__टाइगर / 10 की अभिव्यक्ति को देखते हुए, स्वचालित रूप से विभाज्य संख्याओं की पूरी श्रृंखला के लिए कोडांतरक कोड उत्पन्न करते हैं। यही है, यदि आप जानते हैं कि आपके पास हमेशा 53-बिट संख्या है (यह ठीक इसी तरह से मेरे काम में था), तो आपको अभी भी अतिरिक्त बदलाव का निर्देश मिलता है। लेकिन, अब जब आप समझते हैं कि यह कैसे काम करता है, तो आप संकलक की दया पर भरोसा किए बिना, विभाजन को आसानी से गुणा के साथ बदल सकते हैं। वैसे, C ++ कोड में 64-बिट उत्पाद के उच्च बिट्स को mulh जैसी चीज द्वारा कार्यान्वित किया जाता है, जो कि Asm कोड के अनुसार ऊपर दिए गए {I} MUL {X} निर्देश की पंक्तियों के बराबर होना चाहिए।

शायद अनुबंधों के आगमन के साथ (सी ++ 20 में हम इंतजार नहीं कर रहे हैं) स्थिति में सुधार होगा, और कुछ मामलों में, हम कार पर भरोसा कर सकते हैं! यद्यपि यह C ++ है, प्रोग्रामर यहां सब कुछ के लिए जिम्मेदार है - अन्यथा नहीं।

ऊपर वर्णित तर्क - स्थिरांक के किसी भी भाजक पर लागू होता है, अच्छी तरह से, और नीचे उपयोगी लिंक की एक सूची है:

[१] https://www.agner.org/optimize/instruction_tables.pdf
[२] एगनर फॉग की तुलना में तेजस्वी
[३] इंटेल / एएमडी / एआरएम के लिए अनुकूलन के बारे में उपयोगी जानकारी वाला टेलीग्राम चैनल
[४] पूरी तरह से विभाजन के बारे में, लेकिन अंग्रेजी में