Node.js와 C++의 퀵정렬 속도 비교 (+메모리 할당 개선)

"Minions drawn by H.R. Giger" from DALL-E 2

재귀 없는 퀵정렬을 JS와 C++로 구현하면서 수행속도를 측정하고자 하였다.

 

C++은 정수형 타입이더라도 1바이트, 2바이트, 4바이트, 8바이트로 개발자가 선택하여 사용해야 하는 반면, JS는 정수형과 실수형 타입 모두 number로 사용되고 있다.

 

다만, JS의 경우 ArrayBuffer를 통해 원하는 바이트 크기의 버퍼를 생성할 수 있고, Int32Array() 함수로 해당 버퍼를 래핑하여 배열 원소의 크기를 4바이트로 사용할 수 있다.

 

[기본 배열 사용시]

• JS에서 1억개 할당 시 기본 배열은 최대 6.8GB의 메모리 공간을 차지하였다.
• 정렬 시 시간은 13.452초 소요되었다.
• 메모리 할당 시간은 36.656초 소요되었다.

[고정 크기 배열 사용시]

• JS에서 1억개 할당 시 고정 크기 배열은 400MB를 사용하였다. 정확히 1억개의 4바이트를 할당하였다.
• 정렬 시 시간은 12.507로 기본 배열보다 근소하게 빨랐다.
• 메모리 할당 시간은 2.344초가 소요되었다. 시간이 기본 배열의 6% 정도밖에 되지 않았다.

테스트에서, C++에서는 4바이트 크기인 int 형으로 배열을 만들어 사용하였고, JS에서는 Int32Array 배열을 만들어 사용하였다.

 

데이터 개수를 2천만, 4천만, 6천만, 8천만, 1억으로 증가하여 수행시간을 측정하였다.

 

시간 : 초	C++ (메모리 할당)	C++ (퀵정렬)	JS (메모리 할당)	JS (퀵정렬)
2000만	0.702	2.01	0.531	2.439
4000만	1.426	4.255	0.956	5.11
6000만	2.145	6.545	1.478	7.714
8000만	2.868	8.881	1.901	10.606
1억	3.58	11.284	2.416	13.483

 

특이하게도, 메모리 할당하는 시간은 JS가 더 적게 소요되었다.

 

퀵정렬의 경우 C++가 전체적으로 JS보다 약 20% 빠른 처리성능을 보여주었다.

 

이 결과를 보고, JS와 같은 인터프리트 언어라고 해서 반드시 C++보다 많이 느린 것은 아니라고 생각하게 되었다. 이 정도의 차이는 실제 사용시 크게 체감되지 않을 정도로 볼 수 있을 것 같다.

 

코드는 다음과 같다.

 

[JavaScript]

const USE_FIX_ARR = true;

/** INFO: 파라미터 만큼 배열을 생성하고 랜덤값 입력 */
function generateRandomArray(numData){
    let arr;
    if(USE_FIX_ARR){
        let arrBuffer = new ArrayBuffer(4 * numData);
        arr = new Int32Array(arrBuffer);
    } else {
        arr = new Array(numData).fill(0);
    }
    for(let i=0;i<numData;i++){
        arr[i] = Math.round(Math.random() * numData);
    }
    return arr;
}

function quickSort(arr, start, end){
    let stack = [];
    let low = start, high = end;
    let pivot, tmp;
    let i, j;
    stack.push(high);
    stack.push(low);
    while(stack.length !== 0){
        low = stack.pop();
        high = stack.pop();
        let curLength = high - low + 1;
        if(low >= high){
            //INFO: 한개밖에 없으면 continue
            continue;
        }

        if(curLength > 2) {
            //INFO: 2개 이상인 경우
            let tmpMid = Math.round((low+high) >> 1);
            //INFO: low, mid, high 중 중간값을 정해야 함
            pivot = arr[low] > arr[high] ? (arr[low] > arr[tmpMid] ? (arr[tmpMid] > arr[high] ? tmpMid : high) : low) : (arr[high] > arr[tmpMid] ? (arr[tmpMid] > arr[low] ? tmpMid : low) : high);

            {//SWAP
                tmp = arr[high];
                arr[high] = arr[pivot];
                arr[pivot] = tmp;
            }

            pivot = high;
        } else {
            //INFO: 2개 밖에 없는 경우
            if(arr[low] > arr[high]){
                //SWAP
                tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
            }
            continue;
        }

        //INFO: 피봇
        pivot = arr[high];
        i = low - 1;
        j = high;
        while(true){
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            if(i >= j) break;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        tmp = arr[i];
        arr[i] = arr[high];
        arr[high] = tmp;

        stack.push(high);
        stack.push(i+1);
        stack.push(i-1);
        stack.push(low);
    }
}

function main(){
    let numData = 100000000;
    let dataSizeGap = 5000000;

    for(let j=0;j<1;j++){
        for(let i=0;i<3;i++){
            console.time('mem');
            let arr = generateRandomArray(numData);
            console.timeEnd('mem');
            console.log('Start Quick Sort; data size : ' + numData);
            console.time('quick_sort');
            quickSort(arr, 0, numData - 1);
            console.timeEnd('quick_sort');
            //console.log(arr);
        }
        numData += dataSizeGap;
    }
}
main();

[C++]

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define N 100000000
#define R 100000
#define STKSIZE N

//unsigned int arr[N];
int* arr = nullptr;

int top = 0;
int* stack = nullptr;
//int stack[STKSIZE];

void init_stack() {
    top = 0;
}

void push(int i) {
    if (top < STKSIZE)
        stack[top++] = i;
    else {
        printf("stack full\n");
        exit(0);
        return;
    }
}

int pop() {
    if (top != 0)
        return stack[--top];
    else
        return 0;
}

int isStackEmpty() {
    if (top != 0)
        return 0;
    else
        return 1;
}

void quickSort() {
    int pivot, tmp;
    int i, j;
    int low, high;
    init_stack();
    low = 0;
    high = N - 1;
    push(high);
    push(low);
    while (!isStackEmpty()) {
        low = pop();
        high = pop();
        if (low >= high) {
            continue;
        }
        int curLength = high - low + 1;
        int pivot;

        if (curLength > 2) {
            int tmpMid = (low + high) / 2;
            pivot = arr[low] > arr[high] ? (arr[low] > arr[tmpMid] ? (arr[tmpMid] > arr[high] ? tmpMid : high) : low) : (arr[high] > arr[tmpMid] ? (arr[tmpMid] > arr[low] ? tmpMid : low) : high);
            {
                tmp = arr[high];
                arr[high] = arr[pivot];
                arr[pivot] = tmp;
            }
            pivot = high;
        }
        else {
            if (arr[low] > arr[high]) {
                tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
            }
            continue;
        }

        //INFO: 데이터가 최소 두개
        pivot = arr[high];
        i = low - 1;
        j = high;
        while (1) {
            while (arr[++i] < pivot);
            while (arr[--j] > pivot);
            if (i >= j)
                break;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        tmp = arr[i];
        arr[i] = arr[high];
        arr[high] = tmp;

        push(high);
        push(i + 1);
        push(i - 1);
        push(low);
    }
}

void main() {
    srand(time(NULL));

    stack = new int[STKSIZE];

    clock_t start, end;

    for (int i = 0; i < 3; i++) {
        top = 0;
        start = clock();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (rand() * (rand() + 1)) % N;
        }
        end = clock();
        printf("mem time : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

        start = clock();
        quickSort();
        end = clock();
        printf("quicksort time : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

        delete[] arr;
    }

    delete[] stack;
}