Array and Struct

상위 문서: Assembly

개요

해당 문서에서는 1차원 배열(array)와, 다차원 배열, 그리고 포인터 배열의 특성에 대해 다룬다. 또한 구조체(struct)를 선언할 때, 구조체가 메모리에 어떻게 배치되는지와 정렬 및 패딩(padding) 규칙이 구조체에 어떤 영향을 미치는지에 대해 다룬다.

Array

C에서는 기본적으로 아래와 같이 배열을 선언한다:

T A[N];

Figure 1. Array allocation example

T는 배열의 원소(element)의 자료형, N는 배열에 최대로 저장될 수 있는 원소의 수에 해당한다. 위 명령어를 통해 총 N * sizeof(T) 바이트의 연속적인 메모리 할당이 이뤄진다. 예를 들어, char *p[3];와 같은 명령어는 포인터 자료형의 크기가 8바이트이므로, 총 24바이트의 공간이 할당된다. 이는 figure 1이 잘 보여준다.

Array Access

기본적으로 배열 이름 A는 배열의 첫 원소의 시작 주소를 지정하는 포인터처럼 작동한다. 예를 들어, 배열 val이 figure 2와 같이 선언되었을 때, 배열 이름 val에 대한 산술 연산은 아래와 같이 작동한다.

Figure 2. Array access example

Expression	Type	Value
val	int*	x
&val[1] or val + 1	int*	x + 1 * 4
val[1] or *(val + 1)	int	5
&val[i] or val + i	int*	x + i * 4

아래는 배열의 원소에 접근하는 C언어 기반의 함수와, 동일한 작업을 수행하는 어셈블리 코드이다.

int get_elem(int* arr, long idx) {
  return arr[idx];
}

get_elem:
  mov (%rdi,%rsi,4), %eax
  ret

위 어셈블리 코드에서 %rdi는 배열의 시작 주소를 의미하며, %rsi는 인덱스를 의미한다. 따라서, arr[idx]는 %rdi + 4 * %rsi에 위치한 원소이다.

Array vs. Pointer in C

배열과 포인터는 밀접한 관계가 있지만, 동일하지 않다. char str1[32];과 같이 배열 이름은 포인터처럼 사용될 수 있지만, 진짜 포인터 변수는 아니다. 이는 아래의 예시 코드를 통해서 알아볼 수 있다.

char str1[32];
char str2[64];
char *p = str1;
printf("%p vs. %p\n", str1, p); 
printf("sizeof(str1) = %ld\n", sizeof(str1)); // 배열의 크기 = 32 
printf("sizeof(p) = %ld\n", sizeof(p)); //포인터 크기 = 8
p = str2; //char* 포인터에 배열 이름 할당은 괜찮음
str2 = p; //이는 컴파일 오류를 야기

위의 코드에서는 마지막 줄이 컴파일 오류를 야기한다. 이는 배열 이름은 사실상 상수와 같이 동작하므로, 재할당이 불가하기 때문이다. 하지만 그 외에는 사실상 포인터와 같이 동작하므로, 서로 호환되어 사용되는 것을 보여준다.

Multi-dimensional (2D) Array

C에서는 다음과 같이 2차원 배열을 선언한다:

T A[N][M];

이는 N행 M열의 2차원 배열을 선언하고, 선언된 배열의 메모리 크기는 N * M * sizeof(T)이다. 이때 C언어는 row-major order를 사용하여 이차원 배열의 각 원소들을 저장한다. Row-major order란 같은 행의 원소들이 메모리 상에서 연속적으로 저장되는 것을 의미한다. 예를 들어, 아래와 같이 배열이 주어져있다고 가정하자.

Figure 3. 2D Array: Array of Array

int val[4][5] = {
  {9, 8, 1, 9, 5},
  {9, 8, 1, 0, 5},
  {9, 8, 1, 0, 3},
  {9, 8, 1, 1, 5}
};

위의 배열은 row-major order 기준으로 각 행에 연속적으로 20바이트를 할당한다. 배열이 메모리에 할당된 모습은 figure 3에 잘 나타나있다. i 2차원 배열은 배열의 배열이라고 할 수 있다. 이에 따라, A[i]는 i번째 행(배열)의 시작 주소를 의미한다. 따라서 A[i]가 가리키는 주소는 A[i] = A + i * (M * sizeof(T))와 같이 계산된다.

Access in 2D Array

아래는 2차원 배열의 행에 접근하는 C언어, 어셈블리 코드이다:

