所谓连续内存访问比随机访问更快,指的是locality更好,具体就是指cache hit rate更高。但如果要观测这个现象,题主的代码并不合适。问题在于题主的两个Test函数中都只访问了两个int的地址,远远小于cache容量,不管他们离的多远都会落在cache内,唯一的区别是,Test1中,两个变量分别分配在buffer首尾,相距较远,更有可能被分配在两个cache line中(具体取决于cache映射算法),而Test2中,两个变量相邻,更有可能会被分配在一个cache line中(具体取决于cache line大小),这个差别是几乎可以忽略不计的。
更可行并且更简单的方法是,开一个大数组访问每个元素,分别用连续和随机两种方式。下面代码假设cache line大小是64 byte:
void test1() { size_t size = 64 * 1024 * 1024 / sizeof(int); int * buf = new int[size]; int count = 0; std::chrono::high_resolution_clock::time_point startTime = std::chrono::high_resolution_clock::now(); for (size_t i = 0; i < size; i++) { count += buf[i] * buf[i] % (buf[i] + 100); } std::chrono::high_resolution_clock::time_point endTime = std::chrono::high_resolution_clock::now(); std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count() << "ms" << std::endl; } void test2() { size_t size = 64 * 1024 * 1024 / sizeof(int); int * buf = new int[size]; size_t numElemsPerCacheLine = 64 / sizeof(int); size_t numCacheLines = size / numElemsPerCacheLine; int count = 0; std::chrono::high_resolution_clock::time_point startTime = std::chrono::high_resolution_clock::now(); for (size_t i = 0; i < size; i++) { count += buf[i * numElemsPerCacheLine % numCacheLines + i % numCacheLines]; } std::chrono::high_resolution_clock::time_point endTime = std::chrono::high_resolution_clock::now(); std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count() << "ms" << std::endl; }
其中test1是连续访问(从头到尾),test2是随机访问(连续的两次访问跳一个cache line,到最后一个cache line时跳回第一个cache line);因test2中计算地址时多了一个乘法,一个取模,一个加法,所以test1中用buf[i]的多次计算补平。