c++ - 64-बिट के साथ 32-बिट लूप गणना चर को प्रतिस्थापित करना पागल प्रदर्शन विचलन प्रस्तुत करता है




4 Answers

कल्पित: झूठी डेटा निर्भरता (और संकलक इसके बारे में भी अवगत नहीं है)

सैंडी / आइवी ब्रिज और हैसवेल प्रोसेसर पर, निर्देश:

popcnt  src, dest

प्रतीत होता है कि गंतव्य रजिस्टर dest पर झूठी निर्भरता है। भले ही निर्देश केवल इसे लिखता है, निर्देश तब तक इंतजार करेगा जब तक कि निष्पादन से पहले भाग तैयार न हो जाए।

यह निर्भरता केवल एक ही लूप पुनरावृत्ति से 4 popcnt s को पकड़ नहीं popcnt । यह लूप पुनरावृत्तियों में ले जा सकता है जिससे प्रोसेसर के लिए अलग-अलग लूप पुनरावृत्तियों को समानांतर करना असंभव हो जाता है।

unsigned बनाम uint64_t और अन्य tweaks सीधे समस्या को प्रभावित नहीं करते हैं। लेकिन वे रजिस्टर आवंटक को प्रभावित करते हैं जो चर के लिए रजिस्ट्रार असाइन करता है।

आपके मामले में, गति आवंटक द्वारा किए जाने वाले निर्णय के आधार पर गति (झूठी) निर्भरता श्रृंखला में फंस गई चीज़ों का सीधा परिणाम है।

  • 13 जीबी / एस में एक श्रृंखला है: popcnt - add - popcnt - popcnt → अगला पुनरावृत्ति
  • 15 जीबी / एस में एक श्रृंखला है: popcnt - add - popcnt - add → अगला पुनरावृत्ति
  • 20 जीबी / एस में एक श्रृंखला है: popcnt - popcnt → अगला पुनरावृत्ति
  • 26 जीबी / एस में एक श्रृंखला है: popcnt - popcnt → अगला पुनरावृत्ति

20 जीबी / एस और 26 जीबी / एस के बीच अंतर अप्रत्यक्ष पते का मामूली आर्टिफैक्ट प्रतीत होता है। किसी भी तरह से, प्रोसेसर इस गति तक पहुंचने के बाद अन्य बाधाओं को मारना शुरू कर देता है।

इसका परीक्षण करने के लिए, मैंने कंपाइलर को बाईपास करने और वास्तव में असेंबली प्राप्त करने के लिए इनलाइन असेंबली का उपयोग किया। मैं अन्य सभी निर्भरताओं को तोड़ने के लिए count चर को भी विभाजित करता हूं जो बेंचमार्क के साथ गड़बड़ कर सकता है।

परिणाम यहां दिए गए हैं:

सैंडी ब्रिज ज़ीऑन @ 3.5 गीगाहर्ट्ज: (पूर्ण परीक्षण कोड नीचे पाया जा सकता है)

  • जीसीसी 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • उबंटू 12

विभिन्न रजिस्टर्स: 18.6195 जीबी / एस

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

वही रजिस्टर: 8.4 9 272 जीबी / एस

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

टूटी हुई श्रृंखला के साथ वही रजिस्टर: 17.886 9 जीबी / एस

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

तो संकलक के साथ क्या गलत हो गया?

ऐसा लगता है कि न तो जीसीसी और न ही विजुअल स्टूडियो को पता है कि popcnt की इतनी झूठी निर्भरता है। फिर भी, ये झूठी निर्भरता असामान्य नहीं हैं। यह सिर्फ एक बात है कि संकलक इसके बारे में जानते हैं या नहीं।

popcnt बिल्कुल सबसे ज्यादा इस्तेमाल किया निर्देश नहीं है। तो यह वास्तव में आश्चर्य की बात नहीं है कि एक प्रमुख कंपाइलर इस तरह कुछ याद कर सकता है। ऐसा लगता है कि इस समस्या का उल्लेख कहीं भी कोई दस्तावेज नहीं है। यदि इंटेल इसका खुलासा नहीं करता है, तो बाहर कोई भी तब तक नहीं जान पाएगा जब तक कि कोई मौका न हो।

