당신의 배열이 느린 이유

같은 코드, 다른 성능

2차원 배열의 모든 원소를 1로 채우는 단순한 코드다. 두 코드의 차이는 순회 순서뿐이다.

#define N 10000

int arr[N][N];

// (A) 행 우선 순회 — Row-major
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        arr[i][j] = 1;

// (B) 열 우선 순회 — Column-major
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        arr[i][j] = 1;

결과는 (A)가 (B)보다 수 배에서 수십 배 빠르다¹. 왜 그럴까?

메모리는 1차원이다

프로그래밍에서는 arr[i][j] 처럼 2차원으로 생각하지만, 실제 메모리는 1차원 연속 공간이다.

C/C++, Java, Python(NumPy 기본값) 등 대부분의 언어는 Row-major order로 배열을 저장한다². 즉, 같은 행의 원소들이 메모리에서 연속으로 붙어 있다³.

논리적 배열:         메모리 실제 배치:
[0][0] [0][1] [0][2]   → [0][0] [0][1] [0][2] [1][0] [1][1] [1][2] ...
[1][0] [1][1] [1][2]

반면 Fortran, MATLAB, Julia는 Column-major order로, 같은 열의 원소들이 연속으로 배치된다.

CPU 캐시의 동작 원리

CPU가 메모리에서 데이터를 읽을 때 해당 바이트 하나만 가져오지 않는다. 캐시 라인(Cache Line) 단위(보통 64바이트)로 주변 데이터를 한꺼번에 가져온다⁴.

메모리: ... [0][0] [0][1] [0][2] [0][3] [0][4] [0][5] ...
             ↑_________________________________↑
             한 번의 메모리 접근으로 캐시 라인 전체를 가져옴

int가 4바이트라면, 캐시 라인 하나에 16개의 int가 들어간다.

캐시 히트 vs 캐시 미스

행 우선 순회 (A) — 캐시 친화적

arr[0][0]을 읽는 순간 arr[0][1] ~ arr[0][15]까지 캐시에 올라온다. 다음 접근인 arr[0][1]은 이미 캐시에 있으므로 캐시 히트(Cache Hit) 다.

접근 순서: [0][0] → [0][1] → [0][2] → ... → [0][15] → [0][16] ...
캐시:      MISS     HIT      HIT             HIT       MISS ...

캐시 미스율 낮음

열 우선 순회 (B) — 캐시 비친화적

arr[0][0]을 읽어 캐시 라인에 arr[0][0] ~ arr[0][15]가 올라오지만, 다음 접근은 arr[1][0]이다. 이건 10,000칸 떨어진 메모리 주소에 있으므로 캐시 미스(Cache Miss) 다.

접근 순서: [0][0] → [1][0] → [2][0] → ... → [9999][0] → [0][1] ...
캐시:      MISS     MISS     MISS             MISS       MISS ...

캐시 미스율 높음

실제 측정

#include <stdio.h>
#include <time.h>

#define N 10000

int arr[N][N];

int main() {
    clock_t start, end;

    // 행 우선
    start = clock();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            arr[i][j] = 1;
    end = clock();
    printf("Row-major: %.3f sec\n", (double)(end - start) / CLOCKS_PER_SEC);

    // 열 우선
    start = clock();
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            arr[i][j] = 1;
    end = clock();
    printf("Col-major: %.3f sec\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

3차원 이상 배열에서도 동일하다

3차원 배열 arr[A][B][C]에서 Row-major 언어 기준으로 가장 안쪽 차원(C) 이 메모리에서 연속이다. 따라서 가장 안쪽 루프가 가장 안쪽 차원을 순회해야 캐시 친화적이다.

// 캐시 친화적 — 가장 안쪽 루프가 가장 안쪽 차원
for (int i = 0; i < A; i++)
    for (int j = 0; j < B; j++)
        for (int k = 0; k < C; k++)
            arr[i][j][k] = 1;

// 캐시 비친화적
for (int k = 0; k < C; k++)
    for (int j = 0; j < B; j++)
        for (int i = 0; i < A; i++)
            arr[i][j][k] = 1;

정리

	행 우선 순회	열 우선 순회
메모리 접근 패턴	연속 (Sequential)	불연속 (Strided)
캐시 미스율	낮음 (~6%)	높음 (~100%)
성능	빠름	느림

그냥 최대한 배열 차원 순서대로 접근하게 설계하세요