जीसीसी अनुकूलन ध्वज -ओ 3 कोड धीमा करता है -ओ 2

Question

मुझे यह विषय Why is it faster to process a sorted array than an unsorted array? मिलता है। और इस कोड को चलाने की कोशिश करें। और मुझे अजीब व्यवहार मिलता है। अगर मैं इस कोड को -O3 अनुकूलन ध्वज के साथ संकलित करता हूं तो इसे चलाने के लिए 2.98605 sec लगता है। अगर मैं -O2 के साथ संकलित करता हूं तो यह 1.98093 sec लेता है। मैं एक ही मशीन पर उसी मशीन पर कई बार (5 या 6) चलाने की कोशिश करता हूं, मैं अन्य सभी सॉफ़्टवेयर (क्रोम, स्काइप इत्यादि) बंद करता हूं।

gcc --version 
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2 
Copyright (C) 2014 Free Software Foundation, Inc. 
This is free software; see the source for copying conditions. There is NO 
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

तो कृपया आप मुझे बता सकते हैं कि ऐसा क्यों होता है? मैंने gcc मैनुअल पढ़ा और मुझे लगता है कि -O3 में -O2 शामिल हैं। मदद के लिए शुक्रिया।

पीएस ऐड कोड

#include <algorithm> 
#include <ctime> 
#include <iostream> 

int main() 
{ 
    // Generate data 
    const unsigned arraySize = 32768; 
    int data[arraySize]; 

    for (unsigned c = 0; c < arraySize; ++c) 
     data[c] = std::rand() % 256; 

    // !!! With this, the next loop runs faster 
    std::sort(data, data + arraySize); 

    // Test 
    clock_t start = clock(); 
    long long sum = 0; 

    for (unsigned i = 0; i < 100000; ++i) 
    { 
     // Primary loop 
     for (unsigned c = 0; c < arraySize; ++c) 
     { 
      if (data[c] >= 128) 
       sum += data[c]; 
     } 
    } 

    double elapsedTime = static_cast<double>(clock() - start)/CLOCKS_PER_SEC; 

    std::cout << elapsedTime << std::endl; 
    std::cout << "sum = " << sum << std::endl; 
} 

Answer 1

