What if I told you that changing the order of two nested loops could make your program 45 times slower , without changing the amount of work it performs?
That's exactly what I observed in a recent C++ benchmarking experiment.
While exploring low-level performance optimization and GPU inference, I wanted to understand how CPUs access memory and why cache locality matters.
So I decided to benchmark two approaches to traversing a 2D matrix:
Row-major traversal
Column-major traversal
The results were quite surprising.
Let's understand what happened.
1. How is a 2D array stored in memory?
Consider a simple 3 Γ 4 matrix:
int matrix [ 3 ] [ 4 ] = { { 1 , 2 , 3 , 4 } , { 5 , 6 , 7 , 8 } , { 9 , 10 , 11 , 12 } } ;
Enter fullscreen mode
Exit fullscreen mode
Although we visualize this as a two-dimensional structure, C++ stores it in contiguous memory using row-major order .
Its physical memory layout looks like this:
1 β 2 β 3 β 4 β 5 β 6 β 7 β 8 β 9 β 10 β 11 β 12
Enter fullscreen mode
Exit fullscreenβ¦