Loop vs System.arraycopy

위 병합 정렬을 하다보면, 병합(Merge)할 때 좌측과 우측을 다시 생성해서 데이터를 복사하는 로직이 있다.

static void merge(int[] array, int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];

    // copy elements
    for (int i = 0; i < n1; i++) {
        leftArray[i] = array[left + i];
    }
    for (int j = 0; j < n2; j++) {
        rightArray[j] = array[middle + 1 + j];
    }
    ...

자세한 소스코드는 (ArrayCopyTest.java)[https://github.com/moon1z10/Algorithms/blob/master/Sort/Merge%20Sort/src/ArrayCopyTest.java]를 참고하시기 바랍니다.

이 부분을 생각해 보다가, System.arraycopy가 JNI에서 memcpy를 이용하기 때문에 빠르다고 하는데, 과연 for 루프로 일일히 값을 복사하는 것과 얼마나 큰 차이가 나는지 궁금했다.

그래서 실제로 데이터 크기(배열 크기)가 10개부터 최대 1억개까지 100번의 테스트를 한 평균값(차이)를 확인하고 싶었다. 아래는 이와 관련한 결과표다.

• 매 테스트(for, arraycopy 각각)가 끝나면 System.gc()를 호출해서 힙 메모리를 확보한다.(혹시 모를 중간의 힙 메모리 부족 현상에 대비)

[1차 테스트]
10 : 0.6093942911663501
100 : 1.1538181818181816
1000 : 2.8449166666666614
10000 : 0.47788301721498316
100000 : 0.7794552799179456
1000000 : 1.1457185878720366
10000000 : 1.1390208185130597
100000000 : 1.033861828777882

[2차 테스트]
10 : 0.5891471953971954
100 : 1.1638762509420406
1000 : 2.798850613154953
10000 : 0.5326163386407198
100000 : 0.7773920475259962
1000000 : 1.1820075819126183
10000000 : 1.1089938717358152
100000000 : 1.0270741475683045

[3차 테스트]
10 : 0.3997166195481558
100 : 1.1523131313131316
1000 : 3.0913015873015808
10000 : 0.4648812268985408
100000 : 0.7781141712377341
1000000 : 1.154011297868145
10000000 : 1.1068014791697127
100000000 : 1.0156583926369083

[4차 테스트]
10 : 0.5472709669251915
100 : 1.0074769119769125
1000 : 2.1094746031746046
10000 : 0.4850920393759248
100000 : 0.8148313759939276
1000000 : 1.1602879367520795
10000000 : 1.1083047062029647
100000000 : 1.0109604210492393

컴퓨팅 능력에 따라 많은 차이를 보이겠지만, 힙 메모리가 충분히 확보 되었다고 가정하면,

데이터 사이즈가 커질 수록 System.arraycopy의 속도가 더 빠르다고만 볼수도 없다.

왜 이러한 현상이 일어날까?

1. JVM 최적화: JVM이 JIT(Just-In-Time) 컴파일러를 통해 for 루프를 최적화할 수 있습니다. 이는 for 루프의 성능을 개선하여 System.arraycopy와 비슷한 성능을 보이게 합니다.
2. 메모리 관리: 큰 배열을 복사할 때 System.arraycopy의 성능 이점이 더 두드러집니다. 하지만 테스트에서 힙 메모리 확보를 위한 System.gc() 호출이 반복적으로 수행되어 오버헤드가 발생할 수 있습니다.
3. 캐시 효율성: 작은 배열에서는 캐시 효율성 때문에 for 루프와 System.arraycopy의 성능 차이가 크지 않을 수 있습니다.
4. 테스트 환경: 테스트 환경의 변수들(예: JVM 버전, 운영체제, 하드웨어 등)이 성능에 영향을 미칠 수 있습니다.

만약 repeat (테스트 케이스 개수)를 1로 해서 비교해보면 재밌는 결과를 볼 수 있다.

[1번만 수행할 때 결과]
10 : 0.03937007874015748
100 : 2.090909090909091
1000 : 10.916666666666666
10000 : 43.03125
100000 : 9.567567567567568
1000000 : 1.3107298915682148
10000000 : 0.963932303708499
100000000 : 0.9705304306509438

여기서 의미있는 결과를 얻을 수 있는데,

1. 데이터 사이즈가 매우 작은(대략 <100) 경우 for loop가 더 빠르다.
2. System.arraycopy는 <1백만 사이즈의 데이터의 경우, 훨씬 빠른 결과를 보여준다. 하지만 100번의 반복된 테스트의 평균 결과를 보면 반드시 그렇다고 할 수도 없다. 아니 왜…10000번의 경우, System.arraycopy가 43배나 빠른데, 100번의 테스트 평균은 오히려 더 느려지는 걸까…????
3. 데이터 사이즈가 대략 1천개가 넘어가기 시작하면 Loop와 System.arraycopy의 차이는 무의미해진다.

개인 PC환경에서의 나노초(ns)로 비교 분석 한 내용을 토대로 결론을 지은 것으로, 각각의 환경에 따라 내용을 틀려질 수 있습니다.