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


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

const int n = 100000;

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

यह पाश एक और बाहरी के माध्यम से 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];
}

एमएस पर संकलित दृश्य सी ++ 10.0 पूर्ण अनुकूलन के साथ और SSE2 ए पर 32-बिट के लिए सक्षम इंटेल कोर 2 डुओ (x64), पहला उदाहरण 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।)

enter image description here


1996
2017-12-17 20:40


मूल


ऑपरेटिंग सिस्टम हो सकता है जो प्रत्येक बार जब आप इसे एक्सेस करते हैं तो भौतिक मेमोरी की खोज करते समय धीमा हो जाता है और उसी memblock पर द्वितीयक पहुंच के मामले में कैश की तरह कुछ होता है। - AlexTheo
क्या आप अनुकूलन के साथ संकलित कर रहे हैं? यह ओ 2 के लिए बहुत सारे कोड की तरह दिखता है ... - Luchian Grigore
बस picky होने के लिए, इन दो कोड स्निपेट संभावित ओवरलैपिंग पॉइंटर्स के बराबर नहीं हैं। सी 99 में है restrictऐसी स्थितियों के लिए कीवर्ड। मुझे नहीं पता कि एमएसवीसी के पास कुछ समान है या नहीं। बेशक, अगर यह मुद्दा था तो एसएसई कोड सही नहीं होगा। - user510306
यह स्मृति एलियासिंग के साथ कुछ करने के लिए हो सकता है। एक पाश के साथ, d1[j] साथ aliase हो सकता है a1[j], इसलिए संकलक कुछ स्मृति अनुकूलन करने से वापस ले सकता है। हालांकि ऐसा नहीं होता है यदि आप लेखन को दो लूप में स्मृति में अलग करते हैं। - rturrado
@RocketRoy इससे पहले कि आप सामान बनाने के आरोप लगाते हैं, आप वास्तव में कुछ विवरणों पर ध्यान देने का प्रयास क्यों नहीं करते? आप अपने जवाब में कहते हैं कि आप इसे पुन: पेश नहीं कर सकते हैं। यह सवाल 5 साल का है। क्या आपने संभावना है कि तब से प्रोसेसर में सुधार हुआ है? मेरे जवाब को देखो, यह दिखाता है कि यह कोर 2 पर बड़ा समय पुन: उत्पन्न करता है, लेकिन नेहलेम और बाद में कम है। - Mysticial


जवाब:


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

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

इसका मतलब यह है कि प्रत्येक पाश में आपकी सभी पहुंच एक ही कैश तरीके से गिर जाएगी। हालांकि, इंटेल प्रोसेसर के पास थोड़ी देर के लिए 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 सेकेंड दो loops के साथ। यह ओपी के परिणामों को बिल्कुल पुन: उत्पन्न करता है।

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

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

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

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:

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


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1546
2017-12-17 21:17



+1: मुझे लगता है कि यह जवाब है। अन्य सभी उत्तरों के मुताबिक, यह एक और लूप संस्करण के बारे में नहीं है जो स्वाभाविक रूप से अधिक कैश याद करता है, यह कैश के कारण होने वाले सरणी के विशेष संरेखण के बारे में है। - Oliver Charlesworth
इस; ए झूठी अलियासिंग स्टाल सबसे संभावित स्पष्टीकरण है। - Stephen Canon
@VictorT। मैंने ओपी से जुड़े कोड का इस्तेमाल किया। यह एक .css फ़ाइल उत्पन्न करता है जिसे मैं एक्सेल में खोल सकता हूं और इससे ग्राफ बना सकता हूं। - Mysticial
@ नवाज एक पृष्ठ आमतौर पर 4 केबी है। यदि आप हेक्साडेसिमल पते को देखते हैं जिन्हें मैं प्रिंट करता हूं, अलग-अलग आवंटित परीक्षणों में सभी समान मॉड्यूल 4096 होते हैं। (यह 4 केबी सीमा की शुरुआत से 32-बाइट्स है) शायद जीसीसी में यह व्यवहार नहीं है। यह समझा सकता है कि आप मतभेद क्यों नहीं देख रहे हैं। - Mysticial
रुचि रखने वाले किसी के लिए, मेमोरी संरेखण पर अच्छा पठन है तथा यहां कई हैं  रास्ते पर लिंक  डेटा स्मृति में कैश किया गया है - New Alexandria


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

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

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

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

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

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

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

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

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

