c++ - संयुक्त लूप की तुलना में अलग-अलग loops में elementwise जोड़ों को बहुत तेज क्यों हैं?




performance compiler-optimization vectorization (9)

दूसरे लूप में बहुत कम कैश गतिविधि शामिल है, इसलिए प्रोसेसर को स्मृति मांगों के साथ रखना आसान है।

मान लीजिए कि a1 b1 , b1 , c1 , और d1 प्वाइंट हेप मेमोरी और मेरे न्यूमेरिकल कोड में निम्नलिखित कोर लूप है।

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

इस लूप को लूप के for एक और बाहरी के माध्यम से 10,000 बार निष्पादित for है। इसे तेज करने के लिए, मैंने कोड को बदल दिया:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

इंटेल कोर 2 डुओ (x64) पर 32-बिट के लिए पूर्ण अनुकूलन और SSE2 सक्षम के साथ एमएस विजुअल सी ++ 10.0 पर संकलित, पहला उदाहरण 5.5 सेकंड लेता है और डबल-लूप उदाहरण केवल 1.9 सेकंड लेता है। मेरा सवाल है: (कृपया नीचे दिए गए मेरे संदर्भित प्रश्न का संदर्भ लें)

पीएस: मुझे यकीन नहीं है, अगर यह मदद करता है:

पहले लूप के लिए डिस्सेप्लर मूल रूप से इस तरह दिखते हैं (इस ब्लॉक को पूरे कार्यक्रम में लगभग पांच बार दोहराया जाता है):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

डबल लूप उदाहरण का प्रत्येक पाश इस कोड का उत्पादन करता है (निम्न ब्लॉक को तीन बार दोहराया जाता है):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

प्रश्न कोई प्रासंगिकता के रूप में सामने आया, क्योंकि व्यवहार गंभीर रूप से सरणी (एन) और सीपीयू कैश के आकार पर निर्भर करता है। तो यदि और रुचि है, तो मैं इस सवाल को दोहराता हूं:

क्या आप निम्नलिखित ग्राफ पर पांच क्षेत्रों द्वारा दिखाए गए विभिन्न कैश व्यवहारों के कारण विवरणों में कुछ ठोस अंतर्दृष्टि प्रदान कर सकते हैं?

इन CPUs के लिए एक समान ग्राफ प्रदान करके, CPU / कैश आर्किटेक्चर के बीच अंतर को इंगित करना भी दिलचस्प हो सकता है।

पीपीएस: यहां पूरा कोड है। यह उच्च रिज़ॉल्यूशन समय के लिए TBB Tick_Count का उपयोग करता है, जिसे TBB_TIMING मैक्रो को परिभाषित नहीं किया जा सकता है:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(यह n विभिन्न मूल्यों के लिए एफएलओपी / एस दिखाता है।)


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

पहला कोड प्रत्येक लूप पर उन्हें दूर करने वाले दूरस्थ स्मृति पते को संशोधित करता है, इस प्रकार लगातार कैश को अमान्य करने की आवश्यकता होती है।

दूसरा कोड वैकल्पिक नहीं है: यह सिर्फ दो बार आसन्न पते पर बहता है। यह सभी काम को कैश में पूरा करने के लिए बनाता है, इसे दूसरी लूप शुरू होने के बाद ही अमान्य कर देता है।


यह पुराना सी ++ और अनुकूलन हो सकता है। मेरे कंप्यूटर पर मैंने लगभग एक ही गति प्राप्त की:

एक पाश: 1.577 एमएस

दो लूप: 1.507 एमएस

मैं 16 जीबी रैम के साथ एक ई 5-1620 3.5 गीगाहर्ट्ज प्रोसेसर पर विजुअल स्टूडियो 2015 चलाता हूं।


मूल प्रश्न

दो लूप की तुलना में एक लूप इतना धीमा क्यों है?

निष्कर्ष:

