performance - बलर - क्या तीसरे का उपयोग किये बिना दो चरों को स्वैप करने का कोई बिंदु है?




टाइप्स ऑफ़ असेम्बलर (4)

मुझे पता नहीं है कि उनका उपयोग न करें, लेकिन तीसरे उपयोग किए बिना दो चर को स्वैप करने की तकनीकें हैं, जैसे कि

x ^= y;
y ^= x;
x ^= y;

तथा

x = x + y
y = x - y
x = x - y 

कक्षा में प्रोफेसर ने उल्लेख किया कि ये 20 साल पहले लोकप्रिय थे जब स्मृति बहुत सीमित थी और आज भी उच्च प्रदर्शन अनुप्रयोगों में उपयोग की जाती है। क्या ये सच है? मेरी समझ यह है कि इस तरह की तकनीकों का उपयोग करना व्यर्थ क्यों है:

  1. यह तीसरे चर का उपयोग कर बाधा कभी नहीं हो सकता है।
  2. वैसे भी अनुकूलक यह करता है।

तो क्या तीसरे चर के साथ स्वैप न करने का कोई अच्छा समय है? क्या यह कभी तेज़ है?

एक-दूसरे की तुलना में, वह तरीका है जो XOR बनाम विधि का उपयोग करता है जो +/- तेज़ का उपयोग करता है? अधिकांश आर्किटेक्चर में अतिरिक्त / घटाव और एक्सओआर के लिए एक इकाई होती है, तो इसका मतलब यह नहीं होगा कि वे सभी एक ही गति हैं? या सिर्फ इसलिए कि एक सीपीयू के ऑपरेशन के लिए एक इकाई है इसका मतलब यह नहीं है कि वे सभी एक ही गति हैं?


इन तकनीकों को प्रोग्रामर के बारे में जानना अभी भी महत्वपूर्ण है जो आपकी औसत वाशिंग मशीन के फर्मवेयर लिखते हैं या फिर। उस तरह के हार्डवेयर के बहुत सारे अभी भी Z80 CPUs या इसी तरह से चलते हैं, अक्सर 4K से अधिक स्मृति या उससे अधिक नहीं। उस दृश्य के बाहर, इस तरह के एल्गोरिदमिक "ट्रिकरी" को जानना, जैसा कि आप कहते हैं, उतना ही वास्तविक व्यावहारिक उपयोग नहीं है।

(हालांकि मैं टिप्पणी करना चाहता हूं कि फिर भी, प्रोग्रामर जो इस तरह की चीजों को याद करते हैं और जानते हैं, अक्सर "नियमित" अनुप्रयोगों के लिए बेहतर "प्रोग्रामर" के लिए बेहतर प्रोग्रामर बन जाते हैं जो परेशान नहीं होंगे। निश्चित रूप से क्योंकि बाद में अक्सर लेते हैं "स्मृति अब तक काफी बड़ी है" का रवैया बहुत दूर है।)


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

यदि कार्यकारी रजिस्टर में कोई मूल्य है और इसकी सामग्री को रैम के साथ स्वैप करना आवश्यक है, तो इसका विकल्प:

xorwf other,w  ; w=(w ^ other)
xorwf other,f  ; other=(w ^ other)
xorwf other,w  ; w=(w ^ other)

होने वाला

movwf temp1     ; temp1 = w
movf  other,w   ; w = other
movwf temp2     ; temp2 = w
movf  temp1,w   ; w = temp1 [old w]
movwf other     ; other = w
movf  temp2,w   ; w = temp2 [old other]

तीन निर्देश और कोई अतिरिक्त भंडारण, छः निर्देश और दो अतिरिक्त रजिस्ट्रार बनाम।

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

subwf other,w    ; w = other-w
btfss STATUS,C   ; Skip next instruction if carry set (other >= W)
 subwf other,f   ; other = other-w [i.e. other-(other-oldW), i.e. old W]

मुझे यकीन नहीं है कि कितने अन्य प्रोसेसर के पास एक घटाना निर्देश है लेकिन कोई विनाशकारी तुलना नहीं है, लेकिन इस तरह के प्रोसेसर पर चाल जानने के लिए एक अच्छा हो सकता है।


बेशक यह अभी भी जानना उपयोगी है। विकल्प क्या है?

c = a
a = b
b = c

तीन संसाधनों के साथ तीन संसाधनों के साथ तीन संसाधनों के साथ तीन संसाधन?

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

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

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


यदि आप दो पूरे शब्दों को स्मृति या दो संपूर्ण रजिस्टरों में बदलना चाहते हैं, तो ये चाल उपयोगी होने की संभावना नहीं है। फिर भी यदि आप के पास कोई फ्री रजिस्ट्रार नहीं है (या मेमोरी-टू-मेमोटी स्वैप के लिए केवल एक नि: शुल्क रजिस्टर है) और कोई "एक्सचेंज" निर्देश उपलब्ध नहीं है (जैसे x86 में दो एसएसई रजिस्ट्रारों को स्वैप करते समय) या "एक्सचेंज" निर्देश बहुत महंगा है (जैसे x86 में रजिस्टर-मेमोरी xchg ) और एक्सचेंज या कम रजिस्टर दबाव से बचना संभव नहीं है।

लेकिन यदि आपके चर एक शब्द में दो बिटफील्ड हैं, तो 3-एक्सओआर दृष्टिकोण का एक संशोधन एक अच्छा विचार हो सकता है:

y = (x ^ (x >> d)) & mask
x = x ^ y ^ (y << d)

यह स्निपेट Knuth की "कंप्यूटर प्रोग्रामिंग की कला" वॉल्यूम से है। 4 ए। सेकंड। 7.1.3। यहां y सिर्फ एक अस्थायी चर है। विनिमय करने के लिए दोनों बिटफील्ड xmask का उपयोग बिटफील्ड का चयन करने के लिए किया जाता है, d बिटफील्ड के बीच दूरी है।

इसके अलावा आप कठोरता प्रमाणों (प्लानरिटी को संरक्षित रखने के लिए) में इस तरह की चाल का उपयोग कर सकते हैं। उदाहरण के लिए इस स्लाइड से क्रॉसओवर गैजेट देखें (पेज 7)। यह प्रोफेसर द्वारा "एल्गोरिदमिक लोअर बाउंड्स" में हाल के व्याख्यान से है। एरिक डेमैन





swap