Menu
Which of the following orderings of nested loops to iterate over a 2D array is more efficient in terms of time (cache performance)? Why?
int a[100][100]; for(i=0; i<100; i++) { for(j=0; j<100; j++) { a[i][j] = 10; } } or
for(i=0; i<100; i++) { for(j=0; j<100; j++) { a[j][i] = 10; } } 
281
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.
Nested loops are frequently (but not always) bad practice, because they're frequently (but not always) overkill for what you're trying to do. In many cases, there's a much faster and less wasteful way to accomplish the goal you're trying to achieve.
The first method is slightly better, as the cells being assigned to lays next to each other.
First method:
[ ][ ][ ][ ][ ] .... ^1st assignment ^2nd assignment [ ][ ][ ][ ][ ] .... ^101st assignment Second method:
[ ][ ][ ][ ][ ] .... ^1st assignment ^101st assignment [ ][ ][ ][ ][ ] .... ^2nd assignment 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
