通过一个程序说明cache命中率对内存访问速度的影响

liangbch

我们知道，现代的CPU包含cache部件，cache亦称高速缓冲，其中存储了CPU最近访问过的或者将要访问的数据。和通常的RAM相比，cache也是一种存储器，其特点存储速度非常快，但同样容量的cache比同样的RAM成本高了很多，因此不能做的太大。
  
  cache亦采用多级存储结构，通常的CPU有8-64K的一级cache,256K-12M的2级cache，有的CPU还有3级cache.许多现代的CPU的2级cache与CPU同频，因此速度非常快。
  
  按照intel的说法，在通常情况下，对RAM的访问实际上近似等同于对cache的访问，因为在90%以上的情况下，RAM中的数据已经被缓冲到cache. 因为程序对RAM的访问具有局部性，也就是说，下次访问的数据的地址和这次访问的数据的地址相邻，所有当访问d[ i ]时，CPU的后台"程序"自动把和d[ i ]相邻的数据载入cache. 下次访问d[ i+1 ]时，可直接从cache中读写数据. 只用当访问的数据不在cache中，CPU才直接从RAM读取数据，由于RAM的很高的延时，故直接从RAM中读写数据比从cache中读写数据要慢得多。


  显然，对数据的顺序访问具有极高的cache命中率，因此对数据的顺序访问的性能几乎可达到内存带宽这个上限。内存带宽指内存和cache间批量数据传递的速率,注意内存带宽和内存延时无必然的联系，因为通常情况下，CPU在后台做内存和cache间数据交换，所有内存的高延时被隐藏了。
  
  反之，对数据的随机访问则使得cache命中率大大降低，一旦cache未命中，CPU不得不与内存之间交换数据，此时，内存的高延时就成为瓶颈。

  楼下的代码分别测试 对1M*4,4M*4,16M*4,64M*4的内存块进行顺序读取和随机读取所耗费的时间。其速度比如下(测试机的L2 cache is 6M)

块大小  速度比
4M      3.0
16M     7.1
64M     11.2
256M    12.5

liangbch

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. #include <memory.h>
   
5. 
   
6. #include "currTime.h"
   
7. 
   
8. typedef unsigned long DWORD;
   
9. 
   
10. 
    
11. void initAccessTable(int accessTab[], int len, int isRand )
    
12. {
    
13.         int i,idx;
    
14. 
    
15.         if (isRand==0)  //sequential access
    
16.         {
    
17.                 for (i=0;i<len;i++)
    
18.                 {
    
19.                         accessTab[i]=i;
    
20.                 }
    
21.         }
    
22.         else
    
23.         {
    
24.                 char *tmpBuff=(char *)malloc(len);
    
25.                 memset(tmpBuff,0,len);
    
26. 
    
27.                 for (i=0;i<len;)
    
28.                 {
    
29.                         idx= ((rand() << 15)+ rand()) % len;
    
30.                         if ( tmpBuff[idx]==0)
    
31.                         {
    
32.                                 accessTab[i++]=idx;
    
33.                                 tmpBuff[idx]=1;
    
34.                         }
    
35.                 }
    
36.                 free(tmpBuff);
    
37.         }
    
38. }
    
39. 
    
40. int sum(DWORD pBuff[], int accessTab[], int len)
    
41. {
    
42.         DWORD s=0;
    
43.         int i,idx;
    
44.         for (i=0;i<len;i++)
    
45.         {
    
46.                 idx=accessTab[i];
    
47.                 s += pBuff[idx];
    
48.         }
    
49.         return s;
    
50. }
    
51. 
    
52. //mode=0, sequential access
    
53. //mode=1, random access
    
54. void test_access_RAM(int blk_len, int mode)
    
55. {
    
56.         DWORD *pBuff=malloc(sizeof(DWORD)*blk_len);
    
57.         int *accessTab=malloc(sizeof(int)*blk_len);
    
58.         DWORD i,s;
    
59.         double t;
    
60.        
    
61.         for (i=0;i<blk_len;i++)
    
62.         {
    
63.                 pBuff[i]=rand() & 15;
    
64.         }
    
65.        
    
66.         initAccessTable(accessTab, blk_len, mode);
    
67.        
    
68.         t=currTime();
    
69.         s=sum(pBuff,accessTab,blk_len);
    
70.         t=currTime()-t;
    
71. 
    
72.         printf("s=%d\n",s);
    
73.         if ( mode ==0)
    
74.                 printf("sequential access %d number, it take %.6f ms\n",blk_len,t*1000 );
    
75.         else
    
76.                 printf("random access %d number, it take %.6f ms\n",blk_len,t*1000 );
    
77. 
    
78.         free(pBuff);
    
79.         free(accessTab);
    
80. 
    
81. }
    
82. 
    
83. void test()
    
84. {
    
85.         int blk_len;
    
86.         int i,loop;
    
87.        
    
88.         loop=3;
    
89.         blk_len=1024*1024;
    
90.        
    
91.         for (i=0;i<loop;i++)
    
92.         {        test_access_RAM(blk_len,0); }
    
93.        
    
94.         for (i=0;i<loop;i++)
    
95.         {        test_access_RAM(blk_len,1); }
    
96.        
    
97.         //----------------------------
    
98.         blk_len=4*1024*1024;
    
99.         for (i=0;i<loop;i++)
    
100.         {        test_access_RAM(blk_len,0); }
     
101.        
     
102.         for (i=0;i<loop;i++)
     
103.         {        test_access_RAM(blk_len,1); }
     
104.        
     
105.         //----------------------------
     
106.         blk_len=16*1024*1024;
     
107.         for (i=0;i<loop;i++)
     
108.         {        test_access_RAM(blk_len,0); }
     
109.        
     
110.         for (i=0;i<loop;i++)
     
111.         {        test_access_RAM(blk_len,1); }
     
112.        
     
113.         //----------------------------
     
114.         blk_len=64*1024*1024;
     
115.         for (i=0;i<loop;i++)
     
116.         {        test_access_RAM(blk_len,0); }
     
117.        
     
118.         for (i=0;i<loop;i++)
     
119.         {        test_access_RAM(blk_len,1); }
     
120. }
     
121. 
     
122. int main(int argc, char* argv[])
     
123. {
     
124.         test();
     
125.         return 0;
     
126. }
     

复制代码

kenmark

的确，random access 现在已经不能简单认为是O(1)了，但是细化的研究还是比较欠缺，做cache的还是做编译器的比较多，系统里面大家对cache的认识都比较简化。

最近在思索如果提供给programmer在cache-aware 的programming model，但又不至于增加复杂度