केस 1 एक क्लासिक इंटरपोलेशन समस्या है जो एक अक्षम व्यक्ति होता है। मुझे यह भी लगता है कि यह कई प्रमुख कारणों में से एक था कि क्यों कई मशीन आर्किटेक्चर और डेवलपर्स मल्टी-थ्रेडेड अनुप्रयोगों के साथ-साथ समांतर प्रोग्रामिंग करने की क्षमता के साथ मल्टी-कोर सिस्टम का निर्माण और डिजाइन समाप्त कर चुके थे।

इस तरह के दृष्टिकोण से इसे देखकर हार्डवेयर, ओएस और कंपाइलर कैसे रैप, कैश, पेज फाइल्स इत्यादि के साथ काम करने वाले ढेर आवंटन करने के लिए मिलकर काम करते हैं; गणित जो इन एल्गोरिदम की नींव पर हैं, हमें दिखाता है कि इनमें से कौन सा बेहतर समाधान है। हम एक समानता का उपयोग कर सकते हैं जहां एक Boss या Summation जो Summation For Loop प्रतिनिधित्व करेगा, जिसे श्रमिक A और B बीच यात्रा करना है, हम आसानी से देख सकते हैं कि केस 2 कम से कम 1/2 जितना तेज़ होगा यदि मामला 1 से थोड़ा अधिक नहीं है यात्रा के लिए आवश्यक दूरी और श्रमिकों के बीच किए गए समय में अंतर। यह गणित बेंच मार्क टाइम्स के साथ-साथ असेंबली निर्देशों में अंतर की मात्रा दोनों के साथ लगभग वर्चुअल और पूरी तरह से ऊपर है।

अब मैं यह बताना शुरू कर दूंगा कि यह सब नीचे कैसे काम करता है।

समस्या का आकलन

ओपी का कोड:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

तथा

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

विचार

लूप के 2 प्रकारों के बारे में ओपी के मूल प्रश्न को ध्यान में रखते हुए और अन्य उत्कृष्ट उत्तरों और उपयोगी टिप्पणियों के साथ-साथ कैश के व्यवहार की दिशा में उनके संशोधित प्रश्न को ध्यान में रखते हुए; मैं इस स्थिति और समस्या के बारे में एक अलग दृष्टिकोण लेकर यहां कुछ अलग करने की कोशिश करना चाहता हूं।

पहुंच

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

परिदृश्य

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

हम क्या जानते हैं

हम जानते हैं कि उसका पाश 100,000 बार चलाएगा।हम यह भी जानते हैं कि a1, b1, c1औरd164-बिट आर्किटेक्चर पर पॉइंटर्स हैं। 32-बिट मशीन पर सी ++ के भीतर सभी पॉइंटर्स 4 बाइट्स हैं और 64-बिट मशीन पर वे आकार में 8 बाइट हैं क्योंकि पॉइंटर्स निश्चित लंबाई के हैं। हम जानते हैं कि हमारे पास 32 बाइट हैं जिनमें दोनों मामलों में आवंटित किया जाना है। एकमात्र अंतर यह है कि हम प्रत्येक बाइटन पर 32 बाइट्स या 2-8bytes के 2 सेट आवंटित कर रहे हैं, जहां दूसरे मामले में हम दोनों स्वतंत्र लूप के लिए प्रत्येक पुनरावृत्ति के लिए 16 बाइट आवंटित कर रहे हैं। इसलिए कुल आवंटन में दोनों लूप अभी भी 32 बाइट्स के बराबर हैं। इस जानकारी के साथ आगे बढ़ें और इसके सामान्य गणित, एल्गोरिदम और समानता दिखाएं। हम जानते हैं कि दोनों मामलों में एक ही सेट या संचालन के समूह को कितनी बार किया जाना चाहिए। हम उन दोनों मेमोरी की मात्रा जानते हैं जिन्हें दोनों मामलों में आवंटित करने की आवश्यकता है।हम गधे लगा सकते हैं कि दोनों मामलों के बीच आवंटन का समग्र कार्य भार लगभग समान होगा।

