다차원 배열 & Row-major Order: 심층 탐구

Source: Dev.to

위의 링크에 있는 전체 텍스트를 제공해 주시면, 해당 내용을 한국어로 번역해 드리겠습니다. 현재는 링크만 확인할 수 있으므로, 번역이 필요한 본문을 복사해서 알려 주세요.

다차원 배열과 행‑우선 순서

개념적 보기

int matrix[3][4];

2‑차원 격자로 생각하면 다음과 같습니다:

[0][0]  [0][1]  [0][2]  [0][3]
[1][0]  [1][1]  [1][2]  [1][3]
[2][0]  [2][1]  [2][2]  [2][3]

물리적 보기

메모리는 선형(1‑차원)입니다. CPU는 메모리를 순차적으로만 주소 지정할 수 있기 때문에, 컴파일러는 다차원 배열을 연속된 메모리 블록에 매핑합니다.

행‑우선 순서(row‑major order) 는 요소를 행 단위로 저장합니다; 가장 오른쪽 인덱스가 가장 빨리 변합니다.

주소 계산

배열 type array[ROWS][COLS] 에 대해:

address = base_address + (i * COLS + j) * sizeof(type)

• i * COLS – i개의 전체 행을 건너뛴다.
• + j – 현재 행 안에서 j개의 요소를 이동한다.
• * sizeof(type) – 바이트 단위로 스케일링한다.

예시 – int matrix[3][4] 가 0x1000에 위치하고, 요소 matrix[2][3] 의 주소는:

address = 0x1000 + (2 * 4 + 3) * 4
        = 0x1000 + 11 * 4
        = 0x102C

3차원 배열

type array[D1][D2][D3] 에 대해:

address = base + (i * D2 * D3 + j * D3 + k) * sizeof(type)

• i * D2 * D3 – i개의 전체 “평면(plane)”을 건너뛴다.
• j * D3 – 현재 평면 안에서 j개의 행을 건너뛴다.
• k – 행 안의 위치.

일반 N차원 공식

array[i1][i2]...[iN] 이며 차원이 [D1][D2]...[DN] 일 때:

offset = i1 * (D2*D3*...*DN) +
         i2 * (D3*D4*...*DN) +
         ...
         i(N‑1) * DN +
         iN
address = base + offset * sizeof(type)

컴파일러 변환 예시

int arr[3][4][5];
int x = arr[1][2][3];   // 다음과 같이 변환됨
int x = *(arr + (1*4*5 + 2*5 + 3));

포인터로의 감소(Decay)

• arr + 1 → 전체 행 하나(4 int = 16 byte) 만큼 전진.
• *(arr + 1) + 2 → arr[1][2] 를 가리킴.

arr[i][j] 의 어셈블리 (x86‑64)

; 가정:
;   RAX = arr 의 기본 주소
;   RBX = i
;   RCX = j
;   COLS = 컴파일 타임 상수

mov    rdx, rbx           ; rdx = i
imul   rdx, COLS          ; rdx = i * COLS
add    rdx, rcx           ; rdx = i * COLS + j
shl    rdx, 2             ; rdx = (i*COLS + j) * 4   ; sizeof(int)=4
add    rdx, rax           ; rdx = base + offset
mov    eax, [rdx]         ; arr[i][j] 로드

현대 컴파일러는 LEA 로 연산을 합칠 수 있습니다:

lea    rdx, [rbx + rbx*4]   ; rdx = i * 5   (COLS = 5 인 경우)
lea    rdx, [rdx*4 + rax]   ; 스케일링과 기본 주소 결합
mov    eax, [rdx + rcx*4]   ; arr[i][j] 로드

행‑우선 vs. 열‑우선 순회

행‑우선( C 에서 최적) :

