遍历的访问时间经由恒定长度的阵列

Question

我想要测量的高速缓存的速度（I问question有关），所以我写这样的代码：

#include<cstdio> 
#include<ctime> 
#include<windows.h> 
const int mod = 100000007; 
volatile int f[100000007]; 
volatile int *p; 
int main() 
{ 
    FILE *f1; 
    f1=fopen("CacheTest.txt","w"); 
    for(int l=1;l<=100000;) 
    { 
     clock_t st,ed; 
     st=clock(); 
     int now=0; 
     for(int i=0;i<mod;i++) 
     { 
      now+=l;//note:mod is a prime and that will traversal the array 
      if (now>=mod) now-=mod; 
     } 
     ed=clock(); 
     double extime=(double)(ed-st)/CLOCKS_PER_SEC; 
     st=clock(); 
     now=0; 
     for(int i=0;i<mod;i++) 
     { 
      p=&f[now]; 
      *p=1; 
      now+=l; 
      if (now>=mod) now-=mod; 
     } 
     ed=clock(); 
     double cost=(double)(ed-st)/CLOCKS_PER_SEC; 
     fprintf(f1,"length %d costs %f seconds access time:%f\n",l,cost,cost-extime); 
     printf("length %d costs %f seconds access time:%f\n",l,cost,cost-extime); 
     if (l<50) l++; 
     else if (l<100) l+=2; 
     else if (l<1000) l+=20; 
     else if (l<10000) l+=200; 
     else if (l<100000) l+=2000; 
     else l+=20000; 
    } 
} 

结果如下：

length 1 costs 0.994000 seconds access time:0.153000 
length 2 costs 0.651000 seconds access time:-0.048000 
length 3 costs 1.034000 seconds access time:0.414000 
length 4 costs 1.151000 seconds access time:0.018000 
length 5 costs 1.221000 seconds access time:0.086000 
length 6 costs 1.313000 seconds access time:0.179000 
length 7 costs 1.475000 seconds access time:0.442000 
length 8 costs 1.584000 seconds access time:0.437000 
length 9 costs 1.700000 seconds access time:0.567000 
length 10 costs 1.672000 seconds access time:0.665000 
length 11 costs 1.578000 seconds access time:0.573000 
length 12 costs 2.166000 seconds access time:1.280000 
length 13 costs 2.070000 seconds access time:0.988000 
length 14 costs 2.430000 seconds access time:1.402000 
length 15 costs 2.564000 seconds access time:1.428000 
length 16 costs 2.651000 seconds access time:1.519000 
length 17 costs 2.721000 seconds access time:1.654000 
length 18 costs 2.648000 seconds access time:1.518000 
length 19 costs 2.775000 seconds access time:1.638000 
length 20 costs 2.757000 seconds access time:1.636000 
length 21 costs 2.816000 seconds access time:1.684000 
length 22 costs 2.842000 seconds access time:1.706000 
length 23 costs 2.856000 seconds access time:1.751000 
length 24 costs 2.702000 seconds access time:1.568000 
length 25 costs 2.624000 seconds access time:1.618000 
length 26 costs 2.912000 seconds access time:1.777000 
length 27 costs 2.617000 seconds access time:1.468000 
length 28 costs 2.910000 seconds access time:1.778000 
length 29 costs 2.779000 seconds access time:1.649000 
length 30 costs 2.803000 seconds access time:1.727000 
length 31 costs 2.596000 seconds access time:1.465000 
length 32 costs 2.068000 seconds access time:1.188000 
length 33 costs 2.012000 seconds access time:1.294000 
length 34 costs 3.258000 seconds access time:2.381000 
length 35 costs 3.538000 seconds access time:2.406000 
length 36 costs 3.619000 seconds access time:2.556000 
length 37 costs 3.847000 seconds access time:2.717000 
length 38 costs 3.958000 seconds access time:2.827000 
length 39 costs 3.910000 seconds access time:2.841000 
length 40 costs 3.722000 seconds access time:2.592000 
length 41 costs 4.095000 seconds access time:2.960000 
length 42 costs 3.440000 seconds access time:2.420000 
length 43 costs 4.217000 seconds access time:3.085000 
length 44 costs 4.413000 seconds access time:3.457000 
length 45 costs 4.637000 seconds access time:3.507000 
length 46 costs 4.248000 seconds access time:3.115000 
length 47 costs 4.924000 seconds access time:3.856000 
length 48 costs 5.072000 seconds access time:3.942000 
length 49 costs 4.619000 seconds access time:3.615000 
length 50 costs 5.025000 seconds access time:4.136000 
length 52 costs 5.196000 seconds access time:4.059000 
length 54 costs 4.937000 seconds access time:3.806000 
length 56 costs 5.264000 seconds access time:4.132000 
length 58 costs 5.137000 seconds access time:4.004000 
length 60 costs 5.113000 seconds access time:4.107000 
length 62 costs 4.665000 seconds access time:3.537000 
length 64 costs 5.030000 seconds access time:3.900000 
length 66 costs 4.969000 seconds access time:4.016000 
length 68 costs 5.201000 seconds access time:4.096000 
length 70 costs 5.066000 seconds access time:3.931000 
... 
for the length 70~10000 , the access time is around 4s. 

