c - यह कोड 6.5x धीरज के साथ अनुकूलन योग्य क्यों है?




performance gcc (2)

Godbolt के कंपाइलर एक्सप्लोरर पर अपने कोड का परीक्षण यह विवरण प्रदान करता है:

  • -O0 या अनुकूलन के बिना, उत्पन्न कोड C लाइब्रेरी फ़ंक्शन -O0 कॉल करता है
  • at -O1 में उत्पन्न कोड एक rep scasb निर्देश का उपयोग करके एक सरल इनलाइन विस्तार का उपयोग करता है।
  • -O2 और ऊपर, उत्पन्न कोड एक अधिक विस्तृत इनलाइन विस्तार का उपयोग करता है।

बार-बार अपने कोड को बेंचमार्क करना एक रन से दूसरे में पर्याप्त भिन्नता दिखाता है, लेकिन पुनरावृत्तियों की संख्या में वृद्धि से पता चलता है कि:

  • -O1 कोड C लाइब्रेरी कार्यान्वयन की तुलना में बहुत धीमा है: 32240 बनाम 3090
  • -O2 कोड -O1 की तुलना में तेज है, लेकिन अभी भी C ूप कोड की तुलना में काफी धीमा है: 8570 बनाम 3090

यह व्यवहार gcc और glibc लिए विशिष्ट है। Clang और Apple के Libc के साथ OS / X पर एक ही परीक्षण महत्वपूर्ण अंतर नहीं दिखाता है, जो कि कोई आश्चर्य की बात नहीं है क्योंकि Godbolt दिखाता है कि Clang सभी ऑप्टिमाइज़ेशन स्तरों पर C लाइब्रेरी स्ट्रलेन को कॉल उत्पन्न करता है।

इसे gcc / glibc में बग माना जा सकता है, लेकिन अधिक व्यापक बेंचमार्किंग यह दिखा सकती है कि कॉलिंग strlen का छोटे स्ट्रिंग्स के लिए इनलाइन कोड के प्रदर्शन की कमी से अधिक महत्वपूर्ण प्रभाव पड़ता है। जिन स्ट्रिंग्स पर आप बेंचमार्क असामान्य रूप से बड़े हैं, इसलिए अल्ट्रा-लॉन्ग स्ट्रिंग्स पर बेंचमार्क को केंद्रित करना शायद सार्थक परिणाम न दे सके।

मैंने इस बेंचमार्क में सुधार किया और विभिन्न स्ट्रिंग लंबाई का परीक्षण किया। यह एक इंटेल (R) Core (TM) i3-2100 CPU @ 3.10GHz पर चलने वाले gcc (डेबियन 4.7.2-5) 4.7.2 के साथ लिनक्स पर बेंचमार्क से प्रकट होता है कि -O1 द्वारा उत्पन्न इनलाइन कोड हमेशा धीमा होता है, मध्यम लंबे स्ट्रिंग्स के लिए 10 के एक कारक के रूप में, -O2 केवल बहुत कम स्ट्रिंग्स के लिए libc strlen की तुलना में थोड़ा तेज़ है और आधे लंबे स्ट्रिंग्स के लिए तेज़ है। इस डेटा से, strlen का GNU C लाइब्रेरी संस्करण, अधिकांश स्ट्रिंग लंबाई के लिए काफी कुशल है, कम से कम मेरे विशिष्ट हार्डवेयर पर। यह भी ध्यान में रखते हुए कि बेंचमार्क माप पर कैशिंग का एक बड़ा प्रभाव है।

यहाँ अद्यतन कोड है:

#include <stdlib.h>
#include <string.h>
#include <time.h>

void benchmark(int repeat, int minlen, int maxlen) {
    char *s = malloc(maxlen + 1);
    memset(s, 'A', minlen);
    long long bytes = 0, calls = 0;
    clock_t clk = clock();
    for (int n = 0; n < repeat; n++) {
        for (int i = minlen; i < maxlen; ++i) {
            bytes += i + 1;
            calls += 1;
            s[i] = '\0';
            s[strlen(s)] = 'A';
        }
    }
    clk = clock() - clk;
    free(s);
    double avglen = (minlen + maxlen - 1) / 2.0;
    double ns = (double)clk * 1e9 / CLOCKS_PER_SEC;
    printf("average length %7.0f -> avg time: %7.3f ns/byte, %7.3f ns/call\n",
           avglen, ns / bytes, ns / calls);
}

int main() {
    benchmark(10000000, 0, 1);
    benchmark(1000000, 0, 10);
    benchmark(1000000, 5, 15);
    benchmark(100000, 0, 100);
    benchmark(100000, 50, 150);
    benchmark(10000, 0, 1000);
    benchmark(10000, 500, 1500);
    benchmark(1000, 0, 10000);
    benchmark(1000, 5000, 15000);
    benchmark(100, 1000000 - 50, 1000000 + 50);
    return 0;
}

यहाँ उत्पादन है:

