발표 자료 — CS:APP 3.8.4~3.8.5 (249~253쪽) 정리

도입 (30초)

이번 발표는 **"컴파일러가 다차원 배열 인덱싱을 어떻게 최적화하는가"**에 대한 내용입니다. 핵심 질문은 하나예요 — 배열 원소에 접근할 때마다 매번 곱셈을 해야 할까? 결론부터 말하면, 컴파일러는 최대한 이 곱셈을 피하려고 합니다.

---

1. 고정크기 배열 (3.8.4절) — 2분

예제 설정

#define N 16
typedef int fix_matrix[N][N];

int fix_prod_ele(fix_matrix A, fix_matrix B, long i, long k) {
    long j;
    int result = 0;
    for (j = 0; j < N; j++)
        result += A[i][j] * B[j][k];
    return result;
}

→ 두 16×16 행렬을 곱했을 때, 결과의 (i,k) 위치 값을 구하는 함수입니다. 행렬 곱셈의 정의 그대로, A의 i행과 B의 k열을 내적합니다.

배열 주소 공식 (식 3.1)

&D[i][j] = xD + L(C·i + j)      # L=원소크기, C=열 개수

컴파일러의 최적화

원본 코드는 매번 j로 인덱싱하며 곱셈을 반복하지만, gcc는 이걸 **포인터 3개(Aptr, Bptr, Bend)**로 바꿔버립니다.

int *Aptr = &A[i][0];
int *Bptr = &B[0][k];
int *Bend = &B[N][k];
do {
    result += *Aptr * *Bptr;
    Aptr++;
    Bptr += N;
} while (Bptr != Bend);

왜 빨라지는가 — 핵심

• N=16이 컴파일 시점에 이미 알려진 상수이기 때문에, 주소 = xA + 64i 같은 계산에서 ×64를 **시프트 연산(salq $6)**으로 바꿀 수 있습니다.
• 루프 안에서는 곱셈 없이 덧셈만 반복합니다 (Aptr++, Bptr += 64).
• 정리: **"반복되는 곱셈 → 사전 계산 한 번 + 반복 덧셈"**으로 바꾸는 것 = 이번 절의 핵심 최적화 기법.

+ 응용 예제 (연습문제 3.40, 대각선 채우기)

for (i = 0; i < N; i++) A[i][i] = val;

대각선은 행과 열이 동시에 1씩 증가하므로, 포인터가 "N+1"칸(=68바이트)씩 건너뛰면 됩니다. 같은 원리의 변형일 뿐입니다.

---

2. 가변크기 배열 (3.8.5절) — 1.5분

배경: C99부터는 배열 크기를 변수로 선언할 수 있게 됐습니다.

int var_ele(long n, int A[n][n], long i, long j) {
    return A[i][j];
}

(주의: 크기 n이 반드시 배열보다 먼저 선언되어야 함 — 컴파일러가 차원을 미리 알아야 하므로)

고정크기 버전과의 결정적 차이

고정크기 (N=16) 가변크기 (n)

n·i 계산

salq $6 (시프트)

imulq (진짜 곱셈)

→ n이 실행 중에야 정해지는 값이라, 컴파일러가 "몇 비트 시프트할지"를 미리 알 수 없습니다. 그래서 곱셈을 피할 수 없습니다 — **"이 경우에는 어쩔 수 없다"**고 책도 명시합니다.

루프 최적화도 여전히 일부 적용됨

int *Arow = A[i];
int *Bptr = &B[0][k];
for (j = 0; j < n; j++) {
    result += Arow[j] * *Bptr;
    Bptr += n;
}

B는 포인터로 바뀌지만, A는 인덱스(Arow[j])를 그대로 유지 — 책은 이게 "필연적 차이가 아니라 컴파일러의 선택에 따른 결과일 뿐"이라고 설명합니다.

---

3. 결론 — 이 두 절을 관통하는 핵심 원리 (1분)

배열 인덱싱은 본질적으로 곱셈(식 3.1)이다. 하지만 같은 배열을 규칙적으로 반복 접근할 때는, 그 곱셈을 매번 새로 계산하지 않고 "이전 위치 + 고정 간격"이라는 덧셈으로 대체할 수 있다.

• 고정크기: 크기를 컴파일 시점에 아니까 → 곱셈 자체(×L, ×C)도 시프트로 바꿀 수 있어 가장 빠름
• 가변크기: 크기를 실행 시점에만 아니까 → 곱셈은 피할 수 없지만, 루프 안 반복 곱셈은 덧셈으로 대체 가능

결국 "배열 크기를 컴파일러가 얼마나 미리 알고 있느냐"가 최적화 수준을 결정한다는 것이 두 절의 핵심 메시지입니다.

---

발표용으로 슬라이드(PPT)나 문서 파일로 변환해드릴까요, 아니면 이 정리 그대로 참고하시면서 말로 발표하실 건가요?