हम क्या नहीं जानते

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

आइए जांच करें

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

हमारे दावे:

  • हम अपने लूप और इसके पुनरावृत्तियों को एक सारांश बनेंगे जो 1 से शुरू होता है और लूप के रूप में 0 से शुरू करने के बजाय 100000 पर समाप्त होता है क्योंकि हमें मेमोरी एड्रेसिंग की 0 इंडेक्सिंग योजना के बारे में चिंता करने की आवश्यकता नहीं है क्योंकि हम केवल रुचि रखते हैं खुद एल्गोरिदम।
  • दोनों मामलों में हमारे पास काम करने के लिए 4 कार्य हैं और 2 फ़ंक्शन कॉल हैं जिनमें प्रत्येक फ़ंक्शन कॉल पर 2 ऑपरेशन किए जा रहे हैं। इसलिए हम इन सेट हो जाएगा के रूप में कार्य करता है और समारोह होने के लिए कहता है F1(), F2(), f(a), f(b), f(c)और f(d)

एल्गोरिदम:

पहला मामला: - केवल एक सारांश लेकिन दो स्वतंत्र समारोह कॉल।

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

दूसरा मामला: - दो सारांश - लेकिन प्रत्येक का अपना कार्य कॉल है।

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

यदि आपने देखा कि F2()केवल Sumदोनों में मौजूद है Sum1और Sum2केवल इसमें शामिल है F1()। यह बाद में भी स्पष्ट होगा जब हम यह निष्कर्ष निकालना शुरू करेंगे कि दूसरे एल्गोरिदम से एक अनुकूलन हो रहा है।

पहले मामले के माध्यम से पुनरावृत्तियों को Sumकॉल किया जाता है f(a)जो स्वयं को जोड़ देगा, f(b)फिर यह कॉल f(c)करेगा जो वही करेगा लेकिन f(d)प्रत्येक के लिए स्वयं को जोड़ देगा 100000 iterations। दूसरे मामले में हमारे पास है Sum1और Sum2दोनों ही कार्य करते हैं जैसे कि वे एक ही कार्य को पंक्ति में दो बार बुला रहे थे। इस मामले में हम इलाज कर सकते हैं Sum1और Sum2केवल सादे पुराने के रूप में Sumजहां Sumइस मामले में ऐसा लगता है: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }और अब यह एक अनुकूलन की तरह दिखता है जहां हम इसे एक ही समारोह के रूप में मान सकते हैं।

एनालॉजी के साथ सारांश

दूसरे मामले में हमने जो देखा उसके साथ यह लगभग प्रतीत होता है जैसे ऑप्टिमाइज़ेशन है क्योंकि दोनों के लिए लूप के समान सटीक हस्ताक्षर हैं, लेकिन यह वास्तविक समस्या नहीं है। मुद्दा काम कर रहा है कि द्वारा किया जा रहा नहीं है f(a), f(b), f(c)और f(d)दोनों ही मामलों और दोनों के बीच तुलना में यह दूरी योग दोनों ही मामलों है कि आप समय निष्पादन में अंतर देता में यात्रा करने के लिए है कि में अंतर है।

के बारे में सोचो For Loopsहोने के रूप में Summationsहै कि एक होने के रूप में पुनरावृत्तियों करता है Bossदो लोगों के लिए है कि आदेश दे रहा है Aऔर Bऔर कहा कि अपनी नौकरी मांस के लिए कर रहे Cऔर Dक्रमश: और उनमें से कुछ पैकेज लेने और इसे वापस करने के लिए। यहां समानता में लूप या संक्षेप में पुनरावृत्ति और स्थिति जांच स्वयं वास्तव में प्रतिनिधित्व नहीं करती है Boss। क्या वास्तव में प्रतिनिधित्व Bossयहां वास्तविक गणितीय एल्गोरिदम सीधे से नहीं है, लेकिन की वास्तविक अवधारणा से Scopeऔर Code Blockएक नियमित या उप दिनचर्या, विधि, समारोह, अनुवाद इकाई, आदि के भीतर जहां 2 एल्गोरिथ्म 2 है पहले एल्गोरिथ्म 1 गुंजाइश है लगातार scopes।