chqrlie> gcc -std=c99 -O0 benchstrlen.c && ./a.out
average length       0 -> avg time:  14.000 ns/byte,  14.000 ns/call
average length       4 -> avg time:   2.364 ns/byte,  13.000 ns/call
average length      10 -> avg time:   1.238 ns/byte,  13.000 ns/call
average length      50 -> avg time:   0.317 ns/byte,  16.000 ns/call
average length     100 -> avg time:   0.169 ns/byte,  17.000 ns/call
average length     500 -> avg time:   0.074 ns/byte,  37.000 ns/call
average length    1000 -> avg time:   0.068 ns/byte,  68.000 ns/call
average length    5000 -> avg time:   0.064 ns/byte, 318.000 ns/call
average length   10000 -> avg time:   0.062 ns/byte, 622.000 ns/call
average length 1000000 -> avg time:   0.062 ns/byte, 62000.000 ns/call
chqrlie> gcc -std=c99 -O1 benchstrlen.c && ./a.out
average length       0 -> avg time:  20.000 ns/byte,  20.000 ns/call
average length       4 -> avg time:   3.818 ns/byte,  21.000 ns/call
average length      10 -> avg time:   2.190 ns/byte,  23.000 ns/call
average length      50 -> avg time:   0.990 ns/byte,  50.000 ns/call
average length     100 -> avg time:   0.816 ns/byte,  82.000 ns/call
average length     500 -> avg time:   0.679 ns/byte, 340.000 ns/call
average length    1000 -> avg time:   0.664 ns/byte, 664.000 ns/call
average length    5000 -> avg time:   0.651 ns/byte, 3254.000 ns/call
average length   10000 -> avg time:   0.649 ns/byte, 6491.000 ns/call
average length 1000000 -> avg time:   0.648 ns/byte, 648000.000 ns/call
chqrlie> gcc -std=c99 -O2 benchstrlen.c && ./a.out
average length       0 -> avg time:  10.000 ns/byte,  10.000 ns/call
average length       4 -> avg time:   2.000 ns/byte,  11.000 ns/call
average length      10 -> avg time:   1.048 ns/byte,  11.000 ns/call
average length      50 -> avg time:   0.337 ns/byte,  17.000 ns/call
average length     100 -> avg time:   0.299 ns/byte,  30.000 ns/call
average length     500 -> avg time:   0.202 ns/byte, 101.000 ns/call
average length    1000 -> avg time:   0.188 ns/byte, 188.000 ns/call
average length    5000 -> avg time:   0.174 ns/byte, 868.000 ns/call
average length   10000 -> avg time:   0.172 ns/byte, 1716.000 ns/call
average length 1000000 -> avg time:   0.172 ns/byte, 172000.000 ns/call

मैं किसी कारण के लिए glibc के strlen फंक्शन को बेंचमार्क करना चाहता था और यह पाया कि यह जाहिरा तौर पर जीसीसी में सक्षम ऑप्टिमाइजेशन के साथ बहुत धीमा प्रदर्शन करता है और मुझे पता नहीं क्यों।

यहाँ मेरा कोड है:

#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int main() {
    char *s = calloc(1 << 20, 1);
    memset(s, 65, 1000000);
    clock_t start = clock();
    for (int i = 0; i < 128; ++i) {
        s[strlen(s)] = 'A';
    }
    clock_t end = clock();
    printf("%lld\n", (long long)(end-start));
    return 0;
}

मेरी मशीन पर यह आउटपुट:

$ gcc test.c && ./a.out
13336
$ gcc -O1 test.c && ./a.out
199004
$ gcc -O2 test.c && ./a.out
83415
$ gcc -O3 test.c && ./a.out
83415

किसी तरह, अनुकूलन सक्षम करने से यह लंबे समय तक क्रियान्वित होता है।


GCC की इनलाइन strlen पैटर्न, SSE2 pcmpeqb / pmovmskb और pmovmskb साथ क्या कर सकता है, इसकी तुलना में बहुत धीमी है, जिसे calloc से 16-बाइट संरेखण दिया गया है । यह "अनुकूलन" वास्तव में एक निराशावाद है।

16-बाइट संरेखण का लाभ उठाने वाला मेरा सरल हाथ से लिखा हुआ लूप 5x है जो कि बड़े बफ़र्स के लिए gcc -O3 इनलाइन की तुलना में 5 गुना अधिक है, और छोटी स्ट्रिंग्स के लिए ~ 2x तेज़ है। (और स्ट्रिंग्स को शॉर्ट स्ट्रिंग्स के लिए कॉल करने से अधिक तेज़ है)। मैंने gcc.gnu.org/bugzilla/show_bug.cgi?id=88809 पर एक टिप्पणी जोड़ दी है कि यह क्या है जब यह सक्षम होने पर -O2 / -O3 को इनलाइन करना चाहिए। (16-बाइट तक रैंप करने के सुझाव के साथ यदि हम केवल 4-बाइट संरेखण को शुरू करने के लिए जानते हैं।)

