c# List.RemoveRange 부하

이베스트투자증권의 api를 이용하여 코스피와 코스닥 합해 2,500개 정도 종목들의 체결 데이터와 호가 데이터를 수신하여 List에 담고 있다. 약간의 필터링을 하긴 하지만 그래도 그 양은 상당하다. 장이 끝날 무렵 1gb를 넘는다. 이렇게 수신하는 건 저장하기 위한 게 아니라 연산을 위한 것인데 대개의 경우 연산은 최근 한 시간 정도의 대이터를 대상으로 한다. 따라서 수 시간 전의 리스트 아이템은 지워도 상관이 없다. 특히 장이 열린 뒤 첫 한 시간 정도에 대이터 생산이 폭주하므로 이때 것들만 지워 줘도 메모리 부담이 한결 덜해진다. 그런데 문제는 List의 아이템을 지우는 건 좀 부담스러운 작업이라는 거다.

This method is an O(n) operation, where n is Count.
List<T>.RemoveRange(Int32, Int32) Method

레퍼런스의 저 설명만 봐서는 딱히 메모리가 부족한 상황이 아니라면 굳이 아이템들을 지우는 게 왠지 뻘짓 같다. 저기에서 말하는 Count는 RemoveRange의 둘째 패러미터인 지울 아이템들의 개수가 아니라 List.Count 즉 지우기 전 아이템의 총 개수라는 거에 유의해야 한다. 예를 들어 천만 개 가운데 백만 개를 지우려면 백만 번이 아닌 천만 번의 작업이 필요하다는 소리다. 그러나 결론부터 말하면 미리 겁 먹을 일은 아니다.

Add에 대한 설명도 비슷하다.

If Count already equals Capacity, the capacity of the List is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.
If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
List.Add(T) Method

List에는 Capacity라는 프라퍼티가 있다. List는 메모리의 연속된 공간을 점유해야 하므로 원칙적으로 List의 아이템 개수가 달라지면 통째로 옮길 메모리를 먼저 확보한 뒤 거기에 달라진 내용을 복사해 넣는다. 예를 들어 천만 개의 아이템이 있는 List에 아이템 하나가 더해지면 천만 한 개를 통째로 새로운 자리로 옮겨야 하는 거다. 무척 부담스러운 작업이다. List는 이런 부하를 줄이기 위해 아이템 증가를 위해 메모리를 새로 할당할 때 증가할 개수보다 넉넉하게 공간을 확보한다. 그 크기가 Capacity이며 그 값은 대부분의 경우 Count보다 당연히 크다.

아이템을 추가할 때마다 Capacity가 갱신되지는 않지만 일단 이 값이 변경될 때에는 RemoveRange처럼 O(n)의 작업이 필요하다는 설명이다. 물론 이때의 n도 List.Count다.

여기까지만 보면 RemoveRange도 Add만큼이나 빡센 작업일 거 같아 함부로 하기가 주저된다. 하지만 괜찮다. 비록 Add가 무거운 작업이기는 하지만 주된 부하는 메모리 할당에서 일어나기 때문이다. RemoveRange는 크기를 줄이는 작업이기 때문에 새로 메모리 할당을 하지 않는다.

아래는 Add와 RemoveRange의 처리에 걸리는 시간을 비교한 예제다. 레퍼런스의 설명에 따르면 이들 모두 O(n)엄밀하게는 Add의 경우 더 적게의 작업을 필요로 하지만 실제로 걸리는 부하는 크게 다르다. RemoveRange가 훨씬 적어서 릴리스 빌드를 한 뒤 워밍 업 결과를 제외한 다섯 번의 평균은 Add가 11,552이고 RemoveRange는 고작 17이다.

List<int> Ints = new();

private void Form1_Load(object sender, EventArgs e)
{
    Ints.Add(0);
}

private void button1_Click(object sender, EventArgs e)
{
    Stopwatch stopwatch = new();

    stopwatch.Start();

    for (int i = 0; i < 1000000; i++)
    {
        Ints.Add(i);
    }

    textBox1.AppendText(stopwatch.ElapsedTicks.ToString("#,###") + "\r\n");
}

private void button2_Click(object sender, EventArgs e)
{
    Stopwatch stopwatch = new();

    stopwatch.Start();

    Ints.RemoveRange(0, 1000000);

    textBox2.AppendText(stopwatch.ElapsedTicks.ToString("#,###") + "\r\n");
}

이렇게 List의 아이템 수를 줄여도 List가 차지하는 메모리가 주는 건 아니라는 거에 유의한다. Capacity는 그대로이기 때문이다. 이미 확보해 놓은 공간이 늘어난 거기 때문에 이렇게 아이템 개수를 줄여 놓으면 이후로 한참 List의 크기는 늘지 않는다.