컴퓨터 시스템 : CSAPP 3장 정리 - 3.8 배열의 할당과 접근 Part.1
3.8 배열의 할당과 접근(Array Allocation and Access)
이 절은 배열이 메모리에 어떻게 배치되고 접근되는지, 그리고 어셈블리 코드로 어떻게 변환되는지를 중점적으로 설명한다. 배열은 C 언어에서 스칼라 데이터를 모아 하나의 집합적인 자료형으로 만들 수 있는 수단이다. C는 배열을 아주 단순한 방식으로 구현하며, 이를 통해 기계어로의 변환도 간단해지는 장점이 있다.
🔷 3.8.1 배열의 기본 원리 (Basic Principles)
📌 핵심 아이디어
배열은 C 언어에서 메모리를 연속적으로 할당받는 자료구조이다. 컴파일러가 배열을 다룰 때는 포인터 + 오프셋 방식으로 매우 단순하게 처리한다.
배열은 포인터처럼 행동하지만, 실제로는 정적 메모리 블록을 가리키는 기준 주소(base address)다.
🧩 메모리에서 배열의 배치
배열이 선언되면, 해당 요소들의 총 크기만큼의 메모리 공간이 연속적으로 할당된 다.
T A[N]; // 타입 T, 크기 N- 배열의 시작 주소를 xA, 요소 크기를 L이라고 하면
- 배열 A는 xA, xA + L, xA + 2L, ..., xA + (N-1)L 위치에 각 요소를 저장한 다.
이 구조 덕분에 A[i]에 접근할 때 별도의 복잡한 정보 없이:
A[i] ≡ *(A + i) ≡ 메모리 주소 xA + L*i로 변환된다. 이 연산은 어셈블리 수준에서도 아주 간단하게 구현된다.
🔍 자료형별 예시
배열의 각 요소 타입에 따라 L 값(바이트 크기)이 다르다:
| 선언 | 요소 타입 | 크기(L) | 총 바이트 | 주소 계산 예 |
| char A[12] | char | 1 | 12B | xA + i |
| char *B[8] | 포인터 | 8 | 64B | xB + 8*i |
| int C[6] | int | 4 | 24B | xC + 4*i |
| double *D[5] | 포인터 | 8 | 40B | xD + 8*i |
이렇게 배열은 자료형에 따라 정해진 크기의 스케일링으로 주소 오프셋을 계산한다.
🔧 어셈블리 관점: x86-64의 주소 계산
x86-64 명령어는 다음과 같은 주소 형식을 지원한다:
D(Rb, Ri, S) ≡ Mem[Rb + Ri*S + D]- Rb: 기준 주소 (base) — 배열의 시작 주소
- Ri: 인덱스 값
- S: 스케일 값 (1, 2, 4, 8 중 하나)
- D: 정적 오프셋
예: movl (%rdx,%rcx,4), %eax → E[i] 접근, 여기서 %rdx = xE, %rcx = i, 4 = int 크기
💡 왜 이 구조가 좋은가?
- 간단한 연산만으로 주소 계산이 가능 → 컴파일러 최적화, 하드웨어 지원에 유리
- 포인터 연산도 동일한 원리로 작동 → *(p + i) ≡ p[i]
- 복잡한 배열 구조도 일관된 방식으로 처리 가능
✅ 요약
- 배열은 연속적인 메모리 공간이며, 요소 접근은 주소 = 시작 + 인덱스 × 크기로 계산됨.
- 이 구조는 어셈블리 명령어에서도 직접적으로 구현되며, 매우 효율적임.
- x86-64 아키텍처의 D(Rb, Ri, S) 형식은 이 계산 방식을 기계 수준에서 그대로 지원함.
🔷 3.8.2 포인터 연산 (Pointer Arithmetic)
이 절에서는 C 언어의 포인터와 배열의 유사성 그리고 포인터 연산이 어떻게 배열 인덱싱과 동일하게 작동하는지를 설명한다.
📌 포인터 연산의 기본 원리
C에서는 포인터에 대한 산술 연산이 허용되며, 그 연산은 자료형의 크기 단위로 자동 스케일링 된다.
예시:
int *p; // sizeof(int) = 4
p + 3 // 실제 계산: p + 3 * 4 = p + 12 (바이트 단위 주소 증가)즉, p + i는 내부적으로 xp + L*i로 해석된다.
여기서 xp는 포인터 p가 가리키는 주소이고, L은 자료형 T의 크기이다.
🧠 연산자 정리
- &Expr : 어떤 객체의 주소를 구함 (포인터 생성)
- *AExpr : 포인터가 가리키는 주소의 값을 참조함 (역참조)
- A[i] ≡ *(A + i) : 배열 인덱싱은 포인터 연산 + 역참조의 축약형
이 식들은 모두 주소 계산을 통해 메모리에 접근하는 형태로 번역된다.
🔍 어셈블리 예시: 배열 E에 대한 다양한 접근
조건:
- 배열 시작 주소 xE는 %rdx
- 인덱스 i는 %rcx
| C 표션식 | 타입 | 의미 | 어셈블리 코드 |
| E | int* | 배열 시작 주소 | movq %rdx, %rax |
| E[0] | int | M[xE] | movl (%rdx), %eax |
| E[i] | int | M[xE + 4i] | movl (%rdx,%rcx,4), %eax |
| &E[2] | int* | xE + 8 | leaq 8(%rdx), %rax |
| E + i - 1 | int* | xE + 4i - 4 | leaq -4(%rdx,%rcx,4), %rax |
| *(E + i - 3) | int | M[xE + 4i - 12] | movl -12(%rdx,%rcx,4), %eax |
| &E[i] - E | long | i | movq %rcx, %rax |
💡 핵심 요점
- 포인터 산술 연산은 자료형 크기를 고려하여 자동 스케일링됨
- 배열 접근과 포인터 접근은 완전히 동일하게 처리됨 (즉, A[i] ≡ *(A + i))
- 주소 계산은 어셈블리 명령어 하나로 효율적으로 구현 가능 (ex: leaq)
✅ 요약
- 포인터 연산은 배열 인덱싱과 동일한 방식으로 동작
- 컴파일러는 포인터 산술 연산을 통해 정확한 주소 계산을 수행함
- 어셈블리에서 leaq, movl 등의 명령어로 간단하게 구현 가능
🔷 3.8.3 다중 배열 (Nested Arrays)
이 절은 배열이 다차원 구조로 중첩되어 정의될 경우, 메모리 상에 어떻게 배치되고 접근되는지를 설명한다. 특히 2차원 배열에서 행 우선(row-major) 방식으로 메모리에 저장된다는 점이 핵심이다.
📌 배열의 중첩 선언
int A[5][3];이 선언은 다음과 같이 해석된 다:
typedef int row3_t[3];
row3_t A[5];즉, A는 길이 3인 정수형 배열 row3_t를 5개 가진 배열이다.
- 각 row3_t는 3개의 int 값을 포함 → 12바이트
- 따라서 전체 배열은 12 × 5 = 60바이트
📐 메모리 배치: 행 우선(row-major) 순서
배열 A는 메모리에 다음 순서로 배치된 다:
A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2], ..., A[4][2]이러한 순서는 A가 "배열의 배열"로 선언되어 있기 때문이다.
- 즉, 먼저 A[0] (세 개의 정수), 그다음 A[1], A[2]... 순서로 저장됨
- 이를 통해 2차원 배열을 1차원 메모리 주소로 표현할 수 있게 됨
🧮 주소 계산 공식 (Equation 3.1)
T D[R][C];배열 D[i][j]의 메모리 주소는:
&D[i][j] = xD + L * (C * i + j)- xD: 배열의 시작 주소
- L: 자료형 T의 크기 (예: int는 4바이트)
- C: 열 수
- i: 행 인덱스, j: 열 인덱스
이 공식은 중첩 배열이 어떻게 단일 선형 주소 공간에 매핑되는지를 설명한다.
🔍 예시: int A[5][3]에서 A[i][j]에 접근
가정:
- 시작 주소: %rdi = xA
- i: %rsi, j: %rdx
어셈블리 코드:
leaq (%rsi,%rsi,2), %rax ; 3 * i 계산 → %rax
leaq (%rdi,%rax,4), %rax ; xA + 12i 계산
movl (%rax,%rdx,4), %eax ; [xA + 12i + 4j] 값 로드이 코드는 최종 주소 xA + 12i + 4j를 계산하여 해당 요소에 접근하는 과정이다.
즉, 컴파일러는 위의 공식대로 메모리 주소를 계산해서 적절한 요소에 접근한다.
✅ 요약
- C의 다차원 배열은 배열의 배열(nested arrays)로 정의됨
- 행 우선(row-major) 순서로 메모리에 저장됨
- 컴파일러는 D[i][j] = xD + L(Ci + j) 형태로 주소 계산
- 어셈블리에서는 leaq 명령어 등을 활용하여 효율적으로 계산