प्रत्येक कॉल पर्ची पर पहले मामले में Bossजाता है Aऔर ऑर्डर देता है और पैकेज Aलाने के B'sलिए Bossचला जाता Cहै तो ऑर्डर देता है और ऑर्डर देता है और Dप्रत्येक पुनरावृत्ति पर पैकेज प्राप्त करता है ।

दूसरे मामले में Bossसीधे सभी कामों को प्राप्त होने तक पैकेज Aलाने और B'sपैकेज लाने के लिए काम करता है । फिर सभी संकुल प्राप्त करने के लिए ऐसा करने के Bossसाथ काम करता है।CD's

चूंकि हम 8 बाइट पॉइंटर के साथ काम कर रहे हैं और हीप आवंटन से निपटने के लिए चलिए इस समस्या को यहां मानते हैं। आइए हम कहें कि Boss100 फीट से Aऔर वह A500 फीट से है C। हमें इस बारे में चिंता करने की आवश्यकता नहीं है कि निष्पादन के आदेश के कारण Bossशुरुआत में कितनी दूर है C। दोनों मामलों में Bossशुरुआत में Aपहले से यात्रा करता है B। यह समानता यह नहीं कहना है कि यह दूरी सटीक है; यह एल्गोरिदम की कार्यप्रणाली दिखाने के लिए केवल एक प्रयोग परीक्षण केस परिदृश्य है। कई मामलों में ढेर आवंटन करते समय और कैश और पेज फ़ाइलों के साथ काम करते समय, पता स्थानों के बीच की दूरी भिन्नता में भिन्न नहीं हो सकती है या वे डेटा प्रकारों और सरणी आकारों की प्रकृति के आधार पर बहुत महत्वपूर्ण हो सकती हैं।

टेस्ट मामले:

पहला मामला: पहली बार पुनरावृत्ति परBossआदेश को पर्ची देनेAऔरAबंदकरने के लिए 100 फीट जानापड़ता है और उसकी बात करता है, लेकिन फिरउसेBoss500 फीट की यात्राCकरने के लिए उसे ऑर्डर पर्ची देने केलिएजानापड़ता है। फिर अगले पुनरावृत्ति और दो अन्य पुनरावृत्ति के बादBossदोनों के बीच 500 फीट आगे बढ़ना होगा।

दूसरा मामला: The Boss पहले पुनरावृत्ति पर 100 फीट की यात्रा करना हैA, लेकिन उसके बाद वह पहले से ही वहां है औरAसभी पर्ची भरने तकबसवापस आने कीप्रतीक्षा कर रहा है। फिरBossपहले पुनरावृत्ति पर 500 फीट की यात्रा करना हैCक्योंकिC500 फीट सेAयहBoss( Summation, For Loop )काम करने के बाद सही कहा जा रहा हैAऔर फिर इंतजार कर रहा हैAजब तकC'sऑर्डर स्लिप्स नहीं किया जाता है।

दूरियों में अंतर यात्रा की

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

मनमानी मूल्यों की तुलना

हम आसानी से देख सकते हैं कि 600 10 मिलियन से भी कम है। अब यह सटीक नहीं है, क्योंकि हम दूरी के वास्तविक अंतर को नहीं जानते हैं कि रैम के पते या किस कैश या पेज फ़ाइल प्रत्येक पुनरावृत्ति पर प्रत्येक कॉल कई अन्य अदृश्य चर के कारण होने जा रहा है, लेकिन यह सिर्फ परिस्थिति का आकलन और सबसे बुरी स्थिति परिदृश्य से इसे देखने की कोशिश कर रहा है।

