WEEK 04 컴퓨터시스템 (C3-8)

3.8 배열의 할당과 접근

C에서 배열은 스칼라 데이터를 보다 큰 자료형으로 연계시키는 수단이다. 단순해 기계어로의 번역도 쉽다. 특이한 점은 배열 원소들에 대한 포인터를 만들고 이 포인터 간에 연산을 할 수 있다. 기계어에선 주소 계산으로 번역한다.

최적화 컴파일러는 배열의 인덱스를 사용할 때 필요한 주소계산을 단순화하는데 우수한 성능을 보인다. 그래서 C코드와 그 기계어 번역 간의 관계가 다소 어렵게 해석할 수 있다.

3.8.1기본 원리

자료형 T와 정수형 상수 N에 대해 다음과 같은 선언에 대해 생각해본다.

T A[N];

시작하는 위치를 xA(작은 A)로 표시하자. 이 선언은

1. L * N 바이트의 연속적인 공간을 메모리에 할당하며, L(바이트 단위)은 자료형 T의 크기를 나타낸다.
2. 위 선언문은 새로운 식별자 A를 통해 배열이 시작하는 위치의 포인터로 사용
   포인터의 값은 xA이고, 배열의 각 원소는 0에서 N - 1 사이의 정수형 인덱스를 사용해서 접근할 수 있다.

배열의 원소 i는 주소 xA + L * i에 저장된다.

char	A[12];
char	*B[8];
int		C[6];
double	*D[5];

이 선언문들은 다음과 같은 매개변수로 배열을 생성한다.

배열 A는 12개의 단일 바이트 char 원소로 구성된다. 배열 C는 각각 4바이트 필요로 하는 6개의 정수로 구성된다. 배열 B와 D는 모두 포인터의 배열로 배열의 원소는 각각 8바이트의 크기다.

x86-64의 메모리 참조 인스트럭션은 배열 접근을 간단히 할 수있게 설계됐다.
ex) E가 정수형 데이터 값들의 배열이고 E[i]를 계산하려 한다고 하다면,
E의 주소: %rdx, i: %rcx에 저장되어 있다. 그러면, 다음의 인스트럭션은 주소계산 xE + 4i를 수행하고 메모리 위치를 읽어서 그 결과를 레지스터 %eax에 저장한다.

movl (%rdx,%rcx,4),%eax

1, 2, 4, 8이 기본 자료형의 허용된 배율값 크기다.

3.8.2 포인터 연산

C 언어에서는 포인터에 대한 산술 연산이 가능합니다. 이때 연산 결과는 단순한 덧셈이 아닌, 데이터 타입의 크기에 맞춰 스케일 조정된 계산이 이루어집니다.
Ex) 포인터 p가 타입 T를 가리키고 있고, p의 주소값이 xp라면, p+i라는 표현은 xp + L * i를 의미합니다. 여기서 L은 타입 T의 크기(예: int이면 4바이트)입니다. 즉, p+i는 i번째 요소로 이동한 포인터 주소를 계산하는 방식입니다.

또한, 단항 연산자인 &(포인터 생성)와 *(역참조)는 포인터 생성과 역참조를 위해 사용됩니다. &Expr는 Expr이란 변수의 주소를 의미하고, *AExpr는 주소 AExpr에 저장된 값을 의미합니다. Expr와 *&Expr는 결과적으로 같은 값을 가리킵니다. 즉, 역참조와 주소 참조가 맞물려 상쇄됩니다.

배열은 포인터처럼 동작하기 때문에, 배열 인덱싱 연산자 []는 실제로 포인터 연산을 기반으로 동작합니다.
Ex) A[i]는 *(A+i)와 정확히 동일합니다. 이는 배열 A에서 i번째 요소의 주소를 계산한 뒤, 해당 메모리 위치에 접근하는 방식으로 처리됩니다.

예제를 통해 살펴보면, 정수형 배열 E의 시작 주소가 %rdx 레지스터에 저장되어 있고, 정수형 인덱스 i가 %rcx에 저장되어 있다고 가정했을 때, 다양한 C 표현식은 아래처럼 어셈블리로 변환될 수 있습니다. 데이터 값을 다룰 경우 %eax 레지스터에, 포인터(주소)를 다룰 경우 %rax 레지스터에 결과가 저장됩니다. 이처럼 C 코드의 포인터 및 배열 접근 방식은 어셈블리 코드에서의 주소 계산 방식과 정확히 일치하며, 컴파일러는 이를 기반으로 주소를 계산하고 메모리에 접근하는 명령어를 생성합니다.

