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



3 Answers

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

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

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

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

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

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

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

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

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

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

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

प्रस्ताव

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

Question

मान लीजिए कि 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।

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

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




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

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




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

मुझे नहीं पता कि खराब बेंचमार्क कोड दोष देना है या क्या, लेकिन निम्नलिखित विधियों का उपयोग करके मेरी मशीन पर दो विधियां एक दूसरे के 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 सेकंड में लगभग समान है।




Related