तो इन संख्याओं से यह लगभग दिखता है जैसे एल्गोरिदम एक एल्गोरिदम दो की तुलना में 99% धीमा होना चाहिए; हालांकि, यह केवल है The Boss'sहिस्सा है या एल्गोरिदम की जिम्मेदारी है और यह वास्तविक श्रमिकों के लिए खाते में नहीं है A, B, C, और Dऔर क्या वे एक और लूप के हर यात्रा पर क्या करना है। तो मालिकों का काम केवल कुल काम का लगभग 15 - 40% होता है। तो श्रमिकों के माध्यम से किए गए काम का बड़ा हिस्सा गति दर के अंतर को अनुपात में 50-70% तक रखने के प्रति थोड़ा बड़ा प्रभाव पड़ता है

निरीक्षण: - दो एल्गोरिदम के बीच मतभेद

इस स्थिति में यह काम की प्रक्रिया की संरचना है और यह दिखाता है कि केस 2 समान कार्य घोषणा और परिभाषा के आंशिक अनुकूलन दोनों से अधिक कुशल है जहां यह केवल वेरिएबल्स है जो नाम से अलग हैं । और हम यह भी देखते हैं कि केस 1 में यात्रा की गई कुल दूरी केस 2 में कहीं अधिक है और हम इस दूरी पर विचार कर सकते हैं कि हमारे एल्गोरिदम के बीच हमारे टाइम फैक्टर की यात्रा की गई । प्रकरण 1 के मामले 2 की तुलना में करने के लिए काफी अधिक काम है। यह सबूत में भी देखा गया थाASMजो दोनों मामलों के बीच दिखाया गया था। यहां तक कि के साथ क्या था पहले से ही इन मामलों के बारे में कहा था, यह भी सच है के लिए खाते में नहीं है कि में केस 1 मालिक दोनों के लिए प्रतीक्षा करनी होगी Aऔर Cवापस पाने के लिए इससे पहले कि वह वापस लिए जा सकते हैं Aअगले चरण पर फिर से और यह भी नहीं करता है तथ्य यह है कि अगर के लिए 'टी खाते Aया Bतो एक बहुत ही समय लग रहा है दोनों Bossऔर अन्य कार्यकर्ता (रों) भी एक निष्क्रिय पर इंतजार कर रहे हैं। में केस 2 केवल एक ही जा रहा है बेकार है Bossजब तक कार्यकर्ता वापस हो जाता है। तो इसका भी एल्गोरिदम पर असर पड़ता है।

ओपी संशोधित प्रश्न (ओं)

संपादित करें: प्रश्न कोई प्रासंगिकता के रूप में सामने आया, क्योंकि व्यवहार गंभीर रूप से सरणी (एन) और सीपीयू कैश के आकार पर निर्भर करता है। तो यदि और रुचि है, तो मैं इस सवाल को दोहराता हूं:

क्या आप निम्नलिखित ग्राफ पर पांच क्षेत्रों द्वारा दिखाए गए विभिन्न कैश व्यवहारों के कारण विवरणों में कुछ ठोस अंतर्दृष्टि प्रदान कर सकते हैं?

इन CPUs के लिए एक समान ग्राफ प्रदान करके, CPU / कैश आर्किटेक्चर के बीच अंतर को इंगित करना भी दिलचस्प हो सकता है।

इन सवालों के बारे में