→ 요약하면, C 언어에서 포인터 연산은 단순한 주소 연산이 아니라 자료형 크기를 고려한 계산이 들어가며, 배열 인덱스 접근 또한 포인터 산술과 동일한 방식으로 구현됩니다. 이런 동작 방식은 어셈블리 언어와 연결되어 있어, 어셈블리 수준에서 주소 계산과 메모리 접근이 어떻게 이루어지는지를 이해하는 데에도 중요한 역할을 합니다.

C 언어에서 배열 값을 반환하는 연산은 그 결과의 타입이 int이기 때문에, 어셈블리 코드에서는 4바이트 단위의 연산이 사용됩니다. 대표적으로 movl 명령어와 %eax 같은 32비트 레지스터가 사용됩니다.
반면, 포인터 값을 반환하는 연산은 결과 타입이 int *와 같은 포인터이므로, 8바이트 단위의 연산이 사용됩니다. 이때는 leaq 같은 명령어와 %rax 같은 64비트 레지스터가 사용됩니다.
이처럼 값을 직접 다루는지, 아니면 주소(포인터)를 다루는지에 따라 어셈블리 명령어와 사용하는 레지스터가 달라집니다.

마지막 예시에서 같은 자료구조 내에서 두 포인터 간의 차이를 계산 시, 이 연산의 결과는 long 타입의 값이 됩니다. 그 이유는, 포인터끼리의 차이는 단순히 주소 차이 그 자체가 아니라, 데이터 타입의 크기 단위로 나눈 차이이기 때문입니다.
Ex) int형(4바이트) 배열에서 두 포인터가 가리키는 주소 차이가 8바이트라면, 그 차이는 2(8 / sizeof(int))바이트로 계산됩니다. 이 연산은 컴파일러가 어셈블리 레벨에서 주소값을 뺀 후, 해당 타입의 크기(L)를 나누어 결과를 계산하는 방식으로 구현됩니다.

→ 포인터 간의 뺄셈은 단순 주소 차이가 아닌, "몇 개의 원소 차이인가?"를 구하는 연산으로, 이를 통해 C 언어는 배열에서 인덱스 기반 접근이나 거리 계산을 포인터 연산으로 처리할 수 있게 됩니다.

3.8.3 다중 배열

배열 할당과 참조에 관한 일반적인 원칙들은 배열의 배열을 생성할 때도 적용된다. 다음 선언문은

int A[5][3];

다음 선언문과 동일하다.

typedef int row3_t[3];
row3_t A[5];

자료형 row3_t는 세 정수의 배열로 정의된다. 배열 A는 다섯개의 배열을 원소로 가지고, 각각 세 개의 정수를 저장하기 위해 12바이트가 필요하다. 배열의 총 크기는 453 = 60 바이트이다. (int: 4바이트)

배열 A는 다섯 개의 행과 세 개의 열을 갖는 이차원 배열이다. A[0][0]에 서 A[4][2]까지 참조할 수 있다.
배열의 원소들은 메모리에 ‘행우선’ 순서로 저장된다. 이건 A[0]로 표시되는 모든 행 0의 원소들 다음에 행 1 (A[1])의 원소가 따라오는 방식으로 저장됨을 의미한다.

이 저장 순서는 우리가 사용한 다중 선언의 결과이다.
A를 다섯 개의 원소를 갖는 배열로 보면, 각각은 세 개의 정수들의 배열로 먼저 A[0], A[1]이 따라오는 방식이다.

다차원 배열의 원소를 접근하기 위해서 컴파일러는

1. 원하는 원소의 오프셋을 계산하는 코드를 생성
2. 배열의 시작을 기본 주소로, 오프셋을 인덱스(배율 적용 가능)로 하는 MOV 인스트럭션을 사용

T D[R][C];

일반적으로 다음과 같이 선언된 배열에 대해(수식3.1)

&D[ i ][ j ]=xD+L(C⋅i+j)

