rust - 64-बिट सिस्टम पर रस्ट का 128-बिट पूर्णांक `i128` कैसे काम करता है?




x86-64 bigint (3)

X86_64 पर, -O ध्वज के साथ संकलित, फ़ंक्शन को संभवतः एक स्पष्ट उदाहरण प्रदान करने के लिए

pub fn leet(a : i128) -> i128 {
    a + 1337
}

के लिए संकलित करता है

example::leet:
  mov rdx, rsi
  mov rax, rdi
  add rax, 1337
  adc rdx, 0
  ret

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

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

इस फ़ंक्शन का पैरामीटर 64-बिट रजिस्टरों की एक जोड़ी में पारित किया जाता है, आरएसआई: आरडीआई। परिणाम रजिस्टरों की एक और जोड़ी में वापस किया जाता है, rdx: rax। कोड की पहली दो पंक्तियाँ योग को प्रारंभिक करती हैं।

तीसरी पंक्ति इनपुट के कम शब्द में 1337 जोड़ती है। यदि यह ओवरफ्लो होता है, तो यह सीपीयू के कैरी फ्लैग में 1 ले जाता है। चौथी पंक्ति इनपुट के उच्च शब्द में शून्य जोड़ती है - प्लस 1 अगर यह ले गया है।

आप इसे एक अंकों की संख्या के दो अंकों की संख्या के सरल जोड़ के रूप में सोच सकते हैं

  a  b
+ 0  7
______
 

लेकिन आधार में 18,446,744,073,709,551,616 हैं। आप अभी भी सबसे कम "अंक" जोड़ रहे हैं, संभवत: 1 को अगले कॉलम में ले जा रहे हैं, फिर अगले अंक को ले जा रहे हैं। घटाव बहुत समान है।

गुणन को पहचान (2⁶⁴a + b) (2 +c + d) = 2¹²⁸ac + 2 b (विज्ञापन + bc) + bd का उपयोग करना चाहिए, जहाँ इनमें से प्रत्येक गुणनफल उत्पाद के ऊपरी आधे भाग को एक रजिस्टर में और उत्पाद के निचले आधे हिस्से को लौटाता है एक और। उन कुछ शब्दों को छोड़ दिया जाएगा, क्योंकि 128 वें से ऊपर बिट्स एक u128 में फिट नहीं होते हैं और उन्हें छोड़ दिया जाता है। फिर भी, यह कई मशीन निर्देश लेता है। डिवीजन भी कई कदम उठाता है। एक हस्ताक्षरित मूल्य के लिए, गुणन और विभाजन को अतिरिक्त रूप से ऑपरेंड और परिणाम के संकेतों को बदलने की आवश्यकता होगी। वे ऑपरेशन बहुत कुशल नहीं हैं।

अन्य आर्किटेक्चर पर, यह आसान या कठिन हो जाता है। RISC-V एक 128-बिट अनुदेश-सेट एक्सटेंशन को परिभाषित करता है, हालांकि मेरी जानकारी के लिए किसी ने इसे सिलिकॉन में लागू नहीं किया है। इस विस्तार के बिना, RISC-V वास्तुकला मैनुअल एक सशर्त शाखा की सिफारिश करता है: addi t0, t1, +imm; blt t0, t1, overflow addi t0, t1, +imm; blt t0, t1, overflow

SPARC में x86 के नियंत्रण झंडे की तरह नियंत्रण कोड हैं, लेकिन आपको उन्हें सेट करने के लिए एक विशेष निर्देश, add,cc का उपयोग करना होगा। दूसरी ओर, MIPS आपको यह जांचने की आवश्यकता है कि क्या दो अहस्ताक्षरित पूर्णांकों का योग किसी एक ऑपरेंड से कड़ाई से कम है। यदि ऐसा है, तो इसके अलावा बह निकला। कम से कम आप सशर्त शाखा के बिना कैरी बिट के मूल्य में एक और रजिस्टर सेट करने में सक्षम हैं।

रस्ट में 128-बिट पूर्णांक होते हैं, इन्हें डेटा प्रकार i128 (और अहस्ताक्षरित ints के लिए u128 ) के साथ चिह्नित किया जाता है:

let a: i128 = 170141183460469231731687303715884105727;

Rust इन i128 मूल्यों को 64-बिट सिस्टम पर कैसे काम करता है; जैसे कि यह इन पर अंकगणित कैसे करता है?

चूंकि, जहां तक ​​मुझे पता है, x86-64 सीपीयू के एक रजिस्टर में मूल्य फिट नहीं हो सकता है, तो कंपाइलर किसी भी तरह एक i128 मान के लिए 2 रजिस्टरों का उपयोग करता है? या वे बजाय प्रतिनिधित्व करने के लिए किसी तरह के बड़े पूर्णांक संरचना का उपयोग कर रहे हैं?


कंपाइलर इन्हें कई रजिस्टरों में स्टोर करेगा और जरूरत पड़ने पर उन मूल्यों पर अंकगणित करने के लिए कई निर्देशों का उपयोग करेगा। अधिकांश ISAs में x86 की adc जैसी ऐड-ऑन-कैरी निर्देश है जो विस्तारित-सटीक पूर्णांक जोड़ने / उप करने के लिए इसे काफी कुशल बनाता है।