जैसा कि मैंने बिना संदेह के प्रदर्शन किया है, हार्डवेयर और सॉफ्टवेयर शामिल होने से पहले भी एक अंतर्निहित मुद्दा है। अब पेज फाइलों के साथ मेमोरी और कैशिंग के प्रबंधन के लिए, जो सभी सिस्टम के एकीकृत सेट में एक साथ काम करते हैं: The Architecture{हार्डवेयर, फर्मवेयर, कुछ एंबेडेड ड्राइवर्स, कर्नल और एएसएम निर्देश समूह}, The OS{फाइल और मेमोरी मैनेजमेंट सिस्टम , ड्राइवर्स और रजिस्ट्री}, The Compiler{स्रोत कोड के अनुवाद इकाइयों और अनुकूलन}, और यहां तक ​​कि Source Codeखुद को विशिष्ट एल्गोरिदम के सेट (सेट) के साथ; हम पहले से ही देख सकते हैं एक टोंटी है कि पहले एल्गोरिथ्म के भीतर क्या हो रहा है इससे पहले कि हम भी किसी भी मनमाने ढंग से साथ किसी भी मशीन पर लागू है कि वहाँ Architecture, OSऔरProgrammable Languageदूसरे एल्गोरिदम की तुलना में। तो एक आधुनिक कंप्यूटर के अंतर्निहित शामिल होने से पहले पहले से ही एक समस्या मौजूद थी।

समापन परिणाम

हालाँकि; यह कहना नहीं है कि ये नए प्रश्न महत्व के नहीं हैं क्योंकि वे स्वयं हैं और वे सभी के बाद एक भूमिका निभाते हैं। वे प्रक्रियाओं और समग्र प्रदर्शन को प्रभावित करते हैं और यह उन लोगों के विभिन्न ग्राफ और आकलन के साथ स्पष्ट है जिन्होंने अपना उत्तर (ओं) और टिप्पणी दी है। आप के सादृश्य पर ध्यान देना तो Bossऔर दो कार्यकर्ताओं Aऔर Bजो था जाने के लिए और से संकुल को पुनः प्राप्त करने Cऔर Dक्रमशः और प्रश्न में दो एल्गोरिदम के गणितीय अंकन पर विचार आप देख सकते हैं कि कंप्यूटर की भी भागीदारी के बिना Case 2लगभग 60% है की तुलना में तेजCase 1 और जब आप इन एल्गोरिदम को स्रोत कोड पर लागू करने के बाद ग्राफ़ और चार्ट देखते हैं, तो दिए गए हार्डवेयर पर संचालन करने के लिए ओएस के माध्यम से संकलित और अनुकूलित और निष्पादित किया जाता है, तो आप इन एल्गोरिदम में अंतरों के बीच थोड़ा अधिक गिरावट भी देखते हैं।

अब यदि "डेटा" सेट काफी छोटा है तो यह पहले किसी अंतर के खराब नहीं लग सकता है, लेकिन समय के निष्पादन में मतभेदों के संदर्भ में हम इस कार्य के विकास को देखकर धीमे होने के Case 1बारे में बता सकते हैं:60 - 70%Case 2

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

और यह अनुमान इन दोनों लूपों के बीच औसत अंतर है जो एल्गोरिदमिक और मशीन ऑपरेशंस दोनों सॉफ़्टवेयर ऑप्टिमाइज़ेशन और मशीन निर्देशों से युक्त है। तो जब डेटा सेट रैखिक रूप से बढ़ता है, तो दोनों के बीच समय में अंतर होता है। एल्गोरिदम 1 में एल्गोरिदम 2 की तुलना में अधिक fetches हैं जो स्पष्ट है जब पहली बार पुनरावृत्ति के बाद और प्रत्येक पुनरावृत्ति के लिए Bossअधिकतम दूरी के दौरान यात्रा करना था , जबकि एल्गोरिदम 2 को एक बार यात्रा करना पड़ा और उसके बाद उसे यात्रा करना पड़ा एक अधिकतम दूरी केवल एक समय था जब से जा रहा करने के लिए ।ACBossAAAC

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


