Java ArrayList<Integer> 대 C# List<int> 정렬 성능 비교

인터넷을 둘러 보다가 C++와 C#, Java, 그리고 Node.js 정렬 성능 비교란 흥미로운 글을 발견했다. 글에서는 크기가 1백만인 int[] 배열로 벤치마크를 하고 있었는데, 소스를 약간 고쳐서 자바 ArrayList<Integer>와 C# List<int> 간에는 얼마 만큼의 성능차가 나는지 알아 보았다.

자바

static void quicksort(ArrayList<Integer> a, int start, int end) {
    if (end - start < 2) {
      return;
    }
    int p = a.get(start + (end - start) / 2);
    int l = start;
    int r = end - 1;
    while (l <= r) {
      if (a.get(l) < p) {
        ++l;
        continue;
      }
      if (a.get(r) > p) {
        --r;
        continue;
      }
      int t = a.get(l);
      a.set(l, a.get(r));
      a.set(r, t);
      ++l;
      --r;
    }
    quicksort(a, start, r + 1);
    quicksort(a, r + 1, end);
}

quicksortThreeway()도 수정한 방법은 거의 같으므로 생략. 자바는 인덱서([])를 제공하지 않아서 단지 int[]를 ArrayList<Integer>로 바꿨을 뿐인데도 소스를 거의 절반은 고쳐야 했다.

C#

static void Quicksort(List<int> a, int start, int end)
{
    if (end - start < 2)
    {
        return;
    }
    var p = a[start + (end - start) / 2];
    var l = start;
    var r = end - 1;
    while (l <= r)
    {
        if (a[l] < p)
        {
            ++l;
            continue;
        }
        if (a[r] > p)
        {
            --r;
            continue;
        }
        var t = a[l];
        a[l] = a[r];
        a[r] = t;
        ++l;
        --r;
    }
    Quicksort(a, start, r + 1);
    Quicksort(a, r + 1, end);
}

C#은 한 줄만 고치면 되었다.

벤치마크 결과 및 분석

int 타입은 개당 4바이트라 백만개 짜리 리스트라고 해도 전체가 4MB 밖에 안된다. 캐시 영향을 최소화하기 위해 이 테스트에서는 원소 개수를 천만개로 늘렸다.

결과가 꽤 흥미로운데, 일단 “Built-in”이라고 되어 있는 int[] 벤치마크 항목에선 자바가 C#보다 25% 빠르다. 그 이유는 아마도 자바의 Timsort가 .NET의 Introsort보다 효율적이어서인 것 같다. .NET도 자바 버전을 그대로 이식한 C# 버전이 있으니 다음번엔 그걸로 비교해 보는 것도 좋겠다.

반면 자바 ArrayList<Integer>와 C# List<int>를 대상으로 한 나머지 두 테스트에서는 C# 쪽이 2-웨이는 170%, 3-웨이는 282% 빨랐다. 자바에서는 int 같은 타입의 원소를 리스트에 넣으려면 꼭 박싱(프리미티브 타입을 레퍼런스 타입으로 포장하는 것)을 거쳐야 한다. 그 결과 성능이 엄청나게 희생되는 걸 볼 수 있다. 그렇지만 C#과 자바 양쪽 모두 배열을 쓴 쪽이 압도적으로 빠른 것도 눈여겨 볼 점이다. 대량의 데이터 정렬은 리스트 대신 배열로 하는 게 유리하다는 결론.