एक सरल सी प्रोग्राम के भ्रमित कैशिंग व्यवहार

Question

मैं यह देखने के लिए एक प्रोग्राम के साथ प्रयोग कर रहा हूं कि इसका कैशिंग व्यवहार मेरी वैचारिक समझ के अनुरूप है या नहीं।

ऐसा करने के लिए मैं Perf आदेश का उपयोग कर रहा हूँ:

int main() { 
    int N = 10000; 
    double *arr = malloc(sizeof(double) * N * N); 

    for(int i = 0; i < N; i++) { 
     for(int j = 0; j < N; j++){ 
      arr[i * N + j] = 10.0; 
     } 
    } 
    return 0; 
} 

मैं एक कैश मिल: निम्नलिखित सरल सी कार्यक्रम का कैश-मिस अनुपात रिकॉर्ड करने के लिए

perf stat -e cache-misses ./a.out 

-मिशन अनुपात 50.212%। यदि मैं सरणी एक्सेस पैटर्न को निम्नानुसार बदलता हूं:

arr[j * N + i] 

मुझे लगता है कि कैश-मिस अनुपात 22.206% है।

ये परिणाम मुझे आश्चर्यचकित कर रहे हैं।

1. 50.212% का कैश-मिस अनुपात बहुत ही सरल स्मृति पहुंच पैटर्न के साथ इस तरह के एक सरल कार्यक्रम के लिए बहुत अधिक लगता है। मैं उम्मीद करता हूं कि यह 1/(num-words-per-cache-line) के करीब होगा जो निश्चित रूप से 1/2 से बड़ा है। कैश-मिस अनुपात इतना ऊंचा क्यों है?
2. स्मृति की मेरी (सीमित) समझ से पता चलता है कि कॉलम-प्रमुख क्रम में सरणी पर पुनरावृत्ति करने से परिणामस्वरूप बहुत खराब कैशिंग व्यवहार हो सकता है लेकिन परिणाम जो मुझे मिल रहा है, विपरीत है। क्या चल रहा है?

Answer 1

उत्तर बहुत आसान है: कंपाइलर आपके असाइनमेंट को अनुकूलित करता है। यहाँ कैसे disassembly के अपने कोड के लिए की तरह लग रहा है:

10 int main() { 
    0x00000000004004d6 <+0>: mov $0x2710,%edx 
    0x00000000004004db <+5>: jmp 0x4004e7 <main+17> 

15   for(int j = 0; j < N; j++){ 
    0x00000000004004dd <+7>: sub $0x1,%eax 
    0x00000000004004e0 <+10>: jne 0x4004dd <main+7> 

14  for(int i = 0; i < N; i++) { 
    0x00000000004004e2 <+12>: sub $0x1,%edx 
    0x00000000004004e5 <+15>: je  0x4004ee <main+24> 

10 int main() { 
    0x00000000004004e7 <+17>: mov $0x2710,%eax 
    0x00000000004004ec <+22>: jmp 0x4004dd <main+7> 

16    arr[i * N + j] = 10.0; 
17   } 
18  } 
19  return 0; 
20 } 
    0x00000000004004ee <+24>: mov $0x0,%eax 
    0x00000000004004f3 <+29>: retq 

आप कोई कोडांतरक लाइन arr[i * N + j] = 10.0; के लिए उत्पन्न निर्देश देखते हैं देख सकते हैं, इसलिए उन कैश आप का पालन पर्फ़ साथ कोई संबंध नहीं हैं याद करते हैं।

फिक्स काफी आसान है। सीधे शब्दों में सूचक घोषणा करने के लिए volatile जोड़ने के लिए, अब कार्य उत्पन्न करने के लिए मजबूर कर रहा संकलक, यानी .:

volatile double *arr = malloc(sizeof(double) * N * N); 

disassembly:

10 int main() { 
    0x0000000000400526 <+0>: sub $0x8,%rsp 

11  int N = 10000; 
12  volatile double *arr = malloc(sizeof(double) * N * N); 
    0x000000000040052a <+4>: mov $0x2faf0800,%edi 
    0x000000000040052f <+9>: callq 0x400410 <malloc@plt> 
    0x0000000000400534 <+14>: mov $0x0,%edx 

16    arr[i * N + j] = 10.0; 
    0x0000000000400539 <+19>: movsd 0xc7(%rip),%xmm0  # 0x400608 
    0x0000000000400541 <+27>: jmp 0x40055f <main+57> 
    0x0000000000400543 <+29>: movslq %edx,%rcx 
    0x0000000000400546 <+32>: lea (%rax,%rcx,8),%rcx 
    0x000000000040054a <+36>: movsd %xmm0,(%rcx) 
    0x000000000040054e <+40>: add $0x1,%edx 

15   for(int j = 0; j < N; j++){ 
    0x0000000000400551 <+43>: cmp %esi,%edx 
    0x0000000000400553 <+45>: jne 0x400543 <main+29> 
    0x0000000000400555 <+47>: mov %esi,%edx 

14  for(int i = 0; i < N; i++) { 
    0x0000000000400557 <+49>: cmp $0x5f5e100,%esi 
    0x000000000040055d <+55>: je  0x400567 <main+65> 
    0x000000000040055f <+57>: lea 0x2710(%rdx),%esi 
    0x0000000000400565 <+63>: jmp 0x400543 <main+29> 

17   } 
18  } 
19  return 0; 
20 } 
    0x0000000000400567 <+65>: mov $0x0,%eax 
    0x000000000040056c <+70>: add $0x8,%rsp 
    0x0000000000400570 <+74>: retq 

और भी बहुत कुछ कैश के रूप में अच्छी तरह से याद करते हैं देखते हैं।

आपके परीक्षण को चलाने से आपको बहुत शोर परिणाम मिल सकते हैं। आपको अपना माप कुछ बार चलाना चाहिए और एक औसत लेना चाहिए। Google बेंचमार्क जैसे बेंचमार्क फ्रेमवर्क हैं, इसलिए कृपया एक नज़र डालें।

और अंतिम वाला। i * N + j और j * N + i जैसे आपके दोनों पैटर्न, सीपीयू प्रीफेचर द्वारा आसानी से पहचानने योग्य हैं, इसलिए दोनों मामलों में कैश मिस अनुपात काफी समान होना चाहिए ...