C#에서 List는 정말 많이 사용하는 클래스입니다.
그리고 사용법이 너무 쉬워서 다들 간단하게 기본 생성자를 할당해서 사용하고 계십니다.
혹시…List의 내부가 궁금하지 않으신가요?
저는 지금부터 .NET Framework 4.8 Reference Source를 기반으로 설명하겠습니다. .NET Core도 큰 차이는 없을꺼라 굳게 믿으며…
_defaultCapacity = 4; 는 List의 기본 용량 지표입니다.
52번 줄에 보면 우리가 자주 쓰는 List<T> Vincent = new List<T>();의 생성자가 보이네요.
47번 줄에 있는 길이가 0인 제네릭 배열을 할당하고 있습니다. 지표가 4지만 아무것도 없는 배열을 할당하는 것입니다.
처음 C로 코딩을 시작하신 분들은 아시겠지만, 배열은 할당 후 길이를 바꿀 수 없습니다. 도대체 어떻게 .NET에서는 그게 가능한 걸까요?
자주 사용하는 메서드인 Add 메서드로 가보겠습니다.
public void Add(T item) {
if (_size == _items.Length) EnsureCapacity(_size + 1);
_items[_size++] = item;
_version++;
}
private void EnsureCapacity(int min) {
if (_items.Length < min) {
int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
if (newCapacity < min) newCapacity = min;
Capacity = newCapacity;
}
}
Add 를 호출하면 현재 배열의 사이즈를 비교하고 가득찼다 (_size == _items.Length)고 판단하면 EnsureCapacity 메서드를 호출합니다. 바로 다음 줄 코드를 보면 이상한 게 있습니다.
배열은 0부터 인덱스를 시작하고, 길이는 1부터 체크하기 때문에 배열의 길이와 인덱스의 크기가 같아지면 예약한 메모리 바깥에 할당하는 행위입니다. EnsureCapacity 메서드가 어떤 행위를 했기 때문에 오류가 발생하지 않는 것이겠죠?
EnsureCapacity 메서드를 보니, 이 녀석은 꽉찬 배열의 길이를 묻지도 따지지도 않고 2배로 용량을 늘려버립니다. 물론 2배로 늘린 길이가 Array.MaxArrayLength 초과하지 않아야겠지만요.
그 다음 Capacity라는 Property에 할당합니다. 그럼 Property니까 SetValue 메서드가 발생했겠네요. 확인해보겠습니다.
public int Capacity {
get {
Contract.Ensures(Contract.Result<int>() >= 0);
return _items.Length;
}
set {
if (value < _size) {
if (value > 0) {
T[] newItems = new T[value];
if (_size > 0) {
Array.Copy(_items, 0, newItems, 0, _size);
}
_items = newItems;
}
else {
_items = _emptyArray;
}
}
}
}
set 부분을 확인해보니 121줄에서 현재 길이와 다른 용량이 할당되면 동작 하도록 되어있습니다. 그리고 그 길이가 0보다 큰 값이라면 new T[value]를 이용해서 새로 입력받은 용량만큼 재할당 하고 있습니다. 그리고 그 새로 할당된 배열에 Array.Copy 메서드를 이용해 기존 배열의 값을 복사 하고 있습니다.
예를 들어…
List<int> vincent = new();
vincent.Add(1); // 최초 길이가 0인 배열을 할당했으므로, 여기서 다시 용량이 4인 배열 재할당.
vincent.Add(2);
vincent.Add(3);
vincent.Add(4); // 여기까지 재할당 없음.
vincent.Add(5); //여기서 길이가 8인 배열 재할당.
위와 같이 되는데 재할당 이라는 표현을 쓴 만큼 기존 배열의 길이가 길어진다는 의미가 아니라 남겨두고 새로 할당이라는 뜻입니다.
new int[0]은 카운트가 있으니 가비지는 아니고, 처음 Add하면서 할당된 new int[4]가 에 1~4까지 숫자가 차있는 상태로 가비지가 되고, new int[8] 인 배열이 할당되고 거기에 1~5까지 들어가는 것입니다. 이렇게 재할당을 계속 발생시키는 행위는 GC가 제거할 레퍼런스 카운트가 0인 쓰레기 메모리가 계속 늘어난다는 의미 와 같은 의미입니다. 4, 8, 16, 32 …순서로 할당이 되니 만약 추가해야할 데이터가 10000개라면 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 + 4096 + 8192 + 16384 = 32764개의 메모리 영역이 필요합니다. 물론 16384개 이전의 4부터 8192까지 더한 16380개의 메모리는 쓰레기가 됩니다.
그럼 List를 쓰면 많이 추가할 때마다 가비지가 계속 발생하는 클래스니까 쓰면 안되는건가 싶은데, 간단한 해결책을 .NET API가 제시해주고 있습니다. List(int capacity) 생성자를 이용하는 것입니다.
public List(int capacity) {
if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
Contract.EndContractBlock();
if (capacity == 0) _items = _emptyArray;
else _items = new T[capacity];
}
이 생성자를 이용하면 미리 예약한 크기만큼 처음에 한 번 할당하고 끝납니다. 물론 이 용량마저도 초과하는 데이터를 Add하면 다시 2배만큼 뻥튀기 되는 일이 발생하겠지만, 그래도 재할당하는 횟수가 적으니 overhead가 적을 것입니다. 결국 C와 똑같았고 마법은 .NET에서도 없었습니다.
따라서
List에 담고자 하는 크기를 예측할 수 있다면 반드시 용량을 예약하고 사용하자
이상입니다.