ऐसा इसलिए है क्योंकि सीपीयू में इतने सारे कैश मिस नहीं हैं (जहां इसे रैम चिप्स से आने वाले सरणी डेटा के लिए इंतजार करना पड़ता है)। आपके लिए लगातार सरणी के आकार को समायोजित करना दिलचस्प होगा ताकि आप स्तर 1 कैश (एल 1) के आकार को पार कर सकें, और उसके बाद अपने सीपीयू के स्तर 2 कैश (एल 2) और अपने कोड के लिए लिया गया समय साजिश करें सरणी के आकार के खिलाफ निष्पादित करने के लिए। ग्राफ़ एक सीधी रेखा नहीं होनी चाहिए जैसा आप उम्मीद करेंगे।


मैं यहां चर्चा किए गए परिणामों को दोहराना नहीं कर सकता।

मुझे नहीं पता कि खराब बेंचमार्क कोड दोष देना है या क्या, लेकिन निम्नलिखित विधियों का उपयोग करके मेरी मशीन पर दो विधियां एक दूसरे के 10% के भीतर हैं, और एक लूप आमतौर पर दो से थोड़ा तेज है - जैसा कि आप चाहते हैं उम्मीद करते हैं।

आठ लूप का उपयोग करते हुए ऐरे आकार 2 ^ 16 से 2 ^ 24 तक थे। मैं स्रोत सरणी को प्रारंभ करने के लिए सावधान था, इसलिए += असाइनमेंट FPU से FPU गई स्मृति कचरा जोड़ने के लिए नहीं कह रहा था।

मैंने विभिन्न योजनाओं के साथ खेला, जैसे लूप के अंदर b[j] , d[j] को InitToZero[j] के असाइनमेंट को डालने और += b[j] = 1 और += d[j] = 1 , और मुझे काफी लगातार परिणाम मिल गए।

जैसा कि आप उम्मीद कर सकते हैं, InitToZero[j] का उपयोग करते हुए लूप के अंदर b और d को प्रारंभ करना संयुक्त दृष्टिकोण को एक लाभ प्रदान करता है, क्योंकि उन्हें a और c के असाइनमेंट से पहले बैक-टू-बैक किया जाता था, लेकिन फिर भी 10% के भीतर। जाओ पता लगाओ।

हार्डवेयर पीएल 3 कोर i7 @ 3.4 गीगाहर्ट्ज और 8 जीबी मेमोरी के साथ डेल एक्सपीएस 8500 है । आठ लूप का उपयोग करते हुए 2 ^ 16 से 2 ^ 24 के लिए, संचयी समय क्रमश: 44.987 और 40.965 था। दृश्य सी ++ 2010, पूरी तरह से अनुकूलित।

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

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

मुझे यकीन नहीं है कि क्यों निर्णय लिया गया कि एमएफएलपीएस एक प्रासंगिक मीट्रिक था। हालांकि, विचार स्मृति स्मृति पर ध्यान केंद्रित करना था, इसलिए मैंने फ़्लोटिंग पॉइंट गणना समय की मात्रा को कम करने की कोशिश की। मैंने += में छोड़ा, लेकिन मुझे यकीन नहीं है कि क्यों।

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


पहला लूप प्रत्येक चर में लिखने को वैकल्पिक बनाता है। दूसरे और तीसरे वाले तत्व केवल तत्व आकार के छोटे कूद बनाते हैं।

20 पारियों से अलग कलम और पेपर के साथ 20 पारियों की दो समांतर रेखाओं को लिखने का प्रयास करें। एक बार और फिर दूसरी पंक्ति को खत्म करने का प्रयास करें और वैकल्पिक रूप से प्रत्येक पंक्ति में एक क्रॉस लिखकर एक और समय आज़माएं।


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

एक साधारण लिफो कैशिंग नीति मानते हुए, यह कोड:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

पहले a और b को राम में लोड किया जाएगा और फिर रैम में पूरी तरह से काम किया जाएगा। जब दूसरा पाश शुरू होता है, तो c और d डिस्क से डिस्क में लोड हो जाते हैं और संचालित होते हैं।

