동적 배열

동적 배열에 대해서 알아봅시다.

배열을 크기 변경 가능성을 기준으로 나누어 보면, 크기가 고정된 정적 배열과, 크기 변경이 자유로운 동적 배열로 나눌 수 있습니다. 동적 배열은 더 유연한 데이터 관리를 가능하게 하며, 정적 배열은 크기가 고정된 대신 구현이 쉽고 메모리 사용량이 예측 가능하다는 장점이 있습니다.

오늘날 웹분야에서 쓰이는 대부분의 고수준 언어들(JS, Java, Python)은 동적 배열을 언어 자체나 표준 라이브러리 형태로 제공합니다. 심지어는 더 아래 수준인 시스템 레벨 언어들(C++, Rust, Zig)도 대부분 동적 배열을 언어 기능이나 표준 라이브러리로 제공합니다.

그렇기 때문에 동적 배열을 당연하게 여기며 살아가는 프로그래머도 있는 것 같습니다. 이번 글에서는 아무생각 없이 쓰였던 동적 배열이 어떻게 구현되는지 알아봅시다.

동적 배열의 기본 동작

대부분의 동적 배열들은 거의 같은 규칙을 공유합니다. 할당된 메모리, 할당된 메모리의 크기, *요소의 개수까지 총 세 가지 값을 가지죠. 이 세 값들이 어떻게 사용되는지를 먼저 알아봅시다.

완전히 빈 배열에 요소 추가

우선 각 요소가 4바이트 크기인 배열에 한 개의 요소를 넣는 상황을 예시로 동적 배열의 동작을 살펴봅시다. 보통 처음에는 할당된 메모리는 NULL, 할당된 메모리의 크기와 요소의 개수은 0으로 둡니다.

할당된 메모리: []
할당된 메모리의 크기: 0
요소의 개수: 0
	

이제 배열에 값을 넣으려면 할당된 메모리의 크기를 (요소의 개수) + 1을 바이트 단위로 변환해서 비교합니다. 할당된 메모리의 크기가 부족하면 더 많은 메모리를 할당합니다. 사용 가능한 공간이 없으니 OS에 요청하여 메모리를 받아옵니다. 보통 필요한 양보다 여유를 두고 할당합니다. 16바이트 정도를 할당했다고 해봅시다.

할당된 메모리: [<4byte>,<4byte>,<4byte>,<4byte>]
할당된 메모리의 크기: 16
요소의 개수: 0
	

이제 필요한 공간을 확보했으니, 요소에 값을 넣어줍시다. 여기서는 13을 넣어보겠습니다. 값이 들어갈 위치는 요소의 개수를 인덱스로 씁니다. 현재 요소의 개수는 0이니 배열의 제일 처음에 값을 넣어줍시다.

할당된 메모리: [13,<4byte>,<4byte>,<4byte>]
할당된 메모리의 크기: 0
요소의 개수: 0
	

이제 요소의 개수에 변경된 상태를 반영해줍니다.

할당된 메모리: [13,<4byte>,<4byte>,<4byte>]
할당된 메모리의 크기: 16
요소의 개수: 1
	

꽉찬 배열에 요소 추가

이번에는 요소들이 추가되다가 공간이 부족해졌을때 동적 배열이 어떻게 동작하는지 알아봅시다. 우선 현재 상태는 다음과 같습니다.

할당된 메모리: [13,13,67,423]
할당된 메모리의 크기: 16
요소의 개수: 4
	

여기서 만약 100을 추가하려한다면, 공간이 부족하기 때문에 새로 메모리를 할당해야 합니다. 또한 메모리를 새로 할당한 후 기존 데이터를 복사하고, 기존 메모리는 할당 해제하는 작업까지 필요합니다.

-- 메모리 교체 --
할당된 메모리: [13,13,67,423,<4byte>,<4byte>,<4byte>,<4byte>]
할당된 메모리의 크기: 16
요소의 개수: 4
(기존 메모리 할당 해제)
	

-- 새 요소 추가 --
할당된 메모리: [13,13,67,423,100,<4byte>,<4byte>,<4byte>]
할당된 메모리의 크기: 32
요소의 개수: 5
	

공간이 넉넉할때 요소 추가

