컴퓨터 시스템 : 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) 순서

그림 3.26 행우선 배열의 원소들

배열 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 명령어 등을 활용하여 효율적으로 계산

---