जब जीसीसी जानता है कि इसमें बफर के लिए 4-बाइट संरेखण है ( calloc द्वारा calloc ), यह जीपी पूर्णांक रजिस्टरों (-ओ 2 और उच्चतर) का उपयोग करके इनलाइन strlen को 4-बाइट-ए-ए-टाइम स्केलर बिथेक के रूप में चुनता है।

(एक समय में 4 बाइट्स पढ़ना केवल सुरक्षित है यदि हम जानते हैं कि हम एक ऐसे पृष्ठ पर नहीं जा सकते हैं जिसमें कोई स्ट्रिंग बाइट्स नहीं हैं, और इस प्रकार अनमैप हो सकता है। क्या यह उसी के भीतर एक बफर के अंत को पढ़ने के लिए सुरक्षित है पृष्ठ x86 और x64 पर? (TL: DR हाँ, asm में यह है, इसलिए संकलक कोड का उत्सर्जन कर सकता है जो कि C स्रोत में ऐसा करने पर भी UB होता है। libc strlen कार्यान्वयन भी इसका लाभ उठाते हैं। मेरे लिए वहां अपना नाम देखें। glibc strlen लिंक और बड़े तार के लिए यह कितनी तेजी से चलता है इसका सारांश।)

At- -O1 , gcc हमेशा (ज्ञात संरेखण के बिना भी) इनलाइन repnz scasb को repnz scasb रूप में चुनता है, जो बहुत धीमा है (आधुनिक इंटेल सीपीयू पर लगभग 1 बाइट प्रति घड़ी चक्र)। "फास्ट स्ट्रिंग्स" केवल repz और repz पर लागू होता है, न कि repz / repnz निर्देशों पर, दुर्भाग्य से। उनका माइक्रोकोड एक बार में केवल 1 बाइट है, लेकिन उनके पास अभी भी कुछ स्टार्टअप ओवरहेड हैं। ( https://agner.org/optimize/ )

(हम उदाहरण के लिए संकलक / पुनः लोड करने के लिए संकलक / पुनः लोड करके संकलक से पॉइंटर को "छिपाकर" इसका परीक्षण कर सकते हैं। उदाहरण के लिए, gcc को किसी संरेखण जानकारी को नष्ट करने वाले volatile मान से वापस आने वाले सूचक मान के बारे में शून्य धारणा बनाना है। ।)

GCC के पास कुछ x86 ट्यूनिंग विकल्प हैं जैसे -mstringop-strategy=libcall बनाम unrolled_loop बनाम rep_byte सामान्य रूप से स्ट्रिंग संचालन को rep_byte लिए (न केवल memcmp ; memcmp एक अन्य प्रमुख होगा जो memcmp या लूप के साथ किया जा सकता है)। मैंने जाँच नहीं की है कि इनका यहाँ क्या प्रभाव है।

एक अन्य विकल्प के लिए डॉक्स भी वर्तमान व्यवहार का वर्णन करते हैं। हम इस inlining (अलाइनमेंट-हैंडलिंग के लिए अतिरिक्त कोड के साथ) उन मामलों में भी प्राप्त कर सकते हैं, जहां हम इसे अनलॉग्ड पॉइंटर्स पर चाहते थे। (यह एक वास्तविक पूर्ण जीत हुआ करता था, विशेष रूप से छोटे तारों के लिए, जहां लक्ष्य इनलाइन लूप कचरा नहीं था, मशीन की तुलना में।

-minline-all-stringops
डिफ़ॉल्ट GCC इनलाइन स्ट्रिंग ऑपरेशन के द्वारा ही गंतव्य को कम से कम 4-बाइट की सीमा के साथ जोड़ा जाना माना जाता है। यह अधिक इनलाइनिंग को सक्षम करता है और कोड आकार को बढ़ाता है, लेकिन कोड के प्रदर्शन में सुधार कर सकता है जो तेजी से मेम्कपी, स्ट्रलेन और छोटी लंबाई के लिए मेमसेट पर निर्भर करता है।

GCC में प्रति-फ़ंक्शन विशेषताएँ भी हैं जिन्हें आप स्पष्ट रूप से इसे नियंत्रित करने के लिए उपयोग कर सकते हैं, जैसे __attribute__((no-inline-all-stringops)) void foo() { ... } , लेकिन मैंने इसके साथ नहीं खेला है। (यह इनलाइन-ऑल का विपरीत है। इसका मतलब इनलाइन कोई नहीं है, यह केवल 4-बाइट संरेखण ज्ञात होने पर केवल इनलाइनिंग पर वापस जाता है।)

strlen की इनलाइन strlen स्ट्रेटेजी दोनों ही 16-बाइट संरेखण का लाभ उठाने में विफल रहती हैं, और x86-64 के लिए बहुत खराब हैं

जब तक छोटा-स्ट्रिंग मामला बहुत आम है, एक 4-बाइट चंक कर रहा है, तो संरेखित 8-बाइट चंक 4-बाइट के रूप में लगभग दोगुना हो जाएगा।

और 4-बाइट रणनीति में शून्य बाइट वाले डॉर्ड के भीतर बाइट खोजने के लिए आवश्यक की तुलना में बहुत धीमी सफाई है। यह अपने उच्च बिट सेट के साथ एक बाइट की तलाश करके इसका पता लगाता है, इसलिए इसे अन्य बिट्स से नकाब उतारना चाहिए और bsf (बिट-स्कैन फॉरवर्ड) का उपयोग करना चाहिए। आधुनिक सीपीयू (Intel और Ryzen) पर 3 चक्र विलंबता है। या कम्पाइलर rep bsf tzcnt उपयोग कर सकते हैं इसलिए यह CPU पर tzcnt रूप में चलता है जो BMI1 का समर्थन करता है, जो AMD पर अधिक कुशल है। tzcnt और tzcnt गैर-शून्य इनपुट के लिए समान परिणाम देते हैं।

GCC का 4-बाइट लूप ऐसा लगता है कि यह शुद्ध C से संकलित है, या कुछ लक्ष्य-स्वतंत्र तर्क, बिटकॉन्स का लाभ नहीं उठा रहे हैं। g86 बीएमआई 1 के साथ x86 के लिए संकलन करते समय इसे अनुकूलित करने के लिए nn का उपयोग करता है, लेकिन यह अभी भी प्रति चक्र 4 बाइट्स से कम है।

SSE2 pcmpeqb + pcmpeqb शॉर्ट और लॉन्ग इनपुट दोनों के लिए बहुत बेहतर है । x86-64 यह गारंटी देता है कि SSE2 उपलब्ध है, और x86-64 सिस्टम V में alignof(maxalign_t) = 16 इसलिए calloc हमेशा पॉइंटर्स को लौटाएगा जो कि कम से कम 16-बाइट संरेखित हैं।

मैंने प्रदर्शन के परीक्षण के लिए strlen ब्लॉक के लिए एक प्रतिस्थापन लिखा

जैसा कि उम्मीद थी कि यह 4 के बजाय एक बार में स्काइलेक 16 बाइट्स पर 4x तेज है।

(मैंने मूल स्रोत को -O3 साथ -O3 , फिर asm को यह देखने के लिए संपादित किया कि स्ट्रेलन के इनलाइन विस्तार के लिए इस रणनीति के साथ क्या प्रदर्शन होना चाहिए था। मैंने इसे C स्रोत के अंदर इनलाइन asm में भी चित्रित किया है ; उस संस्करण को Godbolt पर देखें । )

    # at this point gcc has `s` in RDX, `i` in ECX

    pxor       %xmm0, %xmm0         # zeroed vector to compare against
    .p2align 4
.Lstrlen16:                         # do {
#ifdef __AVX__
    vpcmpeqb   (%rdx), %xmm0, %xmm1
#else
    movdqa     (%rdx), %xmm1
    pcmpeqb    %xmm0, %xmm1           # xmm1 = -1 where there was a 0 in memory
#endif

    add         $16, %rdx             # ptr++
    pmovmskb  %xmm1, %eax             # extract high bit of each byte to a 16-bit mask
    test       %eax, %eax
    jz        .Lstrlen16            # }while(mask==0);
    # RDX points at the 16-byte chunk *after* the one containing the terminator
    # EAX = bit-mask of the 0 bytes, and is known to be non-zero
    bsf        %eax, %eax           # EAX = bit-index of the lowest set bit

    movb       $'A', -16(%rdx, %rax)

ध्यान दें कि मैंने स्टोर एड्रेसिंग मोड में स्ट्रैनल क्लीनअप के हिस्से को अनुकूलित किया है: मैं -16 विस्थापन के साथ ओवरशूट के लिए सही हूं, और यह सिर्फ स्ट्रिंग के अंत का पता लगा रहा है, वास्तव में लंबाई की गणना नहीं कर रहा है और फिर बीसीसी की तरह अनुक्रमण कर रहा है। अपने 4-बाइट-एट-ए-टाइम लूप को इनलाइन करने के बाद।

वास्तविक स्ट्रिंग लंबाई (अंत के लिए सूचक के बजाय) प्राप्त करने के लिए, आप rdx-start को घटाएँगे और फिर rax-16 जोड़ेंगे (शायद 2 रजिस्टरों को जोड़ने के लिए LEA के साथ) एक निरंतर, लेकिन 3-घटक LEA में अधिक विलंबता होगी।

AVX लोड शून्य रजिस्टर को नष्ट किए बिना एक निर्देश में तुलना करने के लिए AVX के साथ, पूरे लूप को केवल 4 यूओपी है, नीचे से 5. (परीक्षण / jz मैक्रो-फ़्यूज़ दोनों इंटेल और एएमडी पर एक यूओपी में। गैर-अनुक्रमित के साथ vpcmpeqb । मेमोरी-सोर्स इसे पूरी पाइपलाइन के माध्यम से माइक्रो-फ्यूज्ड रख सकता है, इसलिए यह फ्रंट-एंड के लिए केवल 1 फ्यूज्ड-डोमेन यूओपी है।)

(ध्यान दें कि एसएसई के साथ 128-बिट एवीएक्स को मिलाने से हसवेल पर भी स्टॉल नहीं लगते हैं, जब तक आप शुरू करने के लिए साफ-सुथरी स्थिति में होते हैं। इसलिए मैंने एवीएक्स को अन्य निर्देशों को बदलने के बारे में परेशान नहीं किया, केवल एक। यह मायने रखता है। वहाँ कुछ मामूली प्रभाव लग रहा था जहां pxor वास्तव में मेरे डेस्कटॉप पर vpxor से थोड़ा बेहतर था, हालांकि, एक AVX लूप बॉडी के लिए। यह कुछ हद तक vpxor लग रहा था, लेकिन यह अजीब है क्योंकि कोई कोड-आकार अंतर नहीं है और इस प्रकार कोई संरेखण अंतर नहीं है। ।)

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

बहुत छोटे स्ट्रिंग मामले (जैसे 0 से 3 बाइट्स) के लिए, शुद्ध स्केलर (विशेषकर बुलडोजर-परिवार पर) का उपयोग करके उस मामले के लिए थोड़ा कम विलंबता प्राप्त करना संभव हो सकता है, लेकिन 0 से 15 बाइट्स तक सभी तार होने में लगेंगे एक ही ब्रांच पाथ (लूप ब्रांच कभी नहीं लिया गया) अधिकांश शॉर्ट-स्ट्रिंग्स उपयोग-मामलों के लिए बहुत अच्छा है

15 बाइट तक सभी स्ट्रिंग्स के लिए बहुत अच्छा होना एक अच्छा विकल्प लगता है, जब हम जानते हैं कि हमारे पास 16-बाइट संरेखण है। अधिक प्रेडिक्टेबल ब्रांचिंग बहुत अच्छी है। (और ध्यान दें कि लूपिंग करते समय, pmovmskb विलंबता केवल यह pmovmskb कि हम लूप को तोड़ने के लिए कितनी जल्दी शाखा की गड़बड़ी का पता लगा सकते हैं? शाखा भविष्यवाणी + सट्टा निष्पादन प्रत्येक पुनरावृत्ति में स्वतंत्र pmovmskb की विलंबता को छुपाता है।

अगर हमें उम्मीद है कि तार सामान्य होने की संभावना है, तो हम थोड़ा सा अनियंत्रित हो सकते हैं, लेकिन उस समय आपको बस libc फ़ंक्शन को कॉल करना चाहिए, ताकि रनटाइम पर उपलब्ध होने पर यह AVX2 को भेजा जा सके। 1 से अधिक वेक्टर के लिए अनियंत्रित होना, सफाई को जटिल बनाता है, साधारण मामलों को चोट पहुँचाता है।

आर्क लिनक्स पर gcc8.2 के साथ मेरी मशीन i7-6700k स्काइलेक पर 4.2GHz अधिकतम टर्बो (और energy_performance_preference = प्रदर्शन) पर, मुझे कुछ हद तक लगातार बेंचमार्किंग का समय मिलता है क्योंकि मेरे सीपीयू की घड़ी की गति मेमसेट के दौरान रैंप होती है। लेकिन शायद हमेशा अधिकतम टर्बो तक नहीं; मेमोरी-बाउंड होने पर स्काइलेक का hw पावर प्रबंधन डाउनक्लॉक हो जाता है। perf stat पता चलता है कि मैं आमतौर पर 4.0GHz के आस-पास सही रहता था जब इसे stdout आउटपुट औसत करने के लिए और stderr पर perf सारांश देखें।

perf stat -r 100 ./a.out | awk '{sum+= $1}  END{print sum/100;}'

मैंने अपने asm को GNU C इनलाइन-asm स्टेटमेंट में कॉपी करना समाप्त कर दिया , इसलिए मैं कोड को गॉडबोल्ट कंपाइलर एक्सप्लोरर पर रख सकता था

बड़े तार के लिए, प्रश्न में समान लंबाई: ~ 4GHz Skylake पर समय

  • ~ 62100 clock_t समय इकाइयाँ: -O1 प्रतिनिधि scas: ( clock() थोड़ा अप्रचलित है, लेकिन मैं इसे बदलने से परेशान नहीं हूँ।)
  • ~ 15900 clock_t समय इकाइयाँ: clock_t gcc 4-बाइट लूप रणनीति: 100 रन का औसत =। (या हो सकता है ~ ~ 15800 -march=native लिए andn )
  • ~ 1880 clock_t समय इकाइयाँ: clock_t glibc strlen फ़ंक्शन कॉल के साथ, clock_t का उपयोग करके
  • ~ 3190 clock_t समय इकाइयाँ: (AVX1 128-बिट वैक्टर, 4 यूओपी लूप) हाथ से लिखी गई इनलाइन एएसएम जो कि gcc / inline कर सकती हैं।
  • ~ 3230 clock_t समय इकाइयाँ: (SSE2 5 यूओपी लूप) हाथ से लिखी जाने वाली इनलाइन जो कि gcc / इनलाइन होनी चाहिए।

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

अगर हम बड़े तार के दुर्लभ होने की उम्मीद करते हैं, तो उस मामले के लिए libx से 1.7x धीमा। 1M बाइट्स की लंबाई का मतलब है कि यह मेरे सीपीयू पर L2 (256k) या L1d कैश (32k) में गर्म नहीं रहेगा, इसलिए L3 कैश पर भी अड़चन तेजी से बढ़ गई। (संभवतः एक अनियंत्रित लूप और 256-बिट वैक्टर आरओबी को प्रति बाइट के साथ कई उफ़ तक नहीं रोकते हैं, इसलिए ओओओ निष्पादन आगे तक आगे देख सकता है और अधिक स्मृति समानता प्राप्त कर सकता है, विशेष रूप से पृष्ठ सीमाओं पर।)

लेकिन L3 कैश बैंडविड्थ संभवतः एक टोंटी है जो 4-uop संस्करण को प्रति घड़ी 1 पुनरावृत्ति पर चलने से रोकती है, इसलिए हम AVX से कम लाभ देख रहे हैं जो हमें लूप में एक यूओपी बचा रहा है। L1d कैश में डेटा हॉट होने के साथ, हमें 1.25 साइकिल प्रति पुनरावृत्ति बनाम 1 प्राप्त करना चाहिए।

लेकिन एक अच्छा एवीएक्स 2 कार्यान्वयन 64 बाइट्स प्रति चक्र (2x 32 बाइट लोड) तक पढ़ सकता है जो शून्य की जाँच करने से पहले जोड़े को जोड़ते हुए और जहां वे थे वहां वापस जाने के लिए vpminub का उपयोग करते हैं। इस और libc के बीच का अंतर ~ 2k से ~ 30 kiB के आकार के लिए व्यापक रूप से खुलता है या L1d में गर्म रहता है।

केवल लंबाई = 1000 के साथ कुछ रीड-ओनली परीक्षण बताता है कि L1d कैश में मध्यम आकार के स्ट्रिंग्स के लिए ग्लिबैक स्ट्रलेन मेरे लूप की तुलना में लगभग 4 गुना अधिक तेज है । AVX2 के लिए यह बड़ा है कि बड़े अनियंत्रित लूप को रैंप किया जा सकता है, लेकिन फिर भी आसानी से L1d कैश में फिट हो जाता है। (पढ़ें-केवल स्टोर-फ़ॉरवर्डिंग स्टालों से बचें, और इसलिए हम कई पुनरावृत्तियों कर सकते हैं)

यदि आपके तार इतने बड़े हैं, तो आपको strlen की आवश्यकता के बजाय स्पष्ट-लंबाई वाले स्ट्रिंग्स का उपयोग करना चाहिए, इसलिए एक साधारण लूप को इनलाइन करना अभी भी एक उचित रणनीति की तरह लगता है, जब तक कि यह वास्तव में शॉर्ट स्ट्रिंग्स के लिए अच्छा है और मध्यम के लिए कुल कचरा नहीं है। (300 बाइट्स की तरह) और बहुत लंबा (> कैश आकार) तार।

इसके साथ छोटे तारों को बेंचमार्क करना:

मेरे द्वारा अपेक्षित परिणाम प्राप्त करने की कोशिश में मैं कुछ विषमताओं में भाग गया:

मैंने प्रत्येक पुनरावृत्ति (छोटी निरंतर लंबाई की अनुमति) से पहले स्ट्रिंग को छोटा करने के लिए s[31] = 0 की कोशिश की। लेकिन तब मेरा SSE2 संस्करण लगभग GCC के संस्करण के समान गति था। स्टोर-फ़ॉरवर्डिंग स्टाल अड़चन थे! एक बाइट स्टोर जिसके बाद एक व्यापक भार होता है, स्टोर-फ़ॉरवर्डिंग को धीमा रास्ता देता है जो स्टोर बफर से बाइट्स को L1d कैश से मर्ज करता है। यह अतिरिक्त विलंबता, अगली चाल के लिए स्टोर इंडेक्स की गणना करने के लिए स्ट्रिंग के अंतिम 4-बाइट या 16-बाइट चंक के माध्यम से एक लूप-किए गए डिप चेन का हिस्सा है।

GCC का धीमा 4-बाइट-एट-ए-टाइम कोड उस विलंबता की छाया में पहले के 4-बाइट विखंडू को संसाधित करके रख सकता है। (आउट-ऑफ-ऑर्डर निष्पादन बहुत शानदार है: धीमा कोड कभी-कभी आपके प्रोग्राम की समग्र गति को प्रभावित नहीं कर सकता है)।

मैंने अंततः इसे केवल पढ़ने के लिए संस्करण बनाकर हल किया, और इनलाइन एएसएम का उपयोग करके कंपाइलर को लूप से बाहर निकलने वाले strlen से रोकने के लिए उपयोग किया।

लेकिन स्टोर-फ़ॉरवर्डिंग 16-बाइट लोड का उपयोग करने के साथ एक संभावित मुद्दा है। यदि अन्य C चर को सरणी के अंत में संग्रहीत किया जाता है, तो हम संकरी दुकानों की तुलना में सरणी के अंत में लोड करने के कारण एक SF स्टॉल मार सकते हैं। हाल ही में कॉपी किए गए डेटा के लिए, हम ठीक हैं यदि इसे 16-बाइट या व्यापक संरेखित स्टोर के साथ कॉपी किया गया था, लेकिन छोटी प्रतियों के लिए glibc memcpy 2x ओवरलैपिंग लोड करता है जो ऑब्जेक्ट के प्रारंभ और अंत से पूरे ऑब्जेक्ट को कवर करता है। फिर यह दोनों को स्टोर करता है, फिर से ओवरलैपिंग करता है, मेमोव एसकेएक्स ओवरलैप डीएसटी केस को मुफ्त में हैंडल करता है। तो 2 16-बाइट या 8-बाइट की एक छोटी स्ट्रिंग का टुकड़ा जो कि सिर्फ यादगार था, हमें आखिरी चंक पढ़ने के लिए एक एसएफ स्टाल दे सकता है। (वह जो आउटपुट के लिए डेटा निर्भरता रखता है।)

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

अन्य विचित्रता मुझे पूरी तरह से समझ नहीं आई:

कोड संरेखण केवल पढ़ने के लिए 2 अंतर का कारक बना रहा है, आकार = 1000 ( s[1000] = 0; )। लेकिन सबसे आंतरिक asm लूप स्वयं .p2align 4 या .p2align 5 साथ संरेखित होता है। लूप संरेखण में वृद्धि इसे 2 के कारक से धीमा कर सकती है!

# slow version, with *no* extra HIDE_ALIGNMENT function call before the loop.
# using my hand-written asm, AVX version.
  i<1280000 read-only at strlen(s)=1000 so strlen time dominates the total runtime (not startup overhead)
  .p2align 5 in the asm inner loop. (32-byte code alignment with NOP padding)

gcc -DUSE_ASM -DREAD_ONLY -DHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}'

 Performance counter stats for './a.out' (100 runs):

             40.92 msec task-clock                #    0.996 CPUs utilized            ( +-  0.20% )
                 2      context-switches          #    0.052 K/sec                    ( +-  3.31% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.008 M/sec                    ( +-  0.05% )
       168,103,223      cycles                    #    4.108 GHz                      ( +-  0.20% )
        82,293,840      branches                  # 2011.269 M/sec                    ( +-  0.00% )
         1,845,647      branch-misses             #    2.24% of all branches          ( +-  0.74% )
       412,769,788      instructions              #    2.46  insn per cycle           ( +-  0.00% )
       466,515,986      uops_issued.any           # 11401.694 M/sec                   ( +-  0.22% )
       487,011,558      uops_executed.thread      # 11902.607 M/sec                   ( +-  0.13% )

         0.0410624 +- 0.0000837 seconds time elapsed  ( +-  0.20% )

40326.5   (clock_t)

real    0m4.301s
user    0m4.050s
sys     0m0.224s

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

संभवतः आंतरिक और बाहरी पाश-शाखाएं एक-दूसरे को अलियास कर रही हैं, या नहीं।

निर्देश गणना लगभग समान है, आंतरिक लूप के आगे बाहरी लूप में कुछ एनओपी द्वारा अलग है। लेकिन आईपीसी काफी भिन्न है: समस्याओं के बिना, तेज संस्करण पूरे कार्यक्रम के लिए प्रति घड़ी औसतन 4.82 निर्देश चलाता है। (इनमें से अधिकांश आंतरिक-सबसे अधिक लूप में है जो प्रति चक्र 5 निर्देश चला रहा है, एक परीक्षण / jz के लिए धन्यवाद जो मैक्रो-फ़्यूज़ 2 निर्देशों को 1 यूओपी में देता है।) और ध्यान दें कि uops_executed uops_issued की तुलना में बहुत अधिक है: इसका मतलब है कि सूक्ष्म संलयन है फ्रंट-एंड टोंटी के माध्यम से और अधिक उफ़ पाने के लिए अच्छी तरह से काम करना।

fast version, same read-only strlen(s)=1000 repeated 1280000 times

gcc -DUSE_ASM -DREAD_ONLY -UHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}' 

 Performance counter stats for './a.out' (100 runs):

             21.06 msec task-clock                #    0.994 CPUs utilized            ( +-  0.10% )
                 1      context-switches          #    0.056 K/sec                    ( +-  5.30% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.015 M/sec                    ( +-  0.04% )
        86,239,943      cycles                    #    4.094 GHz                      ( +-  0.02% )
        82,285,261      branches                  # 3906.682 M/sec                    ( +-  0.00% )
            17,645      branch-misses             #    0.02% of all branches          ( +-  0.15% )
       415,286,425      instructions              #    4.82  insn per cycle           ( +-  0.00% )
       335,057,379      uops_issued.any           # 15907.619 M/sec                   ( +-  0.00% )
       409,255,762      uops_executed.thread      # 19430.358 M/sec                   ( +-  0.00% )

         0.0211944 +- 0.0000221 seconds time elapsed  ( +-  0.10% )

20504  (clock_t)

real    0m2.309s
user    0m2.085s
sys     0m0.203s

मुझे लगता है कि यह सिर्फ शाखा की भविष्यवाणी है, अन्य फ्रंट-एंड सामान नहीं है जो एक समस्या है। परीक्षण / शाखा निर्देश एक सीमा के पार विभाजित नहीं हो रहे हैं जो मैक्रो-फ्यूजन को रोकेंगे।

.p2align 5 से .p2align 4 को बदलना उन्हें उलट देता है: -UHIDE_ALIGNMENT धीमा हो जाता है।

यह गॉडबोल्ट बाइनरी लिंक दोनों मामलों के लिए आर्क लिनक्स पर gcc8.2.1 के साथ मैं देख रहा हूँ उसी पैडिंग को पुन: पेश करता है: 2x 11-बाइट nopw + फास्ट केस के लिए बाहरी लूप के अंदर 3-बाइट nop । इसका सटीक स्रोत भी है जिसका मैं स्थानीय स्तर पर उपयोग कर रहा था।

शॉर्ट स्ट्रेलेन रीड-ओनली माइक्रो-बेंचमार्क:

चुने हुए सामान के साथ परीक्षण किया जाता है ताकि यह शाखा की गड़बड़ी या स्टोर-फ़ॉरवर्डिंग से ग्रस्त न हो, और सार्थक डेटा प्राप्त करने के लिए पर्याप्त पुनरावृत्तियों के लिए एक ही छोटी लंबाई का बार-बार परीक्षण कर सके।

strlen=33 , इसलिए टर्मिनेटर 3rd 16-बाइट वेक्टर की शुरुआत के पास है। (मेरा संस्करण 4-बाइट संस्करण बनाम जितना संभव हो उतना बुरा दिखता है।) -DREAD_ONLY , और i<1280000 बाहरी लूप रिपीट लूप के रूप में।

  • 1933 घड़ी_ट: मेरा एएसएम : अच्छा और सुसंगत सर्वश्रेष्ठ-केस समय (शोर नहीं है / जब औसत चल रहा है तब चारों ओर उछल रहा है।) लंबे समय तक -DHIDE_ALIGNMENT के विपरीत / बिना -DHIDE_ALIGNMENT साथ समान -DHIDE_ALIGNMENT । लूप शाखा बहुत कम पैटर्न के साथ अधिक आसानी से अनुमानित है। (स्ट्रलेन = 33, 1000 नहीं)।
  • 3220 घड़ी_टी: जीसीसी -ओ 3 स्ट्रलेन । ( -DHIDE_ALIGNMENT )
  • 6100 घड़ी_टी: जीसीसी -ओ 3 4-बाइट लूप
  • 37200 घड़ी_टी: जीसीसी -ओ 1 रेप्स एससबीबी

तो कम तारों के लिए, मेरा सरल इनलाइन लूप jmp [mem] को एक लाइब्रेरी फ़ंक्शन कॉल धड़कता है जिसे jmp [mem] (कॉल + jmp [mem] ) से jmp [mem] , फिर jmp [mem] के स्टार्टअप ओवरहेड को चलाएं जो संरेखण पर निर्भर नहीं हो सकता है।

नगण्य शाखा-मिसप्रेड्स थे, जैसे कि स्ट्रेंन strlen(s)=33 साथ सभी संस्करणों के लिए 0.05%। रेप्स scasb संस्करण में 0.46% था, लेकिन यह कम कुल शाखाओं से बाहर था। कोई सही ढंग से भविष्यवाणी की गई शाखाओं को रैक करने के लिए कोई आंतरिक लूप नहीं।

ब्रांच repz scasb और कोड-कैश हॉट के साथ, repz scasb बाइट स्ट्रिंग के लिए repz scasb को कॉल करने से 10x से अधिक खराब है। यह वास्तविक उपयोग के मामलों में कम बुरा होगा जहां strlen शाखा-कैश या स्टाल में भी छूट सकता है, लेकिन सीधी-रेखा repz scasb नहीं होगा। लेकिन 10x बड़ा है, और यह काफी कम स्ट्रिंग के लिए है।






glibc