Enter image description here

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

Enter image description here

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

Enter image description here

प्रस्ताव

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


195
2017-12-18 01:29



+1 अच्छा विश्लेषण। मैं पहले स्थान पर डेटा को अनियंत्रित करने का इरादा नहीं रखता था। यह अभी हुआ कि आवंटक ने उन्हें शून्य किया। तो प्रारंभिक डेटा महत्वपूर्ण है। मैंने अभी जवाब के साथ अपना जवाब संपादित किया है वास्तविक कोर 2 आर्किटेक्चर मशीन और वे जो आप देख रहे हैं उसके बहुत करीब हैं। एक और बात यह है कि मैंने कई आकारों का परीक्षण किया n और यह एक ही प्रदर्शन अंतर दिखाता है n = 80000, n = 100000, n = 200000, आदि... - Mysticial
@ मैस्टिसियल मुझे लगता है कि जब भी संभावित इंटर प्रोसेस जासूसी से बचने के लिए प्रक्रिया में नए पेज दिए जाते हैं तो ओएस पेज शून्यिंग लागू करता है। - v.oddou


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


63
2017-12-17 20:47



आप कह रहे हैं कि दूसरा संस्करण कम कैश की याद आती है? क्यूं कर? - Oliver Charlesworth
@ ओली: पहले संस्करण में, प्रोसेसर को एक समय में चार मेमोरी लाइनों तक पहुंचने की आवश्यकता होती है- a[i], b[i], c[i] तथा d[i] दूसरे संस्करण में, इसे केवल दो की जरूरत है। यह जोड़ने के दौरान उन लाइनों को फिर से भरने के लिए और अधिक व्यवहार्य बनाता है। - Puppy
लेकिन जब तक सरणी कैश में टकरा नहीं जाती है, तब तक प्रत्येक संस्करण को पढ़ने और लिखने के लिए समान स्मृति की आवश्यकता होती है। तो निष्कर्ष (मुझे लगता है) कि ये दो सरणी हर समय टकराने लगते हैं। - Oliver Charlesworth
मैं पालन नहीं करता हूं। प्रति निर्देश (यानी प्रति उदाहरण x += y), दो पढ़े और एक लिख रहे हैं। यह किसी भी संस्करण के लिए सच है। कैश <-> सीपीयू बैंडविड्थ आवश्यकता इसलिए वही है। जब तक कोई संघर्ष नहीं होता है, तब तक कैश <-> रैम बैंडविड्थ आवश्यकता भी वही होती है .. - Oliver Charlesworth
जैसा कि में उल्लेख किया गया है stackoverflow.com/a/1742231/102916, पेंटियम एम के हार्डवेयर प्रीफेच 12 अलग-अलग फॉरवर्ड स्ट्रीम ट्रैक कर सकते हैं (और मैं बाद में हार्डवेयर को कम से कम सक्षम होने की उम्मीद करता हूं)। लूप 2 अभी भी केवल चार धाराओं को पढ़ रहा है, इसलिए उस सीमा के भीतर भी अच्छी तरह से है। - Brooks Moses


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

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


37
2017-12-18 01:36



यह गलत है। किसी सरणी के किसी विशेष तत्व का संदर्भ डिस्क से (या गैर-कैश्ड मेमोरी से) में पूरे सरणी को पेंगने का कारण नहीं बनता है; केवल प्रासंगिक पृष्ठ या कैश लाइन में पेज़ किया गया है। - Brooks Moses
@ ब्रूक मूसा - यदि आप पूरे सरणी से घूमते हैं, जैसा कि यहां हो रहा है, तो यह होगा। - OldCurmudgeon
खैर, हाँ, लेकिन पूरे ऑपरेशन पर यही होता है, न कि लूप के आसपास हर बार क्या होता है। आपने दावा किया कि दूसरा फॉर्म "लूप के चारों ओर हर बार दो एरे और पेज को दो बार पेज करेगा," और यही वह है जिसे मैं ऑब्जेक्ट कर रहा हूं। कुल लूप के आकार के बावजूद, इस लूप के बीच में आपकी रैम चार एरे में से प्रत्येक से एक पेज रखेगी, और लूप के साथ समाप्त होने के बाद तक कुछ भी नहीं पड़ेगा। - Brooks Moses
विशेष मामले में जहां n केवल एक ही समय में स्मृति में आपके दो सरणी को पकड़ना संभव था, इसके लिए सही मूल्य था फिर के सभी तत्वों का उपयोग चार एक लूप में सरणी निश्चित रूप से थ्रैशिंग खत्म होनी चाहिए। - OldCurmudgeon
आप उस लूप 2 पेजों की पूरी तरह से क्यों रह रहे हैं a1 तथा b1 पहले असाइनमेंट के लिए, उनमें से प्रत्येक के पहले पृष्ठ की बजाय? (क्या आप 5-बाइट पेज मान रहे हैं, तो एक पृष्ठ आपकी रैम का आधा हिस्सा है? यह सिर्फ स्केलिंग नहीं है, यह एक वास्तविक प्रोसेसर के विपरीत है।) - Brooks Moses


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

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

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