gcc -O3 तो यह पाश-जाता निर्भरता श्रृंखला लंबा सशर्त के लिए एक cmov का उपयोग करता है, को शामिल करने के लिए एक cmov (2 UOPs और अपने इंटेल Sandybridge CPU पर विलंबता के 2 चक्र है जो Agner Fog's instruction tables के अनुसार, x86 टैग विकी भी देखें)। यह one of the cases where cmov sucks है।

यदि डेटा भी मामूली अप्रत्याशित था, तो cmov शायद एक जीत होगी, इसलिए यह एक कंपाइलर बनाने के लिए एक काफी समझदार विकल्प है। (हालांकि, compilers may sometimes use branchless code too much।)

आई put your code on the Godbolt compiler explorer एएसएम देखने के लिए (अच्छी हाइलाइटिंग और अप्रासंगिक लाइनों को फ़िल्टर करने के साथ। आपको अभी भी मुख्य(), हालांकि प्राप्त करने के लिए सभी प्रकार के कोड को स्क्रॉल करना होगा।

.L82: # the inner loop from gcc -O3 
    movsx rcx, DWORD PTR [rdx] # sign-extending load of data[c] 
    mov  rsi, rcx 
    add  rcx, rbx  # rcx = sum+data[c] 
    cmp  esi, 127 
    cmovg rbx, rcx  # sum = data[c]>127 ? rcx : sum 
    add  rdx, 4   # pointer-increment 
    cmp  r12, rdx 
    jne  .L82 

जीसीसी एडीडी के बजाय एलआईए का उपयोग करके एमओवी को बचा सकता था।

एडीडी-> सीएमओवी (3 चक्र) की विलंबता पर लूप बाधाएं, चूंकि लूप का एक पुनरावृत्ति सीएमओ के साथ आरबीएक्स लिखता है, और अगला पुनरावृत्ति एडीडी के साथ आरबीएक्स पढ़ता है।

लूप में केवल 8 फ़्यूज्ड-डोमेन यूओएस हैं, इसलिए यह प्रति 2 चक्रों में जारी हो सकता है। निष्पादन-पोर्ट दबाव भी sum डेप चेन की विलंबता के रूप में एक बाधा जितना खराब नहीं है, लेकिन यह करीब है (सैंडब्रिज में केवल 3 एएलयू बंदरगाह हैं, हैसल के 4 के विपरीत)।

बीटीडब्लू, इसे sum += (data[c] >= 128 ? data[c] : 0); के रूप में लिखने के लिए cmov लूप-ले जाने वाली डेप श्रृंखला से बाहर ले जाने के लिए संभावित रूप से उपयोगी है। अभी भी बहुत सारे निर्देश हैं, लेकिन प्रत्येक पुनरावृत्ति में cmov स्वतंत्र है। यह compiles as expected in gcc6.3 -O2 and earlier, लेकिन गंभीर पथ (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82666) पर gcc7 de-cmov में ऑप्ट-इन करता है। (यह भी यह लिखने की if() तरीका से पहले जीसीसी संस्करणों के साथ ऑटो vectorizes।)

बजना भी मूल स्रोत के साथ महत्वपूर्ण मार्ग बंद cmov लेता है।

---

gcc -O2 है, जो अच्छी तरह से भविष्यवाणी की है क्योंकि अपने डेटा सॉर्ट हो जाता है (gcc5.x और बड़ी उम्र के लिए) एक शाखा उपयोग करता है। चूंकि आधुनिक सीपीयू नियंत्रण निर्भरताओं को संभालने के लिए शाखा-भविष्यवाणी का उपयोग करते हैं, इसलिए लूप-संचालित निर्भरता श्रृंखला कम है: केवल add (1 चक्र विलंबता)।

प्रत्येक पुनरावृत्ति में तुलना-और-शाखा स्वतंत्र है, शाखा-भविष्यवाणी + सट्टा निष्पादन के लिए धन्यवाद, जो सुनिश्चित करने के लिए शाखा दिशा से पहले निष्पादन जारी रखने देता है। sum और पाश-काउंटर:

.L83: # The inner loop from gcc -O2 
    movsx rcx, DWORD PTR [rdx] # load with sign-extension from int32 to int64 
    cmp  ecx, 127 
    jle  .L82  # conditional-jump over the next instruction 
    add  rbp, rcx # sum+=data[c] 
.L82: 
    add  rdx, 4 
    cmp  rbx, rdx 
    jne  .L83 

दो लूप-जाता निर्भरता चेन रहे हैं। sum 0 या 1 चक्र लंबा है, और लूप-काउंटर हमेशा 1 चक्र लंबा होता है। हालांकि, लूप सैंडीब्रिज पर 5 फ़्यूज्ड-डोमेन यूप्स है, इसलिए यह 1 सी प्रति पुनरावृत्ति पर निष्पादित नहीं हो सकता है, इसलिए विलंबता एक बाधा नहीं है।

यह शायद 2 चक्रों (शाखा निर्देश थ्रूपुट पर बाधा) के बारे में एक पुनरावृत्ति पर चलता है, बनाम -ओ 3 लूप के लिए प्रति 3 चक्र बनाम। अगली बाधा एएलयू यूओपी थ्रूपुट होगी: 4 एएलयू यूओप्स (नहीं लिया गया मामला) लेकिन केवल 3 एएलयू बंदरगाहों। (एडीडी किसी भी बंदरगाह पर चला सकते हैं)।

यह पाइपलाइन-विश्लेषण पूर्वानुमान ~ 3 सेकंड के लिए ~ 3 सेकंड के लिए -ओ 3 बनाम ~ 2 सेकंड के लिए बिल्कुल सटीक रूप से मेल खाता है।

---

Haswell/Skylake, एक 1.25 प्रति चक्र पर नहीं-ले जाया मामले चलाने के बाद से यह एक ले लिया शाखा के रूप में एक ही चक्र में एक नहीं लिया शाखा निष्पादित कर सकते हैं और 4 ALU बंदरगाह हैं सकता है। (या a 5 uop loop doesn't quite issue at 4 uops every cycle के बाद से थोड़ा कम)।

(बस का परीक्षण किया:।। Skylake @ 3.9GHz 1.45s में पूरे कार्यक्रम की टहनीदार संस्करण, या 1.68s में शाखा संस्करण चलाता है तो अंतर बहुत छोटा है वहाँ)

---

g + +6.3.1 cmov का उपयोग -O2 पर भी करता है, लेकिन जी ++ 5.4 अभी भी 4.9.2 की तरह व्यवहार करता है।

दोनों जी ++ 6.3.1 और जी ++ 5.4 के साथ

, -fprofile-generate/-fprofile-use का उपयोग कर भी -O3 (-fno-tree-vectorize के साथ) पर टहनीदार संस्करण पैदा करता है।

नए जीसीसी से लूप का सीएमओवी संस्करण सीएमपी/सीएमओवी के बजाय add ecx,-128/cmovge rbx,rdx का उपयोग करता है। यह थोडा अजीब है, लेकिन शायद इसे धीमा नहीं करता है। एडीडी एक आउटपुट रजिस्टर के साथ-साथ झंडे लिखता है, इसलिए भौतिक रजिस्टरों की संख्या पर अधिक दबाव पैदा करता है। लेकिन जब तक यह एक बाधा नहीं है, यह लगभग बराबर होना चाहिए।

---

नए जीसीसी ऑटो vectorizes -O3 साथ पाश है, जो यहां तक ​​कि बस SSE2 के साथ एक महत्वपूर्ण speedup है। (उदाहरण के लिए मेरा i7-6700k स्काइलेक वेक्टरीकृत संस्करण 0.74s में चलाता है, इसलिए स्केलर के रूप में लगभग दोगुना तेज़ या -O3 -march=native 0.35s में, AVX2 256b वैक्टर का उपयोग करके)।

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