→ 배열 원소 D[i][j]는 메모리 주소

다음과 같이 위치한다. L은 자료형 T의 바이트 크기이다.

Ex) 앞에서 정의한 5 * 3 정수 배열 A를 생각해보자. xA, i, j는 %ebp 레지스터 %rdi, %rsi, %rdx에 각각 위치한다고 가정시, 배열의 원소 A[i][j]는 레지스터 %eax에 다음과 같은 코드에 의해 복사될 수 있다.

	A in %rdi, i in %rsi, and j in %rdx
1	leaq	(%rsi,%rsi,2), %rax		Compute 3i
2	leaq	(%rdi,%rax,4), %rax		Compute xA + 12i
3	movl	(%rax,%rdx,4), %eax		Read from M[xA + 12i + 4]

위처럼 코드는 원소의 주소를 x86-64 주소연산의 덧셈과 배율을 사용해서 xA + 12i + 4j = xA + 4(3i + j)형태로 계산한다.

3.8.4 고정크기의 배열

C컴파일러는 고정 크기의 다차원 배열을 위한 코드에 대해 다양한 최적화를 수행할 수 있다.
이번엔 최적화 수준이 -01로 설정했을 시 GCC가 수행하는 몇 가지 최적화를 설명한다.

Ex) 자료형 fix_matrix를 다음과 같이 16 x 16 정수 배열로 선언했다고하면:

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

(이 예제는 좋다, 프로그램이 배열의 차원이나 버퍼의 크기로 상수를 사용할 때, 매번 숫자를 사용하는 것보다 #define 선언을 통해 변수명과 숫자를 연관지어 일괄적으로 변수명을 사용하는 것이 가장 좋다. 이 방식으로 값을 바꿔야하는 경우에도 #define 선언만 간단히 수정하면 된다.)

[최초의 코드]

/* Compute i,k of fixed matrix product */
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와 B의 곱을 계산하는데, 그 중 A의 i번째 행과 B의 k번째 열을 내적(inner product)하여 결과 배열의 i, k번째 원소를 구합니다. 이 계산은 아래 수식으로 표현됩니다:

97fe2-848e-4eee-ace1-4051764d4490:스크린샷_2025-04-07_21.36.48.png)

즉, j를 0부터 N-1까지 반복하면서, A의 i번째 행의 j번째 값과 B의 j번째 행의 k번째 값을 곱하고 그 결과를 모두 더하는 구조입니다.

이 연산에 대해 GCC 컴파일러는 최적화된 어셈블리 코드를 생성하며, 이 코드를 사람이 이해하기 쉬운 C 코드로 다시 표현한 것이 아래의 fix_prod_ele_opt 함수입니다. 이 코드에는 다음과 같은 똑똑한 최적화 기법들이 포함되어 있습니다:

[위의 코드를 최적화한 코드]

1	/* Compute i,k of fixed matrix product */
2	int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
3		int *Aptr = &A[i][0];	      /* Points to elements in row i of A		*/
4		int *Bptr = &B[0][k];	      /* Points to elements in column k of B	*/
5		int *Bend = &B[N][k];	      /* Marks stopping point for Bptr		*/
6		int result = 0;
7		do {					              /* No need for initial test */
8			result += *Aptr * *Bptr;	/* Add next product to sum */
9			Aptr ++;			            /* Move Aptr to next column */
10			Bptr += N;			        /* Move Bptr to next row */
11		} while (Bptr != Bend);		/* Test for stopping point */
12		return result;
13	}

주요 최적화 포인트 정리

1. 인덱스 변수 j 제거

   반복문에서 j라는 정수 인덱스를 아예 사용하지 않고, 대신 포인터 연산으로 반복을 제어합니다. 이는 계산 속도를 높이고 불필요한 인덱스 접근을 줄이는 방식입니다.

2. 포인터를 이용한 배열 접근

   배열 접근을 포인터 기반으로 변환하여 성능을 최적화합니다:

   • Aptr: 배열 A의 i번째 행의 각 원소를 순차적으로 가리키는 포인터입니다. 시작 위치는 &A[i][0].
   • Bptr: 배열 B의 k번째 열의 각 원소를 순차적으로 가리키는 포인터입니다. 시작 위치는 &B[0][k]. 다만, 이건 열 단위로 접근해야 하므로, 행을 기준으로 이동하며 B의 k번째 열을 접근합니다.
   • Bend: 반복문이 종료되어야 할 시점의 Bptr 값입니다. 즉, B의 마지막 열 원소를 넘어서는 주소를 의미하며 반복 조건 체크에 사용됩니다.

