########################################
Cache
########################################


Cache 对循环的影响
****************************************

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

.. code-block:: java

   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++

.. code-block:: cpp

   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);

结果是::

   0.177454
   0.0971365
   0.0398913
   0.0338586
   0.028566
   0.0274254

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