Cache

Cache 对循环的影响

CPU 在读取 Cache 的时候一次读取一个 Cache Line。Cache Line 常见的大小为 64 字节。在循环中步长在一个 Cache Line 中的循环对速度影响一般不大，但是对于不同行的 Cache Line 具有很大的变化。例如：

static public void main(String [] args){
int [] arr = new int[64*1024*1024];

long start1 = System.currentTimeMillis();
for(int i =0; i <arr.length; i++) arr[i] *=3;
System.out.println(System.currentTimeMillis() - start1);

long start2 = System.currentTimeMillis();
for(int i =0; i <arr.length; i+=16) arr[i] *=3;
System.out.println(System.currentTimeMillis() - start2);

long start3 = System.currentTimeMillis();
for(int i =0; i <arr.length; i+=32) arr[i] *=3;
System.out.println(System.currentTimeMillis() - start3);
}

结果是:

30
33
26

原因就是前两个循环读取的 Cache Line 数量是一样的。第三种情况理想情况下应该是少一半，这里不知道什么情况。

另外有些问题的是 C++

int  arrLen = 64 * 1024 * 1024;
int* arr    = new int[arrLen];
for(int i = 0; i < arrLen; ++i) arr[i] = 0;
auto printTime = [&](int step) {
   auto start = std::chrono::steady_clock::now();
   for(int i = 0; i < arrLen; i += step) arr[i] += 2;
   auto                          end    = std::chrono::steady_clock::now();
   std::chrono::duration<double> result = end - start;
   cout << result.count() << endl;
};
printTime(1);
printTime(2);
printTime(6);
printTime(10);
printTime(16);
printTime(32);

结果是:

这里和 Java 明显不同。这已经是关闭了编译器优化了。即使是清空流水线和清除 cache 也不会影响倍数关系。在我电脑上一级和二级缓存的 Cache Line 都是 64 字节