3. 포인터 증가 방식으로 루프 제어

   반복문 안에서는 Aptr을 1칸씩 증가시키고, Bptr은 배열 B의 행 수에 따라 B + L만큼 건너뛰며 열의 다음 원소를 접근합니다. 즉, 포인터 연산을 통해 B[j][k]를 효율적으로 참조합니다.

→ 결국 이 최적화된 코드는 명시적인 인덱스 없이 A[i][j] * B[j][k]를 수행하는데 필요한 각 원소를 포인터를 통해 직접 순차적으로 접근합니다. 그 덕분에 반복문은 훨씬 간결하고 빠르게 동작하게 되며, C의 저수준 특징을 잘 활용한 구조라 할 수 있습니다. 특히 B의 열 접근을 위한 Bptr 처리 방식은 매우 인상적인 부분으로, 실제 어셈블리나 성능 최적화 상황에서 자주 활용됩니다.

3.8.5 가변크기 배열

역사적으로 C에서 컴파일 시에 그 크기가 결정될 수 있는 다차원 배열만을 지원해왔다.(첫 차원은 예외있음)
가변크기 배열을 원하는 프로그래머는 배열들을 위한 저장공간을 malloc이나 calloc 같은 함수를 사용해서 할당해야 했고, 다차원 배열을 1차원 배열들로 행-우선 인덱싱을 사용해서 명시적으로 변환해야 했다. ISO C99에선 배열의 차원을 배열이 할당될 때 계산될 수 있는 수식으로 할 수 있는 방법을 제안했다.
C에서는 가변크기 배열을

int A[expr1] [expr2]

로 지역변수나 함수의 인자로 선언 가능하다. 배열의 차원은 선언 부분을 만날 때 수식 expr1과 expr2를 계산해서 결정된다.
Ex) n x n 배열의 i, j 원소에 접근하는 함수를 다음과 같이 작성 가능하다.

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

매개변수 n은 반드시 매개변수 A[n][n]보다 먼저 나와야한다. 그래서 함수가 매개변수를 만날 때 배열의 차원을 계산할 수 있다.
GCC는 이 역참조 함수에 대한 코드를 다음과 같이 생성한다.

  int var_ele(long n, int A[n][n], long i, long j)
	n in %rdi, A in %rsi, i in %rdx, j in %rcx
1	var_ele:
2		imulq	%rdx, %rdi			Compute n · i
3		leaq	(%rsi,%rdi,4), %rax		Compute xA + 4(n · i
4		movl	(%rax,%rcx,4), %eax		Read from M[xA + 4(n · i) + 4j]
5		ret

해당 어셈블리 주석에 따르면, 이 코드는 2차원 배열 A의 i, j 위치 원소의 주소를 다음과 같은 방식으로 계산합니다.

여기서 x_A는 배열 A의 시작 주소이고, n은 배열의 열 크기, 즉 한 행당 원소 개수입니다. 각 정수형 원소는 4바이트이기 때문에, 인덱스를 4배하여 실제 주소를 계산합니다.

이 주소 계산은 고정 크기 배열의 경우와 매우 비슷합니다. 그러나 몇 가지 차이점이 있습니다.

• 추가된 매개변수 n에 따른 레지스터 사용 변화 고정 크기 배열은 컴파일 타임에 행의 크기가 고정되지만, 여기서는 행 크기 n이 함수 인자로 주어지므로 그에 따라 추가 레지스터를 사용해야 합니다.
  
• 곱셈 명령어(MUL) 사용 n * i를 계산하기 위해 단순한 시프트와 덧셈(예: leag로 3i 계산)이 아니라, 진짜 곱셈 명령어(MUL)를 사용합니다. 곱셈은 일부 프로세서에서 연산 비용이 크기 때문에 성능에 영향을 줄 수 있습니다. 하지만 가변 크기 배열에서는 이 곱셈이 불가피합니다.
  

[반복문에서 최적화]

이러한 곱셈 연산은 성능 저하를 유발할 수 있지만, 컴파일러는 반복문 내부에서 발생하는 규칙적인 배열 접근 패턴을 활용하여 이를 최적화할 수 있습니다.

Ex)

