C# List의 Add, AddRange 사용 시 성능 차이 실험

C#의 List에서 자료를 추가하는 함수로 Add, AddRange가 있다. (Insert, InsertRange도 있지만 이글에서는 다루지 않는다.) 마이크로소프트 공식 문서(List<T>.Add(T), List<T>.AddRange(T))나 여타 다른 곳에서 일반적으로 두 함수 모두 List의 끝에 요소를 추가하는 함수로 설명하고 있으며 차이는 Add는 요소 하나, AddRange는 범위(배열, List 등등)로 추가하느냐 차이이다.

List에 대해 조금만 더 자세히 공부했다면 Add와 AddRange의 차이는 쉽게 알 수 있을 것이다. Add를 백만 번 하는 것과  AddRange로 백만 개 요소를 한 번에 추가하는 것 중 후자가 성능 상 유리하다는 것은 자명하다. 이 차이에 대한 자세한 설명은 아래에 하기로 하고 일단 바로 두 함수의 성능 비교를 먼저 보자.

테스트 코드

static void Main(string[] args)
{
	//실험 준비
	int[] intArray = new int[1000000];
	float[] floatArray = new float[1000000];
	for (int i = 0; i < 1000000; i++)
	{
		intArray[i] = i;
		floatArray[i] = i + i * 0.0000001f;
	}

	List<int> intContainer = new List<int>();
	List<float> floatContainer = new List<float>();


	Thread.Sleep(1500);
	Console.WriteLine("Ready...");
	Thread.Sleep(1500);

	//단순 Add
	System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
	stopwatch.Start();
	for (int i = 0; i < 1000000; i++)
	{
		intContainer.Add(intArray[i]);
		floatContainer.Add(floatArray[i]);
	}
	stopwatch.Stop();
	Console.WriteLine("[1]: " + stopwatch.Elapsed.TotalMilliseconds);

	intContainer.Clear();
	floatContainer.Clear();
	stopwatch.Reset();


	//AddRange 사용
	Thread.Sleep(3000);
	stopwatch.Start();
	intContainer.AddRange(intArray);
	floatContainer.AddRange(floatArray);
	stopwatch.Stop();
	Console.WriteLine("[2]: " + stopwatch.Elapsed.TotalMilliseconds);

	intContainer.Clear();
	floatContainer.Clear();
	stopwatch.Reset();
}

 

참고로, 코드에 int와 float배열 두 개를 사용했는데 큰 의미는 없으니 무시해도 된다.

결과

Ready...
[1]: 9.7543
[2]: 1.0383

 

첫번째가 Add 백만 번(× 2), 두 번째가 AddRange로 백만 개를 한 번(× 2)에 추가한 결과이다.

이러한 결과가 나타난 이유로 마이크로소프트 공식 문서에 따라 설명하면 Add사용 시 Count가 Capacity에 도달하면 Capacity를 늘리기 위해 새 배열을 다시 할당하고 요소를 추가하기 전에 원래 배열을 새 배열에 복사한다.
AddRange도 마찬가지이지만 AddRange는 다수의 요소를 추가하기 위해 함수를 한 번만 호출하므로 배열 할당도 한 번만 이루어지게 되어 성능 상 이점을 가지게 되는 것이다.

Big-O로 나타내 보면 Add와 AddRange는 Count < Capcity인 경우 O(1), Count = Capacity인 경우 O(n) 시간복잡도를 가진다. 이에 따라, 빈 List에서 n개의 요소를 추가한다면 Add의 경우 O(n²), AddRange는 O(n)의 시간복잡도를 가지게 된다.

 

이렇게만 끝내면 조금 허전하니 여기서 좀 더 나아가보자.

마이크로소프트 공식 문서를 다시 인용하면 Add는 분명히 Count < Capacity인 경우 O(1)이라고 했다. 그러면 Add사용 시 미리 Capacity를 지정하면 Count가 Capacity에 도달하는 일이 없으므로 AddRange와 유사한 결과를 얻을 수 있을 것이라고 예측할 수 있다. 과연 그럴까?

다음의 코드를 추가하여 다시 실험을 수행해 보자.

추가 코드

//Capacity 지정 후 Add 사용
Thread.Sleep(3000);
stopwatch.Start();
intContainer.Capacity = intArray.Length;
floatContainer.Capacity = floatArray.Length;
for (int i = 0; i < 1000000; i++)
{
	intContainer.Add(intArray[i]);
	floatContainer.Add(floatArray[i]);
}
stopwatch.Stop();
Console.WriteLine("[3]: " + stopwatch.Elapsed.TotalMilliseconds);

 

결과

Ready...
[1]: 9.6476
[2]: 0.99
[3]: 5.8596

앞선 결과와 마찬가지로 첫 번째가 Add 백만 번(× 2), 두 번째가 AddRange로 백만 개를 한 번(× 2)에 추가, 세 번째가 Capacity를 미리 지정하고 Add 백만 번(× 2)이다.

예측한 대로, 수행 시간은 분명 줄어들었다. 하지만, 여전히 AddRange를 사용한 것에 비해 느리다. 원인은 무엇일까?

원인은 바로 함수 호출의 오버헤드 때문이다. 함수 사용은 공짜는 아니며 미세하게 시간과 메모리 기타 자원을 소모한다. 실제로 위 실험 코드에서 Add, AddRange를 빈 함수로 대체하면 아래의 결과를 얻는다.

Ready...
[1]: 4.0301
[2]: 0.0021

첫 번째가 함수 백만번(× 2) 호출, 두번째가 함수 한 번(×2) 호출이다. 계산을 해보면 5.8596 - 4.0301 = 1.8295 ≒ 0.99로 유사하게 나옴을 알 수 있다. 약 0.8밀리초나 차이가 나지 않느냐고 물을 수 있겠지만 빈 함수에 비교문만 추가해도 시간이 0.2밀리초 정도 증가하며 기타 내부적으로 알 수 없는 코드도 영향을 주었을 것이다.

 

결론적으로, 함수 오버헤드를 빼면 AddRange와 Capacity를 미리 지정 후 Add 하는 것은 큰 차이가 없다. 다만, 함수 호출 비용을 감안하여 일반적으로 AddRange를 사용하면 된다.