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

油条大哥大

假设有这样的代码：

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

复制代码

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

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

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

Lpasarbola

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

isotaztiqotew

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

AbertVab

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

dingji

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

ouukucakac

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

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

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

1. /** \$ uname -a:Linux wayArch 3.10.5-1-ARCH #1 SMP PREEMPT Mon Aug 5 08:04:22 CEST 2013 x86_64 GNU/Linux\$ cat /proc/meminfo | grep -e Commit -e MemMemTotal:        3805168 kBMemFree:         2133448 kBCommitLimit:     1902584 kBCommitted_AS:    2301428 kB*/#include<iostream>using namespace std;int main(){        const int N=512*1024*1024;        int *arr=new int[N];        cout<<sizeof(arr)<<endl;        for(int i=0;i<N;++i){                arr[i]=i;                }        /*        for(int i=0;i<N;++i){                cout<<arr[i]<<'\t';                if(i%10==9) cout<<endl;        }        */        delete[] arr;}

复制代码

oabipalehov

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

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

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