int* get_row(int arr[][5], int row_idx) {
    return arr[row_idx];
}

movslq %esi, %rsi          ; row_idx를 64비트로 확장 //x86-64에서, 주소 계산은 64비트로 이루어져야 함
lea (%rsi, %rsi, 4), %rax  ; %rsi * 5 → 5 * row_idx
lea (%rdi, %rax, 4), %rax  ; 최종 주소 = arr + 20 * row_idx
ret

위 어셈블리 코드의 핵심 구현 사항은 get_row() 함수가 arr + 20 * row_idx에 해당하는 주솟값을 리턴해야 한다는 것이다. 이를 위해서 %rax에 행의 크기(20)를 저장한 다음, 이에 row_idx를 곱하여 최종 주솟값을 구한다. 또한, 아래는 2차원 배열에서의 원소에 접근하는 C언어와 어셈블리 코드이다:

int get_elem(int arr[][5], int row_idx, int col_idx) {
    return arr[row_idx][col_idx]; //arr + 20 * row_idx + 4 * col_idx
}

movslq %esi, %rsi           ; row_idx → 64비트
movslq %edx, %rdx           ; col_idx → 64비트
lea (%rsi,%rsi,4), %rax     ; 5 * row_idx
lea (%rdi,%rax,4), %rax     ; 행의 시작 주소
mov (%rax,%rdx,4), %eax     ; 열 오프셋 더해서 메모리 로드
ret

2차원 배열의 어떤 원소에 접근하기 위해서는, 해당 원소의 주솟값을 arr + 20 * row_idx + 4 * col_idx과 같이 계산해야 한다. 이를 위해 col_idx를 %rdx에 저장한 후, 이를 이용해 최종적인 주솟값을 계산한다. 따라서, 임의의 N * M인 2차원 배열 A가 주어졌을 때, A[n][m]에 해당하는 원소의 주솟값은 A + (M * size * n) + (size * m)와 같이 주어진다.

Array of Pointer

2차원 배열과 포인터 배열은 아래의 간단한 예시를 통해 알아 볼 수 있다:

int univ[3][5] = {
  {1, 5, 2, 8, 9},
  {9, 4, 7, 2, 0},
  {0, 4, 1, 0, 7}
};

int cmu[5] = {1, 5, 2, 8, 9};
int ucb[5] = {9, 4, 7, 2, 0};
int sgu[5] = {0, 4, 1, 0, 7};
int* univ[3] = {cmu, ucb, sgu};

위 예시의 두 번째 코드에는 포인터 배열이 잘 나타나있다. 해당 코드에서 정의된 univ 배열은 3개의 포인터를 저장하고 있으며, 각각 cmu, ucb, sgu라는 세개의 별도 배열을 저장하고 있다. 이때 2차원 배열과의 차이점은, 해당 별도 배열들이 비연속적이며 독립적으로 할당되었다는 것이다. 아래는 포인터의 배열의 어떤 원소를 접근하기 위한 C와, 어셈블리 코드이다.

int get_elem(int* arr[], int ptr_idx, int int_idx) {
  return arr[ptr_idx][int_idx];
}

movslq %esi, %rsi             ; ptr_idx
mov (%rdi,%rsi,8), %rax       ; arr[ptr_idx] → 배열의 포인터
movslq %edx, %rdx             ; int_idx
mov (%rax,%rdx,4), %eax       ; 배열의 요소 접근 
ret

C의 코드는 arr[ptr_idx]를 통해서 별도의 배열 포인터에 접근한 뒤, int_idx를 통해서 특정 원소에 접근한다. 이는 어셈블리 코드에도 정확하게 구현되어 있으며, 결과적으로 *(*(arr + 8 × ptr_idx) + 4 × int_idx)에 해당하는 주솟값에 접근한다. Figure 4는 해당 구조를 잘 보여준다. 아래 표는 2차원 배열과, 포인터 배열 간의 차이를 보여준다:

항목	2차원 배열	포인터 배열
선언	int arr[3][5]	int* arr[3]
메모리 구조	연속된 메모리 블록	각각 독립된 블록을 가리킴
접근 계산식	arr + 20×row + 4×col	*(arr + 8×ptr) + 4×int
어셈블리 복잡도	비교적 단순	2번 메모리 접근 필요
유연성	크기 고정	크기 다양 / 동적 할당 가능

즉, C 코드로는 arr[i][j]가 같아 보여도, 내부적으로는 전혀 다른 방식으로 동작한다.