컴퓨터 시스템 : CSAPP 3장 정리 - 3.8 배열의 할당과 접근 Part.2

크래프톤 정글 (컴퓨터 시스템: CSAPP)/3장 프로그램의 기계수준 표현

컴퓨터 시스템 : CSAPP 3장 정리 - 3.8 배열의 할당과 접근 Part.2

고웅 2025. 4. 6. 09:49

🔍 지금까지의 요약

🔹 3.8 도입: 배열과 주소 계산

C 언어에서 배열은 연속적인 메모리 공간에 할당됨.
배열 이름은 배열 시작 주소(포인터)처럼 동작.
A[i]는 실제로 *(A + i)로 처리되며, 주소 계산은 xA + L*i로 단순화됨.
이 단순한 구조는 어셈블리 주소 계산 명령어(D(Rb, Ri, S))와 자연스럽게 매핑됨.

🔹 3.8.1 기본 원리 (Basic Principles)

T A[N] 형태의 배열은 총 N * L 바이트를 연속적으로 할당.
각 배열 요소 A[i]의 주소는 xA + i * L로 계산됨.
배열 인덱싱은 어셈블리에서 스케일 인덱스를 활용한 주소 계산으로 구현됨 (예: movl (%rdx,%rcx,4), %eax).

🔹 3.8.2 포인터 연산 (Pointer Arithmetic)

포인터 연산은 배열 인덱싱과 동일하게 작동함:
- A[i] ≡ *(A + i)
포인터 연산 시 컴파일러는 자료형 크기에 맞춰 자동 스케일링을 수행.
다양한 포인터 관련 표현(*(E+i-3), &E[i])도 어셈블리에서 효율적으로 번역됨.
이로 인해 포인터 기반 접근이 배열 인덱싱보다 더 유연하게 사용될 수 있음.

🔹 3.8.3 중첩 배열 (Nested Arrays)

다차원 배열은 C에서 배열의 배열로 정의됨 (int A[5][3] → 5개의 3-원소 int 배열).
메모리는 행 우선(row-major) 순서로 배치됨.
접근 주소는 &A[i][j] = xA + L(C * i + j)로 계산됨.
이 접근 방식은 어셈블리에서 복잡한 다차원 배열 접근도 단순한 선형 주소 계산으로 처리할 수 있게 해 줌.

🔷 3.8.4 고정 크기 배열 (Fixed-Size Arrays)

이 절은 고정 크기의 다차원 배열을 사용할 때 컴파일러가 어떻게 최적화할 수 있는지를 설명한다. 특히 배열 곱셈 연산처럼 반복적으로 인덱싱이 필요한 작업에서 컴파일러가 인덱스 계산을 줄이기 위해 어떤 최적화를 하는지를 예시를 통해 보여준다.

📌 전제: fix_matrix 타입

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

고정 크기: 16 × 16 정수형 배열
각 배열은 256개의 int 요소를 가지며, 총 1024바이트 크기

🔍 예제 함수: 행렬 곱셈 원소 계산

(a) 원래 코드

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;
}

A[i]의 행과 B[k]의 열 간 내적(inner product)을 계산하는 함수이다.

💡 최적화 포인트: 인덱스 계산 제거

GCC 최적화(-O1) 결과로 인덱스 대신 포인터 연산 기반 코드로 변환된다.

(b) 최적화된 코드

int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
    int *Aptr = &A[i][0];       // A의 i번째 행 시작 주소
    int *Bptr = &B[0][k];       // B의 k번째 열 시작 주소
    int *Bend = &B[N][k];       // 종료 조건
    int result = 0;

    while (Bptr != Bend) {
        result += *Aptr * *Bptr;
        Aptr++;
        Bptr += N;
    }
    return result;
}

📐 최적화 방식 설명

Aptr는 A[i] 행의 첫 번째 원소 주소부터 순차적으로 이동
Bptr는 B[0][k], B[1][k], ..., B[N-1][k] 식으로 열 방향으로 이동 (한 번에 N씩 증가)
인덱스 변수 j 제거 → 곱셈과 덧셈만으로 반복 수행
루프 종료 조건은 Bptr == Bend로 판단