उदाहरण के लिए, दिया गया

fn main() {
    let a = 42u128;
    let b = a + 1337;
}

संकलक x86-64 के लिए अनुकूलन के बिना संकलन करते समय निम्नलिखित उत्पन्न करता है:
(@PeterCordes द्वारा जोड़ी गई टिप्पणियाँ)

playground::main:
    sub rsp, 56
    mov qword ptr [rsp + 32], 0
    mov qword ptr [rsp + 24], 42         # store 128-bit 0:42 on the stack
                                         # little-endian = low half at lower address

    mov rax, qword ptr [rsp + 24]
    mov rcx, qword ptr [rsp + 32]        # reload it to registers

    add rax, 1337                        # add 1337 to the low half
    adc rcx, 0                           # propagate carry to the high half. 1337u128 >> 64 = 0

    setb    dl                           # save carry-out (setb is an alias for setc)
    mov rsi, rax
    test    dl, 1                        # check carry-out (to detect overflow)
    mov qword ptr [rsp + 16], rax        # store the low half result
    mov qword ptr [rsp + 8], rsi         # store another copy of the low half
    mov qword ptr [rsp], rcx             # store the high half
                             # These are temporary copies of the halves; probably the high half at lower address isn't intentional
    jne .LBB8_2                       # jump if 128-bit add overflowed (to another not-shown block of code after the ret, I think)

    mov rax, qword ptr [rsp + 16]
    mov qword ptr [rsp + 40], rax     # copy low half to RSP+40
    mov rcx, qword ptr [rsp]
    mov qword ptr [rsp + 48], rcx     # copy high half to RSP+48
                  # This is the actual b, in normal little-endian order, forming a u128 at RSP+40
    add rsp, 56
    ret                               # with retval in EAX/RAX = low half result

जहाँ आप देख सकते हैं कि मान 42 rax और rcx में संग्रहीत है।

(संपादक का ध्यान दें: x86-64 C कॉलिंग कन्वेंशन RDX में 128-बिट पूर्णांक लौटाते हैं: RAX। लेकिन यह main मूल्य बिल्कुल नहीं लौटाता है। सभी निरर्थक कॉपी पूरी तरह से अनुकूलन अक्षम करने से है, और यह कि Rust ओवरफ्लो के लिए जाँच करता है। डिबग मोड।)

तुलना के लिए, यहां x86-64 पर रस्ट 64-बिट पूर्णांकों के लिए एएसएम है, जहां किसी भी ऐड-ऑन-कैरी की आवश्यकता नहीं है, प्रत्येक मूल्य के लिए बस एक ही रजिस्टर या स्टैक-स्लॉट है।

playground::main:
    sub rsp, 24
    mov qword ptr [rsp + 8], 42           # store
    mov rax, qword ptr [rsp + 8]          # reload
    add rax, 1337                         # add
    setb    cl
    test    cl, 1                         # check for carry-out (overflow)
    mov qword ptr [rsp], rax              # store the result
    jne .LBB8_2                           # branch on non-zero carry-out

    mov rax, qword ptr [rsp]              # reload the result
    mov qword ptr [rsp + 16], rax         # and copy it (to b)
    add rsp, 24
    ret

.LBB8_2:
    call panic function because of integer overflow

सेटब / परीक्षण अभी भी पूरी तरह से बेमानी है: jc (कूदो अगर सीएफ = 1) बस ठीक काम करेगा।

ऑप्टिमाइज़ेशन सक्षम होने के साथ, रस्ट कंपाइलर ओवरफ्लो के लिए जाँच नहीं करता है + .wrapping_add() तरह काम करता है।


हां, ठीक उसी तरह जिस तरह 32-बिट मशीनों पर 64-बिट पूर्णांक को संभाला जाता था, या 16-बिट मशीनों पर 32-बिट पूर्णांक, या 8-बिट मशीनों पर 16- और 32-बिट पूर्णांक (अभी भी माइक्रोकंट्रोलर पर लागू होते हैं)! )। हां, आप संख्या को दो रजिस्टरों, या मेमोरी स्थानों, या जो कुछ भी (यह वास्तव में कोई फर्क नहीं पड़ता) में संग्रहीत करते हैं। जोड़ और घटाव तुच्छ होते हैं, दो निर्देश लेते हैं और कैरी फ्लैग का उपयोग करते हैं। गुणन के लिए तीन गुणा और कुछ परिवर्धन की आवश्यकता होती है (यह 64-बिट चिप्स के लिए पहले से ही 64x64-> 128 गुणा ऑपरेशन है जो दो रजिस्टरों के लिए आउटपुट के लिए सामान्य है)। डिवीजन ... एक सबरूटीन की आवश्यकता होती है और यह काफी धीमा होता है (कुछ मामलों को छोड़कर जहां एक स्थिर द्वारा विभाजन को शिफ्ट या गुणा में बदला जा सकता है), लेकिन यह अभी भी काम करता है। बिटवाइज़ और / या / एक्सआर को केवल ऊपर और नीचे के हिस्सों में अलग-अलग करना होता है। शिफ्ट को रोटेशन और मास्किंग के साथ पूरा किया जा सकता है। और यह बहुत ज्यादा चीजों को कवर करता है।





llvm-codegen