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




performance compiler-optimization (8)

मान लीजिए कि 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 विभिन्न मूल्यों के लिए एफएलओपी / एस दिखाता है।)


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


कल्पना कीजिए कि आप एक मशीन पर काम कर रहे हैं जहां 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

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


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

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


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


मूल प्रश्न

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

निष्कर्ष:

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


इसके आगे विश्लेषण पर, मेरा मानना ​​है कि यह चार पॉइंटर्स के डेटा संरेखण के कारण (कम से कम आंशिक रूप से) है। यह कैश बैंक / रास्ते के संघर्ष के कुछ स्तर का कारण बन जाएगा।

यदि मैंने सही तरीके से अनुमान लगाया है कि आप अपने सरणी आवंटित कर रहे हैं, तो उन्हें पृष्ठ पंक्ति में गठबंधन होने की संभावना है

इसका मतलब यह है कि प्रत्येक पाश में आपकी सभी पहुंच एक ही कैश तरीके से गिर जाएगी। हालांकि, इंटेल प्रोसेसर के पास थोड़ी देर के लिए 8-तरफा एल 1 कैश एसोसिएटिविटी है। लेकिन हकीकत में, प्रदर्शन पूरी तरह से वर्दी नहीं है। 4-तरीकों तक पहुंचना अभी भी 2-तरीकों से धीमा है।

संपादित करें: वास्तव में ऐसा लगता है कि आप सभी सरणी अलग से आवंटित कर रहे हैं। आम तौर पर जब ऐसे बड़े आवंटन का अनुरोध किया जाता है, तो आवंटक ओएस से ताजा पृष्ठों का अनुरोध करेगा। इसलिए, एक उच्च संभावना है कि पृष्ठ आवंटन से एक ही ऑफसेट पर बड़े आवंटन दिखाई देंगे।

टेस्ट कोड यहां दिया गया है:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

बेंचमार्क परिणाम:

संपादित करें: वास्तविक कोर 2 आर्किटेक्चर मशीन पर परिणाम:

2 एक्स इंटेल ज़ीऑन एक्स 5482 हार्परटाउन @ 3.2 गीगाहर्ट्ज:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

टिप्पणियों:

  • एक लूप के साथ 6.206 सेकेंड और दो लूप के साथ 2.116 सेकेंड । यह ओपी के परिणामों को बिल्कुल पुन: उत्पन्न करता है।

  • पहले दो परीक्षणों में, सरणी अलग से आवंटित की जाती हैं। आप देखेंगे कि उनके पास पृष्ठ के सापेक्ष समान संरेखण है।

  • दूसरे दो परीक्षणों में, उस संरेखण को तोड़ने के लिए सरणी एक साथ पैक की जाती हैं। यहां आप देखेंगे कि दोनों लूप तेज हैं। इसके अलावा, दूसरा (डबल) लूप अब धीमा है जैसा कि आप आमतौर पर अपेक्षा करते हैं।

जैसा कि @ स्टीफन कैनन टिप्पणियों में बताते हैं, वहां संभावना है कि यह संरेखण लोड / स्टोर इकाइयों या कैश में झूठी अलियासिंग का कारण बनता है। मैंने इसके लिए चारों ओर गुगल किया और पाया कि इंटेल वास्तव में आंशिक पता एलियासिंग स्टालों के लिए हार्डवेयर काउंटर है:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html

5 क्षेत्र - स्पष्टीकरण

क्षेत्र 1:

यह एक आसान है। डेटासेट इतना छोटा है कि प्रदर्शन लूपिंग और ब्रांचिंग जैसे ओवरहेड पर हावी है।

क्षेत्र 2:

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

मुझे यकीन नहीं है कि वास्तव में क्या हो रहा है ... संरेखण अभी भी प्रभाव डाल सकता है क्योंकि एग्नेर फॉग कैश बैंक संघर्ष का उल्लेख करता है । (वह लिंक सैंडी ब्रिज के बारे में है, लेकिन विचार अभी भी कोर 2 पर लागू होना चाहिए।)

क्षेत्र 3:

इस बिंदु पर, डेटा अब L1 कैश में फिट नहीं है। तो प्रदर्शन एल 1 <-> एल 2 कैश बैंडविड्थ द्वारा कैप्ड किया गया है।

क्षेत्र 4:

सिंगल-लूप में प्रदर्शन ड्रॉप वह है जिसे हम देख रहे हैं। और जैसा कि बताया गया है, यह संरेखण के कारण है (सबसे अधिक संभावना) प्रोसेसर लोड / स्टोर इकाइयों में झूठे एलियासिंग स्टालों का कारण बनता है।

हालांकि, झूठे एलियासिंग होने के लिए, डेटासेट के बीच काफी बड़ा कदम होना चाहिए। यही कारण है कि आप इसे क्षेत्र 3 में नहीं देखते हैं।

क्षेत्र 5:

इस बिंदु पर, कैश में कुछ भी फिट बैठता है। तो आप मेमोरी बैंडविड्थ से बंधे हैं।


ठीक है, सही जवाब निश्चित रूप से सीपीयू कैश के साथ कुछ करना है। लेकिन कैश तर्क का उपयोग करना काफी मुश्किल हो सकता है, खासकर डेटा के बिना।

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

@ मिस्टिकियल के जवाब ने बहुत से लोगों (मुझे समेत) को आश्वस्त किया, शायद इसलिए कि यह केवल एकमात्र ऐसा था जो तथ्यों पर भरोसा करता था, लेकिन यह सच का केवल एक "डेटा पॉइंट" था।

यही कारण है कि मैंने अपना परीक्षण (निरंतर बनाम अलग आवंटन का उपयोग करके) और @ जेम्स 'उत्तर की सलाह का उपयोग किया।

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

ध्यान दें कि मेरा प्रारंभिक प्रश्न एन = 100.000 पर था। यह बिंदु (दुर्घटना से) विशेष व्यवहार प्रदर्शित करता है:

  1. इसमें एक और दो लूप संस्करण (लगभग तीन का कारक) के बीच सबसे बड़ी विसंगति है।

  2. यह एकमात्र बिंदु है, जहां एक-लूप (अर्थात् निरंतर आवंटन के साथ) दो-लूप संस्करण को धड़कता है। (यह रहस्यवादी का जवाब संभव है, बिल्कुल।)

प्रारंभिक डेटा का उपयोग कर परिणाम:

नतीजे डेटा का उपयोग करके परिणाम (यह रहस्यवादी परीक्षण है):

और यह एक कठिन व्याख्या है: प्रारंभिक डेटा, जिसे एक बार आवंटित किया जाता है और विभिन्न वेक्टर आकार के प्रत्येक निम्न परीक्षण मामले के लिए पुन: उपयोग किया जाता है:

प्रस्ताव

स्टैक ओवरफ़्लो पर प्रत्येक निम्न-स्तरीय प्रदर्शन से संबंधित प्रश्न कैश की विस्तृत श्रृंखला के लिए MFLOPS जानकारी प्रदान करने के लिए आवश्यक डेटा आकारों की आवश्यकता होनी चाहिए! यह जवाबों के बारे में सोचने के लिए हर किसी के समय बर्बाद है और विशेष रूप से इस जानकारी के बिना दूसरों के साथ चर्चा करता है।


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

एक पाश: 1.577 एमएस

दो लूप: 1.507 एमएस

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





vectorization