이 방식은 반복마다 j*N + k 주소를 계산하지 않고, 포인터 자체를 이동시킴으로써 성능을 크게 개선한다.

🧾 어셈블리 코드 분석 (주요 부분)

fix_prod_ele_opt:
    leaq    0(,%rsi,8), %rax         ; %rax = i * 8
    leaq    (%rdi,%rax,2), %rcx     ; %rcx = &A[i][0]
    leaq    (%rdx,%rsi,4), %rsi     ; %rsi = &B[0][k]
    leaq    1024(%rdx,%rsi), %rdx   ; %rdx = &B[N][k]
    movl    $0, %eax                ; result = 0
.L3:
    cmpl    %rdx, %rsi              ; Bptr == Bend ?
    je      .L5                     ; 종료 조건
    movl    (%rcx), %r8d            ; *Aptr → %r8d
    imull   (%rsi), %r8d            ; *Bptr * *Aptr
    addl    %r8d, %eax              ; result += ...
    addq    $4, %rcx                ; Aptr++
    addq    $64, %rsi               ; Bptr += 16 * 4 = 64
    jmp     .L3                     ; 루프 반복
.L5:
    ret

🔍 단계별 설명

leaq 0(,%rsi,8), %rax
leaq (%rdi,%rax,2), %rcx

1. 초기 주소 계산

%rsi = i, %rdi = A
%rax = i * 8
%rcx = A + (i * 8 * 2) = A + i * 16 → &A[i][0] 주소 계산 (A는 16열짜리 행렬이므로 각 행은 64바이트)

2. B 열 주소 계산

leaq (%rdx,%rsi,4), %rsi
leaq 1024(%rdx,%rsi), %rdx

%rdx = B, %rsi = k
%rsi = &B[0][k] (각 행의 간격이 64바이트 → 다음 줄에서는 이를 활용해 Bptr += 64)
%rdx = &B[N][k] = 종료 주소 Bend

3. 루프 본문

movl    (%rcx), %r8d          ; *Aptr
imull   (%rsi), %r8d          ; *Bptr * *Aptr
addl    %r8d, %eax            ; result += ...
addq    $4, %rcx              ; Aptr++
addq    $64, %rsi             ; Bptr += N * 4 = 64

각 반복마다 Aptr은 +4, Bptr은 +64 (다음 행의 같은 열)

4. 종료 조건 검사

cmpl    %rdx, %rsi
je      .L5

Bptr와 Bend 비교 → 같으면 종료

✅ 요약

고정 크기 배열은 컴파일 타임에 배열 크기가 확정되므로 다양한 최적화 가능
대표적 최적화: 포인터를 이용한 반복, 인덱스 제거, 상수 주소 계산
컴파일러는 이를 통해 인덱스 연산을 메모리 접근보다 빠른 연산으로 대체함

🔷 3.8.5 가변 크기 배열 (Variable-Size Arrays)

📌 배경: 고정 크기 배열의 한계

전통적인 C에서는 컴파일 타임에 배열 크기가 결정되어야 했다. 즉, 다차원 배열에서 첫 번째 차원을 제외한 나머지 차원은 정적으로 알려져 있어야 했다. 만약 크기가 가변적인 배열이 필요하다면, malloc 또는 calloc 같은 힙 할당 함수와 수동적인 주소 계산이 필요했다.

💡 ISO C99: 가변 크기 배열(VLA) 도입

ISO C99 표준에서는 함수 인자나 지역 변수로서 가변 크기의 배열 선언을 허용한다. 예:

int A[expr1][expr2];  // expr1과 expr2는 런타임에 계산되는 표현식

함수 인자에서 사용할 경우, 반드시 배열 크기를 지정하는 인자가 앞서 정의되어 있어야 한다.

예제 함수

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

n: 배열 차원을 동적으로 결정하기 위한 인자
A: n × n 가변 배열
A[i][j]: 표준적인 2차원 배열 접근

🧾 어셈블리 코드 분석