• Figure 3.38(a)에서는 두 개의 n x n 배열 A와 B에 대해, A의 i번째 행과 B의 k번째 열을 곱하여 i, k번째 결과를 계산하는 코드가 있습니다. 이는 행렬 곱의 일부입니다.
• GCC 컴파일러는 이 코드를 어셈블리로 변환한 후, 사람이 읽을 수 있도록 C 코드로 다시 표현한 것이 Figure 3.38(b)입니다.

최적화 코드의 스타일 차이
이전의 고정 배열 최적화 코드와 달리, 여기의 최적화된 코드는 아직도 인덱스 변수 j를 유지합니다. 이는 루프 종료 조건을 판단하기 위한 용도이며, 컴파일러가 어떤 방식의 최적화를 선택했느냐에 따른 차이지, 고정 배열과 가변 배열 간의 필수적인 차이는 아닙니다.

즉, 포인터 기반 접근과 인덱스 기반 접근은 모두 사용 가능하며, 이는 컴파일러의 전략에 따라 달라질 수 있다는 것이 핵심입니다.

→ 가변 크기 배열 요약

• 가변 크기 배열을 참조할 때는 n * i + j 형태의 인덱스를 사용하며, 이때 곱셈 연산이 필수입니다.
• 고정 배열보다 약간 더 일반화된 방식일 뿐, 구조적으로는 큰 차이가 없습니다.
• 반복문 내부에서는 컴파일러가 정규적인 접근 패턴을 기반으로 계산을 최적화할 수 있으며, 인덱스를 유지할 수도, 포인터로 바꿀 수도 있습니다.
• 결과적으로, 가변 배열도 효율적으로 다룰 수 있도록 컴파일러가 다양한 최적화 기법을 적용할 수 있습니다.

(a)초기의 C 코드

1	/* Compute i,k of variable matrix product */
2	int var_prod_ele(long n, int A[n][n], int B[n][n], long i, long k) {
3		long j;
4		int result = 0;
5
6		for (j = 0; j < n; j++)
7			result += A[i][j] * B[j][k];
8
9		return result;
10	}

(b)최적화된 C코드

/* Compute i,k of variable matrix product */
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;
}

위는 가변크기 배열에 대한 행렬 곱셈의 원소 i, k를 계산하기 위한 초기 코드와 최적화된 코드이다. 컴파일러가 해당 최적화를 자동으로 실행한다.

다음은 var_prod_ele 루프에 대한 어셈블리 코드이다.

	Registers: n in %rdi, Arow in %rsi, Bptr in %rcx
	4n in %r9, result in %eax, j in %edx
1	.L24:				loop:
2	movl	(%rsi,%rdx,4), %r8d	Read Arow[j]
3	imull	(%rcx), %r8d		Multiply by *Bptr
4	addl	%r8d, %eax		Add to result
5	addq	$1, %rdx		j++
6	addq	%r9, %rcx		Bptr += n
7	cmpq	%rdi, %rdx		Compare j:n
8	jne	.L24			If !=, goto loop

이 프로그램에서는 확장된 값 4n(레지스터 %r9)을 Bptr을 증가시키는 데 사용하고 n의 값(레지스터 %rdi)는 루프의 경계를 체크하기 위해 사용한다.
두 값이 왜 필요한지는 포인터 산술연산자의 배율 때문에 이 C코드에선 드러나지 않는다.

최적화를 활성화하여 GCC가 프로그램이 다중 배열의 원소들을 접근할 때 발생하는 패턴을 인식할 수 있다는 것을 알수 있다. 컴파일러는 수식

&D[ i ][ j ]=xD+L(C⋅i+j)  

을 응용해서 발생했을 곱셈을 회피하는 코드를 생성할 수 있다. 위 최적화된 C코드에서 포인터 기반 코드를 생성하던, 배열기반 코드를 생성하던, 이 최적화들은 프로그램 성능을 개선하게 된다.