इस मामले में लूप विखंडन क्यों समझ में आता है?

Question

विखंडन के बिना कोड इस तरह दिखता है:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[hash(keys[i])] 
    } 
    return ret; 
} 

विखंडन के साथ

:

int check(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[hash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 

नोट्स:

• टोंटी map[hash(keys[i])] जो बेतरतीब ढंग से स्मृति में पहुंचता है।

• सामान्यतः, if(tmp[i]) res[ret++] = i; होगा यदि मैं ret += tmp[i] का उपयोग कर रहा हूं।

• map[..] विखंडन संस्करण आम तौर पर काफी तेज है और मैं क्यों की व्याख्या करने के कोशिश कर रहा हूँ हमेशा 0 या 1

है। मेरा सबसे अच्छा अनुमान यह है कि ret += map[..] अभी भी कुछ निर्भरता पेश करता है और जो सट्टा निष्पादन को रोकता है।

मैं सुनना चाहूंगा कि किसी के पास बेहतर स्पष्टीकरण है या नहीं।

Answer 1

मेरे परीक्षणों से, मुझे फ़्यूज्ड और स्प्लिट लूप के बीच लगभग 2x गति अंतर मिलता है। यह गति अंतर बहुत संगत है इससे कोई फर्क नहीं पड़ता कि मैं लूप को कैसे बदलता हूं।

:

Fused: 1.096258 seconds 
Split: 0.562272 seconds 

---

हालांकि मैं 100% यकीन है कि, मुझे लगता है कि यह है नहीं कर रहा हूँ दो चीजें का एक संयोजन की वजह से (नीचे करने के लिए पूर्ण परीक्षण कोड के लिए देखें।)

1. map[gethash(keys[i])] से कैश की वजह से memory disambigutation के लिए लोड-स्टोर बफर की संतृप्ति।
2. फ़्यूज्ड लूप संस्करण में एक अतिरिक्त निर्भरता।

यह स्पष्ट है कि map[gethash(keys[i])] परिणामस्वरूप लगभग हर बार कैश मिस जाएगा। वास्तव में, यह संभवतः पूरे लोड-स्टोर बफर को संतृप्त करने के लिए पर्याप्त है।

अब देखते हुए निर्भरता को देखें।

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

ret चर पते के संकल्प दुकान res[ret] = i; के लिए आवश्यक है: मुद्दा ret चर रहा है।

• फ़्यूज्ड लूप में, ret एक निश्चित कैश मिस से आ रहा है।
• विभाजन लूप में, rettmp[i] आ रहा है - जो बहुत तेज़ है।

जुड़े हुए लूप मामले की पता संकल्प में इस देरी की संभावना map[gethash(keys[i])] के साथ लोड दुकान बफर को अवरुद्ध करने के लिए स्टोर करने के लिए res[ret] = i कारण बनता है।

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

---

मान लीजिए:

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[i] = i; // Change "res" to "i" 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 

यह पता संकल्प निर्भरता टूट जाएगा।

^{(ध्यान दें कि इसे अब और एक ही नहीं है, लेकिन यह सिर्फ प्रदर्शन अंतर प्रदर्शित करने के लिए है।)}

तो हम इसी तरह समय मिलता है:

Fused: 0.487477 seconds 
Split: 0.574585 seconds 

---

यहाँ पूरा परीक्षण है कोड:

#define SIZE 67108864 

unsigned gethash(int key){ 
    return key & (SIZE - 1); 
} 

int check_fused(int * res, char * map, int n, int * keys){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += map[gethash(keys[i])]; 
    } 
    return ret; 
} 
int check_split(int * res, char * map, int n, int * keys, int *tmp){ 
    int ret = 0; 
    for(int i = 0; i < n; ++i){ 
     tmp[i] = map[gethash(keys[i])]; 
    } 
    for(int i = 0; i < n; ++i){ 
     res[ret] = i; 
     ret += tmp[i]; 
    } 
    return ret; 
} 


int main() 
{ 
    char *map = (char*)calloc(SIZE,sizeof(char)); 
    int *keys = (int*)calloc(SIZE,sizeof(int)); 
    int *res = (int*)calloc(SIZE,sizeof(int)); 
    int *tmp = (int*)calloc(SIZE,sizeof(int)); 
    if (map == NULL || keys == NULL || res == NULL || tmp == NULL){ 
     printf("Memory allocation failed.\n"); 
     system("pause"); 
     return 1; 
    } 

    // Generate Random Data 
    for (int i = 0; i < SIZE; i++){ 
     keys[i] = (rand() & 0xff) | ((rand() & 0xff) << 16); 
    } 

    printf("Start...\n"); 

    double start = omp_get_wtime(); 
    int ret; 

    ret = check_fused(res,map,SIZE,keys); 
// ret = check_split(res,map,SIZE,keys,tmp); 

    double end = omp_get_wtime(); 

    printf("ret = %d",ret); 
    printf("\n\nseconds = %f\n",end - start); 

    system("pause"); 
} 

Answer 2

मुझे नहीं लगता कि यह सरणी अनुक्रमण है, लेकिन hash() फ़ंक्शन को कॉल करें जो पाइपलाइन स्टॉल का कारण बन सकता है और इष्टतम निर्देश रीडरिंग को रोक सकता है।