Menu
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?
718
This is due to cache misses. C multidimensional arrays are stored with the last dimension as the fastest. So the first version will miss the cache on every iteration, whereas the second version won't. So the second version should be substantially faster.
Unless you are talking about static arrays, 1D is faster. Clearly the 2D case loses the cache locality and uses more memory. It also introduces an extra indirection (and thus an extra pointer to follow) but the first array has the overhead of calculating the indices so these even out more or less. Save this answer.
It only shows that in C language, 2-D arrays are stored in row major order and thus iterating its elements in a row major order is more efficient. In languages like Pascal and Fortran, iterating by column major order will be more efficient because 2-D arrays are stored in column major order there.
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.
115
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
