컴퓨터 메모리 저장 방식과 2차원 for문 관계

질문

아래 코드와 같이 2차원 배열이 있고 두 개의 이중 for문이 있을 때 어떤 접근이 더 효율적일까?

(모든 상황은 다 동일하고 단순 두 개의 코드 차이만 있다고 가정한다.)

답변

당연히 1번 이중 for문 즉 행 접근이 더 효율적일 것이라 생각했다.

근거

1) 컴퓨터 메모리는 일렬로 구성되어 있다, 즉 row 우선 순서로 저장된다.

2) 따라서 이차원 배열이라도 row 여러개가 순차적으로 저장된 뒤 그 다음 column으로 이동해 row를 채우지 않을 까 생각했다.

3) 그렇기에 CPU 캐시 효율성을 높이는 접근 방법은 row먼저 접근하는 1번 이중 for문이라고 생각했다.

찾아 본 결과 내 접근이 맞았다!!! 더 나아가 2번의 경우 메모리 접근의 불연속이 생겨 CPU 캐시 미스가 더 자주 생길 수 있다 한다.

int main(void)
{
    int a[1000][1000] = {1, };
    int sum = 0;
    
    // row (가로 접근)
    for ( int i = 0; i < 1000; i++ )
    {
        for ( int j = 0; j < 1000; j++ )
        {
            sun += a[i][j];
        }
    }
    
    // column (세로 접근)
    for ( int i = 0; i < 1000; i++ )
    {
        for ( int j = 0; j < 1000; j++ )
        {
            sun += a[j][i];
        }
    }
}