( अपडेट: संस्करण 4.9.2 के रूप में , जीसीसी इस झूठी निर्भरता से अवगत है और ऑप्टिमाइज़ेशन सक्षम होने पर इसे क्षतिपूर्ति करने के लिए कोड उत्पन्न करता है। क्लैंग, एमएसवीसी और यहां तक ​​कि इंटेल के अपने आईसीसी सहित अन्य विक्रेताओं के प्रमुख कंपाइलर्स अभी तक इसके बारे में अवगत नहीं हैं यह microarchitectural erratum और कोड को उत्सर्जित नहीं करेगा जो इसके लिए क्षतिपूर्ति करता है।)

सीपीयू की इतनी झूठी निर्भरता क्यों है?

हम केवल अनुमान लगा सकते हैं, लेकिन ऐसा लगता है कि इंटेल के पास दो-ऑपरेंड निर्देशों के लिए एक ही हैंडलिंग है। सामान्य निर्देश जैसे add , sub दो ऑपरेटरों को लेते हैं जिनमें से दोनों इनपुट हैं। इसलिए प्रोसेसर डिज़ाइन को सरल रखने के लिए इंटेल शायद उसी श्रेणी में popcnt को shoved popcnt दिया।

एएमडी प्रोसेसर में यह झूठी निर्भरता नहीं दिखती है।

संदर्भ के लिए पूर्ण परीक्षण कोड नीचे दिया गया है:

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

यहां एक समान दिलचस्प बेंचमार्क पाया जा सकता है: http://pastebin.com/kbzgL8si
यह बेंचमार्क popcnt एस की संख्या बदलता है जो (झूठी) निर्भरता श्रृंखला में हैं।

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

मैं डेटा के बड़े सरणी को popcount करने का सबसे तेज़ तरीका popcount रहा था। मुझे एक बहुत ही अजीब प्रभाव का सामना करना पड़ा: लूप वैरिएबल को unsigned से बदलकर uint64_t ने मेरे पीसी पर प्रदर्शन ड्रॉप 50% कर दिया।

