Array and Struct

상위 문서: Memory

개요

해당 문서에서는 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차원 배열과, 포인터 배열 간의 차이를 보여준다:

Figure 4. Array of Pointer: Element Access

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

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

Struct

구조체는 여러 개의 변수(필드)를 하나로 묶은 복합 자료형이다. 이때 struct 정의 자체는 변수를 따로 생성하지 않으며, 변수 선언을 따로 필요로 하며 구조체가 정의되면 일반 변수처럼 사용될 수 있다. 아래는 예시 구조체 node의 정의이다:

struct node {
    int a[4];           // 4 * 4 = 16 bytes
    long l;             // 8 bytes (offset 16)
    struct node *next;  // 8 bytes (offset 24)
};

Figure 5. Structure Representation

위 구조체는 32바이트로 구성되며, figure 5와 같이 저장된다. 이때 필드는, 선언 순서에 따라 저장된다:

• a[4] → offset 0
• l → offset 16
• next → offset 24

구조체는 메모리 블록으로 표현되며, 각 필드는 구조체 내에서 오프셋(offset)을 통해 접근한다. 또한 컴파일러가 구조체의 크기와 padding을 자동으로 결정한다. 아래는 linked list 내의 원소를 확인하는 C언어와 어셈블리어를 이용한 코드이다.

void set(struct node *n, int v, int idx) {
    while (n) {
        n->a[idx] = v; //포인터를 통해 필드에 접근 시 '.'을 사용한다.
        n = n->next;
    }
}

0x401108: movslq %edx,%rax        ; idx를 64비트로 확장 → %rax
0x40110b: mov %esi,(%rdi,%rax,4)  ; n->a[idx] = v
0x40110e: mov 0x18(%rdi),%rdi     ; n = n->next (offset 24)
0x401112: test %rdi,%rdi          ; n != NULL ?
0x401115: jne 0x401108            ; 반복

위 어셈블리 코드에서는, 구조체 내의 필드에 오프셋을 이용하여 접근하는 것을 볼 수 있다. 구조체 내의 배열 a에 접근할 때에는 (%rdi + 4 * idx)을 통해서 오프셋 0을 활용하며, next 필드에 접근할 때는 0x18(%rdi)을 통해 오프셋 24를 활용한다.

Alignment of Structure

Figure 6. Unalignment example

정렬(Alignment)란, 데이터가 올바른 주소에 배치되는지를 의미한다. 이때 정렬된 상태란, K바이트 자료형의 값이 K의 배수인 주소값에 위치하는 것을 의미한다. 예를 들어, int(4 바이트) 자료형 변수는 4의 배수로 시작하는 주소에 위치해야 성능적으로 좋다. 이는 하드웨어가 메모리를 word 단위(예: 8바이트)로 접근하며, 데이터를 여러 word에 걸쳐 저장하면 성능 저하나 오류가 발생할 수 있기 때문이다. 예를 들어 figure 6에서는 주소 1006에서 int 변수가 시작하므로, 두 word를 걸치게 되어 unaligned 상태가 된다.

이를 바탕으로 구조체를 정렬하는 규칙을 만들면 아래와 같다:

1. 구조체 내부의 각 필드는 자신의 필드 크기를 기준으로 정렬되어야 한다.
2. 구조체 전체의 시작/끝 주소도 구조체 내에서의 가장 큰 필드 크기(K_max)의 배수 단위로 정렬해야 한다.

구조체의 필드를 어떻게 선언하여도 해당 규칙을 만족하여도 해당 규칙을 만족하도록, 컴파일러는 구조체를 저장할 때 padding을 메모리 내에 선언한다. padding이란 사용되지 않는 더미(dummy) 공간이다. 아래는 예시 구조체 s1의 선언 코드와, s1이 메모리에 저장되는 개요 figure 7이다:

Figure 7. Alignment of Structure

struct S1 { 
    char c;        // 1 byte
    int i[2];      // 8 bytes (4*2)
    double d;      // 8 bytes
    short s;       // 2 bytes
};

따라서 구조체의 필드 선언 시 정렬을 고려하는 것은 메모리의 낭비를 줄일 수 있다. 따라서 권장되는 방식은 큰 타입부터 필드를 선언하는 것이다. 물론 이는 필수적인 규칙이 아니므로, 코드의 가독성을 위해서 이를 지키지 않을 수도 있다. 아래는 구조체 s3와 s4를 통해 이를 명시적으로 보여준다:

Figure 8. Saving Memory Space

struct S3 {          struct S4 {
    char c;              int i;   
    int i;               char c;
    char d;              char d;
};                   };

Array of Struct

구조체 배열은 예시 구조체 s2와 이에 대해 설명하는 코드, figure 9을 통해 그 작동 원리를 간단하게 파악할 수 있다.

Figure 9. Array of Struct Example

struct S2 {
    short i;    // 2 bytes
    int j;      // 4 bytes
    short k;    // 2 bytes
};
struct S2 a[8];

short get_k(struct S2 arr[], int idx) {
    return arr[idx].k;
}

movslq %esi, %rsi             ; idx 확장
lea (%rsi, %rsi, 2), %rax     ; idx * 12(구조체 크기) 계산
movzwl 0x8(%rdi,%rax,1), %eax ; arr[idx].k → offset 8