int main(void) {
    int arr[2][3] = {
        {1, 2, 3},
        {4, 5, 6}
    };

    printf("Base address: %p\n", (void *)arr);

    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 3; ++j) {
            printf("arr[%d][%d] = %d at address %p\n",
                   i, j, arr[i][j], (void *)&arr[i][j]);
        }
    }

    /* 1‑차원 평탄 배열로 취급 */
    int *flat = (int *)arr;
    printf("\nAs

> **Source:** ...

```c
flat array:\n");
    for (int k = 0; k < 6; ++k) {
        printf("flat[%d] = %d at address %p\n",
               k, flat[k], (void *)&flat[k]);
    }

    return 0;
}

샘플 출력

Base address: 0x7ffc8b3e1a40
arr[0][0] = 1 at address 0x7ffc8b3e1a40
arr[0][1] = 2 at address 0x7ffc8b3e1a44
arr[0][2] = 3 at address 0x7ffc8b3e1a48
arr[1][0] = 4 at address 0x7ffc8b3e1a4c
arr[1][1] = 5 at address 0x7ffc8b3e1a50
arr[1][2] = 6 at address 0x7ffc8b3e1a54

As flat array:
flat[0] = 1 at address 0x7ffc8b3e1a40
flat[1] = 2 at address 0x7ffc8b3e1a44
flat[2] = 3 at address 0x7ffc8b3e1a48
flat[3] = 4 at address 0x7ffc8b3e1a4c
flat[4] = 5 at address 0x7ffc8b3e1a50
flat[5] = 6 at address 0x7ffc8b3e1a54

주소가 sizeof(int)(4 바이트)씩 순차적으로 증가하는 것을 확인할 수 있으며, 이는 행 우선(row‑major) 레이아웃임을 증명합니다.

일차원 접근 단축법

int rows = 3, cols = 4;
int *arr = malloc(rows * cols * sizeof(int));

/* Access arr[i][j] as a flat array */
int value = arr[i * cols + j];

동적 2‑D 배열 할당

/* 각 행을 별도로 할당 – 각 행이 자체 할당을 가짐 */
int **arr = malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    arr[i] = malloc(cols * sizeof(int));
}

/* 자연스럽게 접근: arr[i][j] */

/* 연속 블록 – 전체 행렬을 하나의 할당으로 */
int **arr = malloc(rows * sizeof(int *));
arr[0] = malloc(rows * cols * sizeof(int));   /* 큰 한 덩어리 */
for (int i = 1; i < rows; i++) {
    arr[i] = arr[0] + i * cols;                /* 각 행의 시작을 가리키도록 */
}

/* 정리 */
free(arr[0]);   /* 큰 데이터 블록 해제 */
free(arr);      /* 행 포인터 배열 해제 */

Memory Layout & Addressing

• 다차원 배열은 선형화되어 메모리에 배치됩니다.

• 행 우선 순서(C의 기본)란 가장 오른쪽 인덱스가 가장 빠르게 변한다는 의미입니다.

• arr[i][j]의 주소는 다음과 같이 계산됩니다.

  base_address + (i * COLS + j) * sizeof(element_type)

캐시, TLB 및 접근 패턴

• 현대 CPU는 계층적 캐시(L1, L2, L3)를 가지고 있다. 순차 접근은 캐시 적중률을 최대화한다.
• Cache line 예시 (64 bytes):
  • int = 4 bytes → 라인당 16개의 int.
  • arr[0][0]에 접근하면 arr[0][0] … arr[0][15]가 캐시로 로드된다.
• TLB는 가상‑주소에서 물리‑주소로의 변환을 캐시한다. 스트라이드 접근이나 무작위 접근은 TLB 스래싱을 일으킬 수 있다.
• CPU는 순차 패턴을 감지하면 다음 캐시 라인을 미리 가져온다. 행‑우선 순서(row‑major order)로 행렬을 순회하면(내부 루프가 열을 담당) 하드웨어가 효율적으로 프리패치한다.

핵심 요점

• 선형화: 다차원 배열은 단일 연속 블록으로 저장됩니다.
• 행 우선 순서: 가장 오른쪽 인덱스가 가장 빠르게 변합니다.
• 주소 공식: base + (i * COLS + j) * sizeof(type).
• 순회가 중요: 최적 성능을 위해 저장 순서대로 반복합니다.
• 진짜 배열 vs. 포인터‑투‑포인터: 레이아웃이 달라서 서로 다른 트레이드오프가 있습니다 (연속성 vs. 가변 행 크기).
• 컴파일러 매직: arr[i][j]는 자동으로 포인터 연산으로 변환됩니다.
• 캐시 지역성: 순차 접근은 무작위 접근보다 10–100× 빠를 수 있습니다.
• 이러한 저수준 세부 사항을 이해하면 다음에 도움이 됩니다:
  • 더 빠른 코드를 작성하고,
  • 메모리 관련 버그를 디버깅하며,
  • 하드웨어나 다른 언어와 깔끔하게 인터페이스할 수 있습니다.