csapp

죽지도 않고 또 온 csapp다

오늘은 csapp 3.8이다

3.8 배열 할당과 접근

C 프로그램에서 배열이 기계수준에서 어떻게 처리되는지다

컴파일러는 계산을 무척 단순화해 파악하기 어려울 수 있다

컴파일러가 C 구문 변환하는 방식과 메모리 관리의 핵심 부분이다

3.8.1 기본원리

간단한 배열 저장하는 원리를 서술한다

요점은
C의 배열은 가상 메모리의 바이트 배열이며, 포인터는 메모리 주소를 나타내고, 컴파일러는 성능을 위해 지역 변수를 레지스터에 유지하는 최적화를 수행한다는 거다

그 외에는 어떻게 작동하는지 예시 나오는데 스킵하겠다

궁금하면 찾아보면 나온다

3.8.2 포인터 산술 연산

C에서는 포인터에서 산술 연산 쓴다

이런 식으로 포인터 산술 연산을 할 때,
포인터가 가리키는 데이터 타입의 크기만큼 값을 자동으로 조정한다

즉,

• p + i는 실제로 포인터 값 + (데이터 타입 크기 * i)가 된다.

• 배열 인덱싱 A[i]도 내부적으로는 *(A + i)로 동작한다.

예시 표

표현식	타입	값	어셈블리 코드
$E$	int*	$xE$	movl %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

• C에서 & (주소 연산자) 와 *(역참조 연산자) 를 조합하면 포인터와 값을 자유롭게 오갈 수 있다.

• 예: *&x == x

• 포인터끼리의 뺄셈은 두 포인터가 같은 배열 안에 있을 때, 인덱스 차(몇 번째 떨어져있는지)를 알 수 있다.

• int, double 등 타입에 따라 연산 결과가 달라짐

  • 예를 들어, double* p; p + 2라면 실제 주소는 p에서 16(=8×2) 바이트만큼 증가

요점은
C에서 포인터와 배열은 메모리 주소와 산술 연산을 통해 효율적으로 연결되며, 어셈블리 레벨에서는 이 산술이 데이터 타입 크기에 맞춰 변환된다. 이를 통해 배열 요소의 빠르고 직접적인 접근이 가능하다

3.8.3 중첩 배열

요점 :
배열 할당과 참조의 일반 원칙은 배열의 배열을 만들 때에도 그대로 적용된다

중첩 배열 예시

• 선언: int A[5][3];
  → 5행 3열짜리 2차원 배열
  → 총 5 × 3 = 15개의 int(각 4바이트) = 60바이트 연속 공간 차지

• 메모리 저장 순서(행 우선):
  A[0][0], A[0][1], A[0][2],
  A[1][0], A[1][1], A[1][2], …
  이런 식으로 한 행의 모든 열이 연속 저장, 다음 행이 그 뒤에 저장됨

• 특정 요소의 주소 계산:
  A[i][j]의 주소 = 배열 시작주소 + 4 × (3i + j)
  (여기서 4는 int 크기, 3은 열의 개수)

• 어셈블리 예시:

  • $3i$ 계산 → leaq (%rsi,%rsi,2), %rax

  • $12i(=3i×4)$ 더하기 → leaq (%rdi,%rax,4), %rax

  • $4j$ 더해 실제 주소 얻기 및 값 읽기 → movl (%rax,%rdx,4), %eax

이를 통해 다차원 배열도 실제로는 1차원 메모리 공간에 행 우선 방식으로 저장되며, 원하는 요소의 주소는 행과 열 정보를 합쳐서 계산 한다는 걸 알 수 있다

3.8.4 고정 크기 배열

요점 :
C 컴파일러는 고정 크기 다차원 배열에서 동작하는 코드에 대해 다양한 최적화를 수행할 수 있다

예시로 최적화 코드가 나오는데

어차피 구체적인 예시는 나중에 공부하면 되니까 어떤식으로 이루어지는 지만 간략히 다루겠다

최적화

• 인덱스 기반 반복 → 포인터 기반 반복

  • 배열 인덱스 대신 포인터를 직접 이동하여 반복문 효율을 극대화

  • 불필요한 인덱스 연산을 없애고 필수 연산만 남김

• 배열 인덱싱의 복잡한 주소 계산 → 단순한 포인터 이동

  • 배열의 행/열 위치 계산이 모두 사라지고, 포인터 증가만으로 원하는 위치에 접근

  • 복잡한 산술 연산 대신 단순한 주소 이동으로 최적화

• 루프 종료 조건도 단순히 포인터 비교로 처리

  • 반복 종료 조건이 인덱스나 카운터 비교가 아닌, 시작/끝 포인터만 비교하도록 단순화

  • 반복문 내 연산이 더 줄어듦

3.8.5 가변 크기 배열

요점 :
가변 크기 배열은 컴파일 시점에 크기를 알 수 없어, 런타임에 크기가 결정되고, 지역 변수로 선언될 경우 스택에 동적으로 할당된다.

기존엔 배열크기를 반드시 정했어야 했으나
가변 크기 배열 기능이 추가됨

가변 크기의 경우 고정 크기 배열과 다른 최적화를 해야함

두 배열의 차이점

비교 항목	고정 크기 배열	가변 크기 배열 (VLA)
크기 결정 시점	컴파일 시점 (상수, 매크로 등으로 지정)	실행 시점 (함수 인자, 지역 변수, 런타임 값)
주소 계산 방법	상수배(shift/add)로 단순화 가능 예: 4×3i+4j (i행 j열)	곱셈 필요 예: 4×(n×i+j) (n은 런타임 값)
컴파일러 최적화	인덱스 → 포인터 이동 변환 매우 용이 루프 풀기 등 적극	곱셈 최소화 위해 패턴 분석 포인터 이동 등 일부 적용
반복문 패턴	인덱스 없이 포인터만 이동하는 최적화 적용 쉬움	루프 인덱스(j) 남기는 경우 많음
성능	더 빠름 (곱셈 등 연산 줄어듦)	런타임 곱셈 필수로 약간 느릴 수 있음
코드 예시	int A[5][3]; 컴파일러가 상수 크기 활용	int A[n][n]; n이 함수 인자 등 런타임 값
주소 계산 어셈블리	leaq/shift/add 등 사용	imul(곱셈) 필수
포인터 최적화	한 번 계산한 후 포인터 증가만 반복	증가값(n)이 런타임 값이므로 곱셈 또는 누적 덧셈 사용
최적화 제한 요소	없음(정적 정보 풍부)	n값을 미리 알 수 없음
루프 종료 조건	포인터 비교로 간단히 처리 가능	루프 변수(j)와 n 비교 필요

간단 정리

• 고정 크기 배열:
  컴파일러가 상수값을 모두 알기 때문에, 인덱싱 연산을 “더하기/쉬프트”만으로 처리하거나, 반복문 전체를 포인터 이동만으로 바꿔서 매우 빠르고 효율적으로 최적화함. 반복문 풀기(loop unrolling) 같은 고급 최적화도 용이하다

• 가변 크기 배열(VLA):
  크기를 런타임에만 알 수 있으므로, 인덱싱에 “곱셈”이 꼭 들어가고, 반복문 최적화에 한계가 있음. 그래도 컴파일러가 패턴을 인식해 포인터 연산, 중복 곱셈 최소화 등 일부 최적화를 적용할 수 있다