आईसीसी इस तरीके से इस लूप को अनलॉक क्यों करता है और अंकगणित के लिए ली का उपयोग करता है?

Question

एक std :: unordered_map <> (https://godbolt.org का उपयोग करके) के लिए आईसीसी 17 जेनरेट कोड को देखकर मुझे बहुत उलझन में छोड़ दिया।

मैं इस के लिए उदाहरण के नीचे आसुत:

long count(void** x) 
{ 
    long i = 0; 
    while (*x) 
    { 
    ++i; 
    x = (void**)*x; 
    } 
    return i; 
} 

-O3 ध्वज के साथ आईसीसी 17 के साथ इस संकलन,, निम्नलिखित disassembly की ओर जाता है:

count(void**): 
     xor  eax, eax          #6.10 
     mov  rcx, QWORD PTR [rdi]       #7.11 
     test  rcx, rcx          #7.11 
     je  ..B1.6  # Prob 1%      #7.11 
     mov  rdx, rax          #7.3 
..B1.3:       # Preds ..B1.4 ..B1.2 
     inc  rdx           #7.3 
     mov  rcx, QWORD PTR [rcx]       #7.11 
     lea  rsi, QWORD PTR [rdx+rdx]      #9.7 
     lea  rax, QWORD PTR [-1+rdx*2]      #9.7 
     test  rcx, rcx          #7.11 
     je  ..B1.6  # Prob 18%      #7.11 
     mov  rcx, QWORD PTR [rcx]       #7.11 
     mov  rax, rsi          #9.7 
     test  rcx, rcx          #7.11 
     jne  ..B1.3  # Prob 82%      #7.11 
..B1.6:       # Preds ..B1.3 ..B1.4 ..B1.1 
     ret              #12.10 

स्पष्ट कार्यान्वयन की तुलना में (जो जीसीसी और क्लैंग का उपयोग, ओओ 3 के लिए भी), ऐसा लगता है कि कुछ चीजें अलग-अलग होती हैं:

1. यह लूप को अनलॉक करता है, वापस लूपिंग से पहले दो कमी के साथ - हालांकि, इसके बीच में एक सशर्त कूद है।
2. यह गणित से कुछ के लिए ली का उपयोग करता
3. यह जबकि पाश के हर दो पुनरावृत्तियों के लिए एक काउंटर (इंक RDX) रहता है, और तुरंत
(Rax और RSI में) हर यात्रा के लिए इसी काउंटरों की गणना करता है

यह सब करने के संभावित लाभ क्या हैं? मुझे लगता है कि शेड्यूलिंग के साथ ऐसा कुछ हो सकता है?

count(void**): 
     mov  rdx, QWORD PTR [rdi] 
     xor  eax, eax 
     test rdx, rdx 
     je  .L4 
.L3: 
     mov  rdx, QWORD PTR [rdx] 
     add  rax, 1 
     test rdx, rdx 
     jne  .L3 
     rep ret 
.L4: 
     rep ret 

Answer 1

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

---

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

असल में आईसीसी ने इस लूप को अनलॉक करने में एक खराब काम किया है।i को संभालने के लिए एलआईए और एमओवी का उपयोग करने का तरीका सुंदर ब्राइंडेड है, क्योंकि यह दो inc rax निर्देशों से अधिक यूपीएस का उपयोग करता है। (हालांकि यह महत्वपूर्ण पथ को कम करता है, आईवीबी पर और बाद में शून्य-विलंबता mov r64, r64 है, इसलिए उन यूपीएस चलाने पर आउट ऑफ़ ऑर्डर निष्पादन आगे बढ़ सकता है)।

बेशक, चूंकि पॉइंटर-पीछा की विलंबता पर इस विशेष पाश की बाधाओं के बाद, आप प्रति 4 घड़ियों (स्काइलेक पर एल 1 भार-उपयोग विलंबता, पूर्णांक रजिस्टरों के लिए) का एक लंबे-श्रृंखला श्रृंखला का सर्वोत्तम अनुभव कर रहे हैं, या अधिकांश 5 इंटेल माइक्रोआर्किटेक्चर पर 5 घड़ियों में से एक। (मैंने इन विलंबों को दोबारा जांच नहीं किया; उन विशिष्ट संख्याओं पर भरोसा न करें, लेकिन वे सही हैं)।

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

एक छोटी श्रृंखला के लिए, बाहर के आदेश निष्पादन सक्षम हो सकता है पाश के बाद कुछ चल रहा है पर आरंभ करने के लिए, अगर पाश निकास शाखा सही ढंग से भविष्यवाणी की है। उस स्थिति में, लूप अनुकूलित करने के लिए उपयोगी है।

अनलॉकिंग समस्या पर अधिक शाखा-पूर्वानुमानकर्ता प्रविष्टियां भी फेंकता है। एक लूप-एक्जिट शाखा के बजाय एक लंबे पैटर्न के साथ (उदाहरण के लिए 15 ले जाने के बाद नहीं लिया गया), आपके पास दो शाखाएं हैं। उसी उदाहरण के लिए, जो कभी नहीं लिया जाता है, और जो 7 बार लेता है तो 8 वें समय नहीं लिया जाता है।

---

यहाँ क्या एक हाथ से लिखा unrolled-दर-दो कार्यान्वयन लग रहा है की तरह:

निकास बिंदुओं में से एक के लिए पाश-बाहर निकलने के रास्ते में i ऊपर फिक्स, ताकि आप इसे सस्ते में संभाल कर सकते हैं लूप के अंदर।

count(void**): 
    xor  eax, eax    # counter 
    mov  rcx, QWORD PTR [rdi] # *x 
    test  rcx, rcx 
    je  ..B1.6 
.p2align 4 # mostly to make it more likely that the previous test/je doesn't decode in the same block at the following test/je, so it doesn't interfere with macro-fusion on pre-HSW 
.loop: 
    mov  rcx, QWORD PTR [rcx] 
    test  rcx, rcx 
    jz  .plus1 

    mov  rcx, QWORD PTR [rcx] 
    add  rax, 2 
    test  rcx, rcx 
    jnz  .loop 
..B1.6: 
    ret 

.plus1:   # exit path for odd counts 
    inc  rax 
    ret 

इस पाश शरीर 5 जुड़े हुए डोमेन UOPs करता है तो दोनों टेस्ट/जेसीसी जोड़े वृहद फ्यूज। हैसवेल एक एकल डिकोड समूहों में दो फ्यूजन बना सकता है, लेकिन पहले के CPUs नहीं कर सकते हैं।

जीसीसी का कार्यान्वयन केवल 3 यूओपीएस है, जो सीपीयू की समस्या चौड़ाई से कम है। लूप बफर से जारी छोटे loops के बारे में this Q&A देखें। कोई सीपीयू वास्तव में प्रति घड़ी एक से अधिक शाखाओं को निष्पादित/सेवानिवृत्त नहीं कर सकता है, इसलिए यह जांचना आसानी से संभव नहीं है कि सीपीयू 4 यूपीएस से कम के साथ कैसे लूप जारी करता है, लेकिन स्पष्ट रूप से हैसवेल प्रति 1.25 चक्रों में 5-यूओपी लूप जारी कर सकता है। पहले सीपीयू केवल इसे प्रति चक्र 2 पर जारी कर सकते हैं।

Answer 2

1. कारण है कि यह ऐसा है, के रूप में यह एक स्वामित्व संकलक है करने के लिए कोई निश्चित जवाब नहीं है:

   बस की तुलना के लिए, इस जीसीसी 6.2 द्वारा बनाया गया कोड है। केवल इंटेल जानता है क्यों। उस ने कहा, इंटेल कंपाइलर अक्सर लूप अनुकूलन में अधिक आक्रामक है। इसका मतलब यह नहीं है कि यह बेहतर है। मैंने ऐसी स्थितियों को देखा है जहां इंटेल के आक्रामक इनलाइनिंग ने क्लैंग/जीसीसी की तुलना में खराब प्रदर्शन किया है। उस स्थिति में, मुझे कुछ कॉल साइटों पर स्पष्ट रूप से इनलाइन करना पड़ा। इसी प्रकार, बेहतर प्रदर्शन प्राप्त करने के लिए इंटेल सी ++ में प्रागम्स के माध्यम से अनलॉक करना प्रतिबंधित है।

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

3. मैं वहाँ एक वैकल्पिक लाभ यहाँ है

   नहीं दिख रहा है क्या करने के लिए प्रयोग किया जाता है