cache对程序运行效率的影响？

wayne

假设有这样的代码：

1. const int N=512*1024*1024;
   
2. int *arr=new int[N];
   
3. for (int i = 0; i < N; i += K) arr[i] *= 3;

复制代码

针对不同的K(1<K<1024)，该程序会有对应的一个运行时间，这个时间曲线大致是什么样子呢？

我打算写个程序核实一下。

假如不让你写程序，你能给出该曲线的形状吗？

wayne

顶起来。
贴出此题的目的只是 期待老大们的回复，然后我能从中学到更多外延的东西

liangbch

这个例子不具代表性。K越大，循环次数越少。耗时越短。另外，数组的siz越小，速度越快，因为如果数组的siz小于cache的size,用不了多久，数组的所有元素都被加载到cache中去了，从这往后，所有的内存的访问仅在cache中进行，cache的命中率接近100%。

wayne

栈的最大值OS是咋限制的，最大可以是多少？

mathe

使用malloc应该可以分配大一点的空间，如果在Windows下使用virtualAlloc等命令应该可以分配更加大的内存（还会使用虚拟存储）。
当K不是很大时,CPU会对内存访问顺序访问进行预测，提前转载数据到缓存，所以速度会很快，但是大到一定程度估计预测就失去作用了。于是那时，花费的时间就在访问内存上了

wayne

mathe 发表于 2013-8-8 17:20
使用malloc应该可以分配大一点的空间，如果在Windows下使用virtualAlloc等命令应该可以分配更加大的内存（ ...

恩，我把原题又改了。通过尝试发现，貌似堆上面分配的默认最大值(512*1024*1024*8B =4GB)  不能超过机器的实际内存 (4GB, X86_64)，
不然会提示

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

这是我的测试代码以及机器配置，能编译通过：

1. /**
   
2. \$ uname -a:
   
3. Linux wayArch 3.10.5-1-ARCH #1 SMP PREEMPT Mon Aug 5 08:04:22 CEST 2013 x86_64 GNU/Linux
   
4. 
   
5. \$ cat /proc/meminfo | grep -e Commit -e Mem
   
6. MemTotal: &#160; &#160; &#160; &#160;3805168 kB
   
7. MemFree: &#160; &#160; &#160; &#160; 2133448 kB
   
8. CommitLimit: &#160; &#160; 1902584 kB
   
9. Committed_AS: &#160; &#160;2301428 kB
   
10. */
    
11. 
    
12. #include<iostream>
    
13. using namespace std;
    
14. int main()
    
15. {
    
16.         const int N=512*1024*1024;
    
17.         int *arr=new int[N];
    
18.         cout<<sizeof(arr)<<endl;
    
19.         for(int i=0;i<N;++i){
    
20.                 arr[i]=i;       
    
21.         }
    
22. 
    
23.         /*
    
24.         for(int i=0;i<N;++i){
    
25.                 cout<<arr[i]<<'\t';
    
26.                 if(i%10==9) cout<<endl;
    
27.         }
    
28.         */
    
29.         delete[] arr;
    
30. 
    
31. }
    

复制代码

无心人

cache填充是以某个字节倍数为单位连续读取的

所以，一旦你步长超过这个倍数，将会严重受制于cache大小
应该是写会延迟

我手里有本intel的指令优化手册谈到了一个筛法求素数的例子
就是当筛子的步长很大时候，直接写，会遇到写延迟
判定一下反倒速度很快