var_ele:
  imulq %rdx, %rdi           ; %rdi = n × i
  leaq (%rsi,%rdi,4), %rax   ; %rax = xA + 4(n × i)
  movl (%rax,%rcx,4), %eax   ; A[i][j] = *(xA + 4(n×i + j))
  ret

설명:

%rdi = n, %rsi = A, %rdx = i, %rcx = j
imulq로 n * i 연산 수행 (동적 크기이므로 leaq가 아닌 imul 사용)
주소 계산은: xA + 4(n * i + j)

고정 크기 배열과의 차이점:

고정 크기 배열에서는 leaq로 주소 계산 최적화 가능 (곱셈 대신 shift & add)
가변 배열은 imul 명령어 필요 → 약간의 성능 저하 가능

🔄 루프 최적화 예시

원래 코드 (행렬 곱)

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

최적화된 코드

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

A[i]는 포인터이므로 한 줄을 바로 참조 가능
Bptr는 k열을 순차적으로 접근하며 +n씩 이동
j는 인덱스로 유지되며 종료 조건 판단에 사용됨

✅ 요약

가변 크기 배열은 런타임에 크기가 결정되는 배열이며, n 등의 인자를 통해 정의됨
주소 계산은 고정 배열과 유사하지만, 동적 크기 때문에 곱셈 연산 필요
컴파일러는 반복 패턴을 인식해 포인터 기반 접근 등 최적화 수행 가능
C99의 기능을 활용하면, 유연하고 효율적인 배열 처리가 가능함

✅ 3.8 배열의 할당과 접근 — 전체 요약

🔹 배열이란?

C 언어에서 배열은 연속된 메모리 공간에 저장된 동일 타입의 데이터 집합
배열 이름은 해당 배열의 **시작 주소(포인터)**로 해석됨
인덱스 접근 A[i]는 주소 xA + i * L로 해석되며, 이는 어셈블리에서 효율적인 주소 계산으로 구현됨

🔸 3.8.1 기본 원리

T A[N] → 총 N * L 바이트의 연속 메모리 할당
어셈블리에서 mov (%base,%index,scale) 형태로 배열 요소 접근
주소 연산은 매우 단순하며, 자료형 크기(L)에 따라 자동 스케일링

🔸 3.8.2 포인터 연산

배열 인덱싱 A[i]는 *(A + i)로 해석 가능
포인터 연산은 인덱스와 동일한 주소 계산을 따름
포인터와 배열은 동일한 원리로 작동하며, 어셈블리에서도 동일하게 번역됨

🔸 3.8.3 중첩 배열 (다차원 배열)

2차원 배열 T A[R][C]은 배열의 배열 구조
메모리는 행 우선(row-major) 순서로 배치
A[i][j] → 주소 계산: xA + L*(C*i + j)
어셈블리는 곱셈 및 덧셈 조합으로 주소 계산 수행

🔸 3.8.4 고정 크기 배열

배열 크기가 고정되어 있으면, 컴파일러는 인덱스 연산을 포인터 기반 반복으로 최적화 가능
반복문 내에서 인덱스 계산을 제거하고, Aptr++, Bptr += N처럼 포인터를 이동시킴
성능 개선에 큰 효과가 있음

🔸 3.8.5 가변 크기 배열 (VLA)

C99부터 런타임에서 크기를 지정할 수 있는 배열이 도입됨
int A[n][n]처럼 n이 인자로 전달되어 배열 크기를 동적으로 정의
주소 계산은 여전히 L*(n*i + j)지만, n이 상수가 아니므로 imul 같은 곱셈 명령어 필요
포인터 기반 최적화도 여전히 가능함

🧠 전체 통합 메시지

"C의 배열은 고정 크기, 포인터 연산, 다차원 구조, 동적 크기 배열까지 모두 단순하고 일관된 주소 계산 방식으로 처리되며, 이는 어셈블리 수준에서 매우 효율적인 구현을 가능하게 한다. 컴파일러는 이를 활용해 다양한 최적화 전략을 적용할 수 있다."

저작자표시 동일조건