बेंचमार्क

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with unsigned
            for (unsigned i=0; i<size/8; i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }
    {
        startP = chrono::system_clock::now();
        count=0;
        for( unsigned k = 0; k < 10000; k++){
            // Tight unrolled loop with uint64_t
            for (uint64_t i=0;i<size/8;i+=4) {
                count += _mm_popcnt_u64(buffer[i]);
                count += _mm_popcnt_u64(buffer[i+1]);
                count += _mm_popcnt_u64(buffer[i+2]);
                count += _mm_popcnt_u64(buffer[i+3]);
            }
        }
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
        cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
             << (10000.0*size)/(duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

जैसा कि आप देखते हैं, हम यादृच्छिक डेटा का एक बफर बनाते हैं, आकार x मेगाबाइट्स के साथ जहां x कमांड लाइन से पढ़ा जाता है। इसके बाद, हम बफर पर फिर से चलते हैं और popcount करने के लिए आंतरिक x86 popcount संस्करण का उपयोग करते हैं। अधिक सटीक परिणाम प्राप्त करने के लिए, हम 10,000 बार पॉपकाउंट करते हैं। हम पॉपकाउंट के लिए समय मापते हैं। ऊपरी मामले में, निचले मामले में, आंतरिक लूप वैरिएबल unsigned , आंतरिक लूप चर uint64_t । मैंने सोचा कि इससे कोई फर्क नहीं पड़ता है, लेकिन इसके विपरीत मामला है।

(बिल्कुल पागल) परिणाम

मैं इसे इस तरह संकलित करता हूं (जी ++ संस्करण: उबंटू 4.8.2-19ubuntu1):

g++ -O3 -march=native -std=c++11 test.cpp -o test

मेरे Haswell कोर i7-4770K CPU @ 3.50 गीगाहर्ट्ज पर परिणाम हैं, test 1 चल रहा है (इसलिए 1 एमबी यादृच्छिक डेटा):

  • हस्ताक्षर किए गए 41 9 5 9 360000 0.401554 सेक 26.113 जीबी / एस
  • uint64_t 41959360000 0.75 9 822 सेक 13.8003 जीबी / एस

जैसा कि आप देखते हैं, uint64_t संस्करण का थ्रूपुट केवल unsigned संस्करण में से एक है! समस्या यह प्रतीत होती है कि अलग-अलग असेंबली उत्पन्न होती है, लेकिन क्यों? सबसे पहले, मैंने एक कंपाइलर बग के बारे में सोचा, इसलिए मैंने क्लैंग clang++ (उबंटू क्लैंग संस्करण 3.4-1ubuntu3) की कोशिश की:

clang++ -O3 -march=native -std=c++11 teest.cpp -o test

परिणाम: test 1

  • हस्ताक्षर किए गए 41 9 5 9 36000000 0.3 9 8 9 3 सेकेंड 26.3267 जीबी / एस
  • uint64_t 41959360000 0.680954 सेकंड 15.3986 जीबी / एस

तो, यह लगभग एक ही परिणाम है और अभी भी अजीब है। लेकिन अब यह बहुत अजीब हो जाता है। मैं बफर आकार को प्रतिस्थापित करता हूं जो स्थिर 1 साथ इनपुट से पढ़ा गया था, इसलिए मैं बदलता हूं:

uint64_t size = atol(argv[1]) << 20;

सेवा मेरे

uint64_t size = 1 << 20;

इस प्रकार, कंपाइलर अब संकलन समय पर बफर आकार जानता है। शायद यह कुछ अनुकूलन जोड़ सकते हैं! g++ लिए संख्याएं यहां दी गई हैं:

  • हस्ताक्षर किए गए 41 9 5 9 36000000 0.50 9 156 सेकेंड 20.5 9 44 जीबी / एस
  • uint64_t 41959360000 0.508673 सेकंड 20.6139 जीबी / एस

अब, दोनों संस्करण समान रूप से तेज़ हैं। हालांकि, unsigned गए भी धीमे हो गए ! यह 26 से 20 GB/s तक गिर गया, इस प्रकार निरंतर मूल्य से एक गैर-स्थिरता को एक विकृतिकरण के कारण बदल दिया गया । गंभीरता से, मुझे कोई संकेत नहीं है कि यहां क्या हो रहा है! लेकिन अब नए संस्करण के साथ clang++ करने के लिए:

  • हस्ताक्षर किए गए 41 9 5 9 36000000 0.677009 सेकंड 15.4884 जीबी / एस
  • uint64_t 41959360000 0.67690 9 सेकंड 15.4906 जीबी / एस

रुको क्या? अब, दोनों संस्करण 15 जीबी / एस की धीमी संख्या में गिराए गए हैं। इस प्रकार, निरंतर मूल्य से एक गैर-स्थिरता को बदलने से क्लैंग के लिए दोनों मामलों में धीमी कोड भी आती है!

मैंने अपने बेंचमार्क को संकलित करने के लिए एक आइवी ब्रिज सीपीयू के साथ एक सहयोगी से पूछा। उन्हें समान परिणाम मिलते हैं, इसलिए ऐसा लगता है कि हैसवेल नहीं है। क्योंकि दो कंपाइलर यहां अजीब परिणाम उत्पन्न करते हैं, यह एक कंपाइलर बग प्रतीत नहीं होता है। हमारे पास एएमडी सीपीयू नहीं है, इसलिए हम केवल इंटेल के साथ परीक्षण कर सकते हैं।

अधिक पागलपन, कृपया!

पहला उदाहरण लें ( atol(argv[1]) ) और चर से पहले एक static , यानी:

static uint64_t size=atol(argv[1])<<20;

जी ++ में मेरे परिणाम यहां दिए गए हैं:

  • हस्ताक्षर किए गए 41 9 5 9 360000 0.396728 सेकंड 26.4306 जीबी / एस
  • uint64_t 41959360000 0.50 9 484 सेकंड 20.5811 जीबी / एस

हाँ, अभी तक एक और विकल्प । हमारे पास अभी भी u32 साथ तेज़ 26 जीबी / एस है, लेकिन हम कम से कम 13 जीबी / एस से 20 जीबी / एस संस्करण में u64 प्राप्त करने में कामयाब रहे! मेरे u64 के पीसी पर, u64 संस्करण u64 संस्करण से भी तेज हो गया, जो सभी का सबसे तेज़ परिणाम प्रदान करता था। अफसोस की बात है, यह केवल g++ लिए काम करता है, clang++ static बारे में परवाह नहीं करता है।

मेरा प्रश्न

क्या आप इन परिणामों को समझा सकते हैं? ख़ास तौर पर:

  • u32 और u64 बीच u32 अंतर कैसे हो सकता है?
  • निरंतर बफर आकार द्वारा गैर-स्थिरता को प्रतिस्थापित करने से कम इष्टतम कोड ट्रिगर कैसे हो सकता है?
  • static कीवर्ड का सम्मिलन u64 लूप को तेज़ी से कैसे बना सकता है? मेरे कॉलेज के कंप्यूटर पर मूल कोड से भी तेज!

मुझे पता है कि ऑप्टिमाइज़ेशन एक मुश्किल क्षेत्र है, हालांकि, मैंने कभी सोचा नहीं था कि ऐसे छोटे बदलाव निष्पादन समय में 100% अंतर का कारण बन सकते हैं और निरंतर बफर आकार जैसे छोटे कारक फिर से परिणामों को पूरी तरह मिला सकते हैं। बेशक, मैं हमेशा उस संस्करण को रखना चाहता हूं जो 26 जीबी / एस पॉपकाउंट करने में सक्षम है। एकमात्र विश्वसनीय तरीका मैं सोच सकता हूं कि इस मामले के लिए असेंबली पेस्ट करें और इनलाइन असेंबली का उपयोग करें। यह एकमात्र तरीका है जिसे मैं संकलक से छुटकारा पा सकता हूं जो छोटे बदलावों पर पागल लगते हैं। तुम क्या सोचते हो? क्या अधिकतर प्रदर्शन के साथ कोड को विश्वसनीय रूप से प्राप्त करने का कोई और तरीका है?

Disassembly

विभिन्न परिणामों के लिए यहां डिस्सेप्लर है:

जी ++ / u32 / non-const bufsize से 26 जीबी / एस संस्करण:

0x400af8:
lea 0x1(%rdx),%eax
popcnt (%rbx,%rax,8),%r9
lea 0x2(%rdx),%edi
popcnt (%rbx,%rcx,8),%rax
lea 0x3(%rdx),%esi
add %r9,%rax
popcnt (%rbx,%rdi,8),%rcx
add $0x4,%edx
add %rcx,%rax
popcnt (%rbx,%rsi,8),%rcx
add %rcx,%rax
mov %edx,%ecx
add %rax,%r14
cmp %rbp,%rcx
jb 0x400af8

G ++ / u64 / non-const bufsize से 13 जीबी / एस संस्करण:

0x400c00:
popcnt 0x8(%rbx,%rdx,8),%rcx
popcnt (%rbx,%rdx,8),%rax
add %rcx,%rax
popcnt 0x10(%rbx,%rdx,8),%rcx
add %rcx,%rax
popcnt 0x18(%rbx,%rdx,8),%rcx
add $0x4,%rdx
add %rcx,%rax
add %rax,%r12
cmp %rbp,%rdx
jb 0x400c00

क्लैंग ++ / u64 / non-const bufsize से 15 जीबी / एस संस्करण:

0x400e50:
popcnt (%r15,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r15,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r15,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r15,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp %rbp,%rcx
jb 0x400e50

जी ++ / u32 और u64 / const bufsize से 20 जीबी / एस संस्करण:

0x400a68:
popcnt (%rbx,%rdx,1),%rax
popcnt 0x8(%rbx,%rdx,1),%rcx
add %rax,%rcx
popcnt 0x10(%rbx,%rdx,1),%rax
add %rax,%rcx
popcnt 0x18(%rbx,%rdx,1),%rsi
add $0x20,%rdx
add %rsi,%rcx
add %rcx,%rbp
cmp $0x100000,%rdx
jne 0x400a68

क्लैंग ++ / u32 और u64 / const bufsize से 15 जीबी / एस संस्करण:

0x400dd0:
popcnt (%r14,%rcx,8),%rdx
add %rbx,%rdx
popcnt 0x8(%r14,%rcx,8),%rsi
add %rdx,%rsi
popcnt 0x10(%r14,%rcx,8),%rdx
add %rsi,%rdx
popcnt 0x18(%r14,%rcx,8),%rbx
add %rdx,%rbx
add $0x4,%rcx
cmp $0x20000,%rcx
jb 0x400dd0

दिलचस्प बात यह है कि सबसे तेज़ (26 जीबी / एस) संस्करण भी सबसे लंबा है! ऐसा लगता है कि lea का उपयोग करने वाला एकमात्र समाधान है। कुछ संस्करण कूदने के लिए jb का उपयोग करते हैं, अन्य लोग jne उपयोग करते हैं। लेकिन इसके अलावा, सभी संस्करण तुलनात्मक प्रतीत होते हैं। मैं नहीं देखता कि 100% प्रदर्शन अंतर कहां से उत्पन्न हो सकता है, लेकिन मैं असेंबली को समझने में बहुत सक्षम नहीं हूं। सबसे धीमा (13 जीबी / एस) संस्करण भी बहुत छोटा और अच्छा दिखता है। क्या कोई इसे समझा सकता है?

सीख सीखी

कोई फर्क नहीं पड़ता कि इस सवाल का जवाब क्या होगा; मैंने सीखा है कि वास्तव में गर्म लूप में हर विवरण महत्वपूर्ण हो सकता है, यहां तक ​​कि ऐसे विवरण भी जो हॉट कोड से कोई संबंध नहीं लगते हैं । मैंने कभी सोचा नहीं है कि लूप वैरिएबल के लिए किस प्रकार का उपयोग करना है, लेकिन जैसा कि आप देखते हैं कि ऐसा मामूली परिवर्तन 100% अंतर कर सकता है! यहां तक ​​कि एक बफर का भंडारण प्रकार भी एक बड़ा अंतर बना सकता है, जैसा कि हमने आकार चर के सामने static कीवर्ड को सम्मिलित करने के साथ देखा था! भविष्य में, मैं सिस्टम कंपोनेंट के लिए महत्वपूर्ण हैं जो वास्तव में तंग और गर्म लूप लिखते समय विभिन्न कंप्यूटर्स पर विभिन्न विकल्पों का परीक्षण करेगा।

दिलचस्प बात यह भी है कि प्रदर्शन अंतर अभी भी बहुत अधिक है हालांकि मैंने पहले से ही लूप को चार बार अनलॉक कर दिया है। तो अगर आप अनलॉक करते हैं, तो भी आप प्रमुख प्रदर्शन विचलन से हिट कर सकते हैं। काफी दिलचस्प।




यह कोई जवाब नहीं है, लेकिन अगर मैं टिप्पणी में परिणाम डालता हूं तो पढ़ना मुश्किल है।

मुझे इन परिणामों को मैक प्रो ( Westmere 6-कोर Xeon 3.33 गीगाहर्ट्ज) के साथ मिलता है। मैंने इसे clang -O3 -msse4 -lstdc++ a.cpp -oa ( clang -O3 -msse4 -lstdc++ a.cpp -oa समान परिणाम प्राप्त) के साथ संकलित किया।

uint64_t size=atol(argv[1])<<20; साथ uint64_t size=atol(argv[1])<<20;

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

uint64_t size=1<<20; साथ uint64_t size=1<<20;

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

मैंने यह भी करने की कोशिश की:

  1. परीक्षण आदेश को उलट दें, परिणाम वही है, इसलिए यह कैश कारक को नियंत्रित करता है।
  2. रिवर्स में कथन के for : for (uint64_t i=size/8;i>0;i-=4) । यह वही परिणाम देता है और यह साबित करता है कि संकलन पर्याप्त है कि आकार को प्रत्येक पुनरावृत्ति (अपेक्षित के रूप में) द्वारा विभाजित न करें।

मेरा जंगली अनुमान यहां है:

गति कारक तीन भागों में आता है:

  • कोड कैश: uint64_t संस्करण में बड़ा कोड आकार है, लेकिन इसका मेरे ज़ीऑन CPU पर कोई प्रभाव नहीं पड़ता है। यह 64-बिट संस्करण धीमा बनाता है।

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

  • निर्देश केवल 64-बिट संकलन (यानी, prefetch) पर उत्सर्जित होते हैं। यह 64-बिट तेज बनाता है।

तीन कारक एक साथ मनाए गए विरोधाभासी परिणामों के साथ मेल खाते हैं।




क्या आपने जीसीसी के लिए -funroll-loops -fprefetch-loop-arrays करने का प्रयास किया है?

मुझे इन अतिरिक्त अनुकूलन के साथ निम्नलिखित परिणाम मिलते हैं:

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s



क्या आपने लूप के बाहर कमी चरण को स्थानांतरित करने का प्रयास किया है? अभी आपके पास डेटा निर्भरता है जिसकी वास्तव में आवश्यकता नहीं है।

प्रयत्न:

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];

आपके पास कुछ अजीब अलियासिंग भी चल रहा है, मुझे यकीन नहीं है कि सख्त एलियासिंग नियमों के अनुरूप है।




Related

c++ performance optimization assembly compiler-optimization