नया साल मुबारक हो! मैं क्लासिक प्लॉट का वर्णन करूँगा - सी ++ में लंबे अंकगणित का अनुकूलन कोडांतरक आवेषण का उपयोग करना। हालाँकि, Habré पर यह अभी तक नहीं था, इसलिए कुछ हिचकिचाहट के बाद मैंने इसे यहाँ पोस्ट करने का निर्णय लिया, आप मुझे क्षमा कर देंगे यदि आप खुद एक बार एक ही बात लिख चुके हैं और मुझसे अधिक उन्नत हैं :-)
फ़ील्ड को शून्य * शब्द दें - जन शब्द, int wc - सरणी में शब्दों की संख्या को बिगआईंट वर्ग में एक लंबे पूर्णांक का प्रतिनिधित्व करते हुए घोषित किया जाता है, बाइट्स में शब्द की लंबाई संकलन चरण पर सेट की गई है)। फिर शुद्ध C ++ में जोड़ का कार्यान्वयन इस तरह हो सकता है:
... typedef unsigned int uInt; typedef unsigned long long int uLong; #define MAX_uInt ((uInt)(-1)) #define MUL ((uLong)MAX_uInt)
यह देखा जा सकता है कि C हमारी समस्या को हल करने के लिए बहुत उपयुक्त नहीं है: आप एक ही बार में 8 बाइट्स नहीं जोड़ सकते हैं, क्योंकि एकल अतिप्रवाह बिट के लिए कोई जगह नहीं है।
हम विचार करते हैं कि प्रोसेसर कितने लंबे चक्रों को एक लंबे पूर्णांक के शब्दों की एक सरणी से प्रत्येक 4 बाइट्स जोड़कर खर्च करता है। कुछ इस तरह:
struct timespec t1, t2; BigInt *a = ..., *b = ...;
यहाँ GCC अनुकूलन कुंजी पर प्रगति है:
हम कोडांतरक सम्मिलित का उपयोग करके जोड़ विधि के शरीर को फिर से लिखते हैं:
भविष्य में, मैं तुरंत संकलन परिणाम (uInt int लंबे लंबे int के लिए) लिखूंगा:
... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lahf add $8, %rdx add $8, %rbx sahf loop lo jnc nocarry ...
संक्षेप में यहां क्या हो रहा है: बीएक्स और डीएक्स रजिस्टर में वर्तमान शब्द के संकेत होते हैं, एडीसी एक बहुत ही सुविधाजनक निर्देश है जो स्रोत, रिसीवर और अतिप्रवाह ध्वज को जोड़ता है, आपको क्या चाहिए! lahf और sahf मूल झंडे को बचाते हैं और लोड करते हैं - इन निर्देशों की आवश्यकता है क्योंकि जोड़ने से ओवरफ़्लो ध्वज को रीसेट करता है। लूप के रूप में कई बार यह cx रजिस्टर में करता है।
यह वास्तव में (ईमानदारी से) है जो मैंने पहले लिखा था। यह विकल्प क्रमशः "लंबे संस्करण" में प्रत्येक चार बाइट्स के लिए
3.5 चक्रों के लिए, दोनों संस्करणों में
7 चक्रों के लिए किया जाता है। जीसीसी अभी भी अपने सर्वश्रेष्ठ में है, लेकिन परिणामी कोडांतरक को अभी तक अनुकूलित और अनुकूलित किया जाना है।
।
बुरी अफवाहें लूप स्टेटमेंट के आसपास जाती हैं। आपको इसके बिना प्रयास करना होगा, खासकर जब से इसकी लागत लगभग कुछ भी नहीं है:
... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lahf add $8, %rdx add $8, %rbx sahf dec %rcx jnz lo jnc nocarry ...
परिणाम
5 (2.5) उपाय है! लूप का उपयोग कभी न करें - यह एक पंक्ति बचाता है, लेकिन यह प्रत्येक पुनरावृत्ति पर 2 बोल्ड घड़ी चक्रों के रूप में खर्च करता है।
।
मैं संकेत में वृद्धि से निपटना चाहूंगा - क्या सीएफ (कैरी फ्लैग - "ट्रांसफर", ओवरफ्लो का झंडा) को छूने का कोई तरीका नहीं है? सौभाग्य से, वहाँ है - अंतिम निर्देश एक मेमोरी संदर्भ की गणना करता है और इसे झंडे को छूने के बिना रिसीवर रजिस्टर में डालता है। यहां बताया गया है कि आप इसका उपयोग कैसे बढ़ा सकते हैं:
... clc lo: mov (%rbx), %rax adc %rax, (%rdx) lea 8(%rdx), %rdx lea 8(%rbx), %rbx dec %rcx jnz lo jnc nocarry ...
वास्तव में
lea 8 (% rdx),% rdx
के रूप में ही करता है
$ 8,% rdx जोड़ें
- रजिस्टर करने के लिए शब्द आकार जोड़ता है।
इस विकल्प के लिए, प्रोसेसर
2 घड़ी चक्र (यानी
1 घड़ी चक्र प्रति 4 बाइट्स) खर्च करता है। सच कहूं, तो मुझे इतना समय लगने की उम्मीद नहीं थी।
।
आगे क्या करना है?
SSE , दुर्भाग्यवश, यहाँ सहायक नहीं है: जब तक 64-बिट आर्किटेक्चर का उपयोग किया जाता है, तब तक गैर-विद्यमान पैड
xmm, xmm निर्देश अनिवार्य रूप से माइक्रोइन्स्ट्रक्शंस की एक ही धारा को दो सामान्य परिवर्धन के अनुक्रम के रूप में उत्पन्न करेगा, अतिप्रवाह जोड़ को समानांतर करना असंभव है। बिल्कुल, इसका मतलब है कि हमें एक पंक्ति में दो अतिरिक्त लिखने की ज़रूरत है, एक असेंबलर चक्र को तैनात करना। सुनहरा अनुकूलन चाल।
// WS = 16 ... clc lo: mov (%rbx), %rax adc %rax, (%rdx) mov 8(%rbx), %rax adc %rax, 8(%rdx) lea 16(%rbx), %rbx lea 16(%rdx), %rdx dec %rcx jnz lo jnc nocarry ...
अब एक पुनरावृत्ति
3 चक्रों में की जाती है, जो कि 4 बाइट्स के लिए
0.75 चक्र से मेल खाती है।
हुर्रे! GCC -O2 ने किया 8 बार! आगे सोचने का समय नहीं है! एक बार फिर सभी आगामी के साथ!