दूसरा पाश

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

लूप के आस-पास हर दो में दो सरणी और पेज को पेज दोहराएगा । यह स्पष्ट रूप से बहुत धीमा होगा।

आप शायद अपने परीक्षणों में डिस्क कैशिंग नहीं देख रहे हैं लेकिन आप शायद कैशिंग के किसी अन्य रूप के साइड इफेक्ट्स देख रहे हैं।

ऐसा लगता है कि यहां थोड़ा भ्रम / गलतफहमी हो रही है, इसलिए मैं एक उदाहरण का उपयोग करके थोड़ा विस्तार करने की कोशिश करूंगा।

कहें n = 2 और हम बाइट्स के साथ काम कर रहे हैं। मेरे परिदृश्य में हमारे पास केवल 4 बाइट रैम हैं और हमारी बाकी की स्मृति काफी धीमी है (100 गुना अधिक पहुंच कहें)।

अगर बाइट कैश में नहीं है , तो एक काफी गूंगा कैशिंग नीति मान लीजिए , इसे वहां रखें और निम्न बाइट भी प्राप्त करें, जबकि हम इसमें हैं, आपको इस तरह का परिदृश्य मिलेगा:

  • साथ में

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • कैश a[0] और a[1] फिर b[0] और b[1] और कैश में a[0] = a[0] + b[0] करें - अब कैश में चार बाइट हैं, a[0], a[1] और b[0], b[1] । लागत = 100 + 100।

  • कैश में a[1] = a[1] + b[1] करें। लागत = 1 + 1।
  • c और d लिए दोहराएं।
  • कुल लागत = (100 + 100 + 1 + 1) * 2 = 404

  • साथ में

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • कैश a[0] और a[1] फिर b[0] और b[1] और कैश में a[0] = a[0] + b[0] करें - अब कैश में चार बाइट हैं, a[0], a[1] और b[0], b[1] । लागत = 100 + 100।

  • कैश और कैश c[0] और c[1] से d[0] और d[1] और एक c[0] = c[0] + d[0] कैश में। लागत = 100 + 100।
  • मुझे संदेह है कि आप देखना शुरू कर रहे हैं कि मैं कहां जा रहा हूं।
  • कुल लागत = (100 + 100 + 100 + 100) * 2 = 800

यह एक क्लासिक कैश थ्रैश परिदृश्य है।


शाखा-पूर्वानुमान लाभ!

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

if (expression)
{
    // Run 1
} else {
    // Run 2
}

जब भी कोई if-else\ switchकथन होता है, तो यह निर्धारित करने के लिए अभिव्यक्ति का मूल्यांकन किया जाना चाहिए कि कौन सा ब्लॉक निष्पादित किया जाना चाहिए। कंपाइलर द्वारा उत्पन्न असेंबली कोड में, सशर्त branch निर्देश डाले जाते हैं।

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

ऐसा कहा जा रहा है कि संकलक वास्तव में मूल्यांकन किए जाने से पहले परिणाम की भविष्यवाणी करने की कोशिश करता है। यह ifब्लॉक से निर्देश लाएगा , और अगर अभिव्यक्ति सच साबित हो जाती है, तो अद्भुत! हमने इसका मूल्यांकन करने के लिए समय निकाला और कोड में प्रगति की; यदि नहीं तो हम गलत कोड चला रहे हैं, पाइपलाइन फ्लश हो गई है, और सही ब्लॉक चलाया गया है।

दृश्य:

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

जबकि पाइपलाइनों को फ्लश करना बहुत तेज़ है, आजकल इस जुआ को लेना इसके लायक है। सॉर्ट किए गए डेटा या डेटा जो धीरे-धीरे बदलते हैं, की भविष्यवाणी करना तेजी से परिवर्तन की भविष्यवाणी करने से हमेशा आसान और बेहतर होता है।

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------




c++ c performance compiler-optimization vectorization