前几行的访问时间很低，我不知道为什么。

然后程序运行稳定，访问时间大约为0.4s，我认为原因是大多数访问都碰到了L1级缓存。

随着更大的长度，时间变成1.5秒左右。也许一级缓存不起作用，但二级缓存起作用。

然后时间到了4秒，也许根本没有缓存命中？

上述结果似乎符合我的预期。

但是！意外的事情发生了，我感到惊讶。

当超过20000长度，访问时间变为：

length 20000 costs 1.828000 seconds access time:1.453000 
length 22000 costs 1.867000 seconds access time:1.492000 
length 24000 costs 1.959000 seconds access time:1.584000 
length 26000 costs 1.977000 seconds access time:1.603000 
length 28000 costs 1.987000 seconds access time:1.613000 
length 30000 costs 2.045000 seconds access time:1.669000 
length 32000 costs 1.951000 seconds access time:1.575000 
length 34000 costs 1.980000 seconds access time:1.611000 
length 36000 costs 1.988000 seconds access time:1.613000 
length 38000 costs 1.993000 seconds access time:1.619000 
length 40000 costs 1.850000 seconds access time:1.473000 
length 42000 costs 2.010000 seconds access time:1.634000 
length 44000 costs 1.991000 seconds access time:1.615000 
length 46000 costs 1.977000 seconds access time:1.601000 
length 48000 costs 1.977000 seconds access time:1.601000 
length 50000 costs 1.927000 seconds access time:1.552000 
length 52000 costs 1.907000 seconds access time:1.531000 
length 54000 costs 2.013000 seconds access time:1.637000 
length 56000 costs 2.014000 seconds access time:1.639000 
length 58000 costs 2.011000 seconds access time:1.640000 
length 60000 costs 1.978000 seconds access time:1.606000 
length 62000 costs 2.046000 seconds access time:1.672000 
length 64000 costs 2.076000 seconds access time:1.700000 
length 66000 costs 2.068000 seconds access time:1.693000 
length 68000 costs 2.014000 seconds access time:1.639000 
length 70000 costs 2.123000 seconds access time:1.748000 
length 72000 costs 2.032000 seconds access time:1.646000 
length 74000 costs 2.015000 seconds access time:1.638000 
length 76000 costs 2.023000 seconds access time:1.646000 
length 78000 costs 1.873000 seconds access time:1.497000 
length 80000 costs 1.655000 seconds access time:1.278000 

任何人都可以解释为什么这些奇怪的事情发生？我现在卡住了，不知道这件事。

在此先感谢。

Answer 1

当你测试这样的东西时，你应该保持你的系统处于空闲状态。

我在我的电脑里测试了三次，当长度> 5000时，它保持3秒。