이번에는 공간이 넉넉할때 동적 배열이 어떻게 동작하는지 알아봅시다. 우선 현재 상태는 다음과 같습니다.

할당된 메모리: [13,<4byte>]
할당된 메모리의 크기: 8
요소의 개수: 1
	

이때는 그냥 있는 공간에 값을 넣어주면 됩니다.

할당된 메모리: [13,13]
할당된 메모리의 크기: 8
요소의 개수: 2
	

다른 조작들

삭제, 복사등의 다른 작업들은 추가적인 메모리를 요구할 일이 없기 때문에 일반적인 배열과 거의 비슷한 방식으로 사용됩니다.

동적 배열의 확장 정책

동적 배열의 공간이 부족할때 얼마만큼 확장하는지에 따라 동적 배열의 효율이 달라집니다. 만약 공간이 부족할때 정확히 필요한 만큼만 추가 할당을 하게 된다면, 모든 요소 append가 메모리 할당을 발생시켜 심각한 성능 저하를 일으킬 것입니다.

1.5배씩 확장하는 것이 좋다고 하지만, 구현 단순성을 위해서 보통 2배씩 늘린다고 합니다. 다음은 위키피디아에 있던 동적 배열 구현별 확장 비율입니다.

C에서의 동적 배열

C에서 동적 배열을 표현하려면 다음과 같은 구조체를 만들 수 있습니다.

struct DynamicIntArray {
	int *data;
	size_t size;
	size_t cap;
};

하지만 이렇게 하면 매 타입마다 새로운 구조체를 만들어 줘야하는 번거로움이 있습니다. 그래서 이런 방법을 사용할 수 있습니다.

struct DynamicArrayHeader {
	size_t size;
	size_t cap;
};

이렇게 size와 cap 정보만을 담은 Header 구조체를 먼저 만듭니다.

그 다음 이런식으로 배열을 할당해줍니다.

int *arr = (int*)((struct DynamicArrayHeader*)malloc(10*sizeof(int)+sizeof(struct DynamicArrayHeader))+1);

이렇게 할당하면 메모리는 다음과 같은 구조가 됩니다.

+--------+-------------+
| Header |   int[10]   |
+--------+-------------+
         |
         `-> int *arr가 가리키는 위치
	

꽤나 긴 코드이지만 뜯어보면 간단한 구조를 가집니다.

// int 10개, 헤더 한 개 크기의 메모리를 할당합니다.
malloc(10*sizeof(int) + sizeof(struct DynamicArrayHeader))

// 할당한 메모리의 타입을 변경합니다.
(struct DynamicArrayHeader*)

// 포인터를 1만큼 이동시킵니다.
// 타입이 struct DynamicArrayHeader*로 변환됐기에
// struct DynamicArrayHeader의 바이트 수만큼 이동합니다.
+ 1

// 메모리의 타입을 변경합니다.
(int*)

이런식으로 헤더를 포인터 앞에 숨겨버리면 int*같은 단순한 포인터를 동적 배열처럼 사용할 수 있게 됩니다.

구현

지금까지는 동적 배열에 필요한 상태와, 그 상태를 어떤식으로 배치하는지를 알아봤습니다. 이제 실제 동적 배열을 구현해봅시다.

구현 단순성을 위해 매크로와 헤더 트릭을 사용하지 않겠습니다. 간단한 예시이기 때문에 append 기능만 작성했습니다.

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>

typedef struct {
	int *data;
	size_t size;
	size_t cap;
} DynamicIntArray;

int da_append(DynamicIntArray* arr, int value)
{
	if (arr->size >= arr->cap) {
		size_t new_cap = arr->cap == 0 ? 2 : arr->cap*2;
		int *new_data = realloc(arr->data, sizeof(*arr->data)*new_cap);
		if (new_data == NULL) return 1;
		arr->data = new_data;
		arr->cap = new_cap;
	}
	arr->data[arr->size++] = value;
	return 0;
}

int main()
{
	DynamicIntArray arr = {0};
	da_append(&arr, 10);
	da_append(&arr, 20);
	da_append(&arr, 30);
	da_append(&arr, 40);
	for (int i = 0; i < arr.size; ++i) {
		printf("%d\n", arr.data[i]);
	}
	return 0;
}