27
2017-12-17 20:49



यह कैश को निरंतर अवैध क्यों कर देगा? - Oliver Charlesworth
@ ओली चेहरल्सवर्थ: कैश को मेमोरी पतों की एक समान श्रृंखला की हार्ड कॉपी के रूप में सोचें। यदि आप किसी पते का उपयोग न करने का नाटक करते हैं, तो आपको कैश को फिर से लोड करना होगा। और यदि कैश में कुछ संशोधित किया गया था, तो इसे रैम में वापस लिखा जाना चाहिए, या यह खो जाएगा। नमूना कोड में, 100'000 पूर्णांक (400kbytes) के 4 वेक्टर एल 1 कैश (128 या 256 के) की क्षमता से अधिक संभावना है। - Emilio Garavaglia
इस परिदृश्य में कैश के आकार का कोई प्रभाव नहीं पड़ता है। प्रत्येक सरणी तत्व का उपयोग केवल एक बार किया जाता है, और उसके बाद इससे कोई फर्क नहीं पड़ता कि इसे बेदखल कर दिया गया है या नहीं। कैश आकार केवल तभी मायने रखता है जब आपके पास अस्थायी इलाका है (यानी आप भविष्य में उसी तत्व का पुन: उपयोग करने जा रहे हैं)। - Oliver Charlesworth
@ ओली चार्ल्सवर्थ: अगर मुझे कैश में एक नया मान लोड करना है, और इसमें पहले से ही एक मूल्य है जिसे संशोधित किया गया है, तो मुझे इसे लिखना सबसे पहले है, और इससे मुझे लिखने की प्रतीक्षा मिलती है। - Emilio Garavaglia
लेकिन ओपी के कोड के दोनों प्रकारों में, प्रत्येक मान ठीक से एक बार संशोधित हो जाता है। आप प्रत्येक संस्करण में लिखने के लिए समान संख्या में ऐसा करते हैं। - Oliver Charlesworth


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

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

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

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

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

हार्डवेयर है डेल एक्सपीएस 8500 पीढ़ी 3 के साथ कोर i7 @ 3.4 गीगाहर्ट्ज और 8 जीबी मेमोरी। आठ लूप का उपयोग करते हुए 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 सेकंड में लगभग समान है।


16
2017-12-30 01:34



आपके द्वारा यहां उल्लिखित गलत संरेखण दंड तब होता है जब एक व्यक्तिगत लोड / स्टोर जिसे गलत तरीके से गलत किया जाता है (असाइन किए गए एसएसई लोड / स्टोर सहित)। लेकिन यह मामला यहां नहीं है क्योंकि प्रदर्शन विभिन्न सरणी के सापेक्ष संरेखण के प्रति संवेदनशील है। निर्देश स्तर पर कोई misalignments नहीं हैं। प्रत्येक एकल लोड / स्टोर ठीक से गठबंधन किया जाता है। - Mysticial


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


14
2017-12-17 20:52



मुझे विश्वास नहीं है कि कैश आकार और सरणी आकार के बीच कोई बातचीत है। प्रत्येक सरणी तत्व केवल एक बार उपयोग किया जाता है, और फिर सुरक्षित रूप से बेदखल किया जा सकता है। कैश के बीच एक बातचीत हो सकती है लाइन आकार और सरणी आकार, हालांकि, अगर यह चार सरणी संघर्ष करने का कारण बनता है। - Oliver Charlesworth
आप सही हैं, इस प्रभाव को प्रदर्शित करने के लिए यह गलत उदाहरण है - James


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

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


12
2017-08-17 15:23





मूल प्रश्न

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


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

ओपी का कोड:

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


पहुंच

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


परिदृश्य

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