c++ 2d array access speed changes based on [a][b] order?
Possible Duplicate:
Why is my program slow when looping over exactly 8192 elements?
I have been tinkering around with a program that I'm using to simply sum the elements of a 2d array. A typo led to what seem to me at least, some very strange results.
When dealing with array, matrix[SIZE][SIZE]:
for(int row = 0; row < SIZE; ++row)
for(int col = 0; col < SIZE; ++col)
sum1 += matrix[row][col];
Runs very quickly, however is the above line sum1... is modified:
sum2 += matrix[col][row]
As I did once on accident without realizing it, I notice that my runtime increases SIGNIFICANTLY. Why is this?
This is due to caching behaviour of your program.
Arrays are just consecutive blocks of memory, so when you access [row][column] you are accessing the memory sequentially. This means the data page you are accessing is on the same page, so the access is much faster.
When you do [column][row], you aren't accessing that memory sequentially anymore, so you will end up with more cache misses, so your program runs much slower.
The memory locations of matrix[row][col] and matrix[row][col + 1] are adjacent.
The memory locations of matrix[row][col] and matrix[row + 1][col] are separated by SIZE amount of items.
Computers like accessing memory SEQUENTIALLY not RANDOMLY , thus the adjacent access is faster. For an analogy think hard drive performance, sequential read/write is always better than random read/write. This has to do with how your CPU caches memory and tries to predict what you'll need next.
It's because in the quicker case the CPU's memory prefetching is actually useful as you're iterating in a linear fashion. In the slow case you're jumping around the memory and so prefetching has little effect as the data is unlikely to be in the cache.
链接地址: http://www.djcxy.com/p/15074.html上一篇: 为什么初始化一个大小为2的幂矩阵？