[JAVA 8] ParallelSort

Arrays.parallelSort()

• Fork/Join 프레임워크를 사용해서 배열을 병렬로 정렬하는 기능을 제공한다.

 

병렬 정렬 알고리즘

• 배열을 둘로 계속 쪼갠다.
• 합치면서 정렬한다.

 

이전에 parallelStream을 설명할 때 말한 적이 있다. 상황에 따라서 병렬로 하는게 빠를 수도 있고, 더 느릴 수도 있다고 말이다. 실제로 그렇게 되는지 확인해보자.

 

sort()와 parallelSort() 비교

int size = 10000000;
int[] numbers = new int[size];
Random random = new Random();
IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());

long start = System.nanoTime();
Arrays.sort(numbers);
System.out.println("  serial sorting took " + (System.nanoTime() - start));

IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());
start = System.nanoTime();
Arrays.parallelSort(numbers);
System.out.println("parallel sorting took " + (System.nanoTime() - start));

위의 코드에서 size만 변경해보며 시간이 얼마나 걸리는지 차이를 알아보자.

 

size가 1,000인 경우

• serial sorting took 635,363
• parallel sorting took 2,320,564

 

size가 10,000인 경우

• serial sorting took 4,114,773
• parallel sorting took 5,344,624

 

size가 100,000인 경우

• serial sorting took 39,835,655
• parallel sorting took 42,495,858

 

size가 1,000,000인 경우 

• serial sorting took 967,621,466
• parallel sorting took 333,204,237
• 알고리즘 효율성은 같다. 시간복잡도 : O(nlogN), 공간복잡도 : O(n)

 

size가 10,000,000인 경우

• serial sorting took 968,464,268
• parallel sorting took 277,913,894

 

size가 100,000,000인 경우

• serial sorting took 10,152,806,777
• parallel sorting took 2,313,726,436

size를 10단위로 늘려가며 테스트를 해보니 값이 커질 수록 병렬처리가 빠른 것을 확인해볼 수 있습니다.

 

그렇다면, size가 작으면 병렬이 느리고 size가 크면 병렬이 빠른 이유는 무엇일까요??

 

일단, 직렬 프로그래밍과 병렬 프로그래밍이 어떻게 다른지 알아야합니다.

 

프로세스에서 여러가지 일을 수행하기 위해선 멀티쓰레드를 사용해야 합니다. 단일쓰레드는 직렬 프로그래밍, 멀티쓰레드는 병렬 프로그래밍에서 사용한다고 보면됩니다. 여튼, 병렬 프로그래밍에서 사용하는 쓰레드는 쓰레드풀이 있지만, 쓰레드를 만들어 사용한다고하면 시간이 오래걸립니다. 이 때문에 실제로 size가 작을 때 작은 size를 계산하는 동안 쓰레드를 가져오는데 시간을 소모하기때문에 더 시간이 오래 걸리는 것 입니다. 

 

실제로 size가 100일 때 시간 차이를 확인해 보았습니다. 

public class SortTest {
    public static void main(String[] args) {
        int size = 100;
        int[] numbers = new int[size];
        Random random = new Random();
        IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());

        long start = System.nanoTime();
        Arrays.sort(numbers);
        System.out.println("  serial sorting took " + (System.nanoTime() - start));

        IntStream.range(0, size).forEach(i -> numbers[i] = random.nextInt());
        start = System.nanoTime();
        Arrays.parallelSort(numbers);
        System.out.println("parallel sorting took " + (System.nanoTime() - start));



        start = System.nanoTime();
        MyThread myThread = new MyThread();
        myThread.start();
        System.out.println("Thread took " + (System.nanoTime() - start));
    }

    public static class MyThread extends Thread{
        int num;

        public MyThread() {
            this.num = 0;
        }

        public MyThread(int num) {
            this.num = num;
        }

        @Override
        public void run() {
            System.out.println("Thread Test");
        }
    }
}

 

출력

size 100일 때 시간

serial sorting 작업은 399,160입니다. 1개의 쓰레드를 생선하는데 필요한 시간은 1,075,145로 100개를 직렬로 정렬하는 것보다 더 오랜 시간을 소모하는 것을 확인할 수 있습니다. 그렇기 때문에 size에 따라서 직렬로 사용할지 병렬로 사용할지 잘 판단하여야 합니다.