[Java] sort와 parallelSort 비교

백기선님의 자바 8 강의에서 정렬을 학습하다가 궁금해서 적게되었다. (정리한 깃허브)

 

자바 8 이전에는 Arrays.sort()를 사용하여 정렬을 하였다.

자바 8 이후 sort()를 개선한 새로운 메소드인 Arrays.parallelSort()가 나왔다.

특히 parallelSort에 대해 간단하면서도 내부적으로 동작하는 설명이 없어서 직접 찾아보고 작성하게 되었다.

 

 

 

 

1. Arrays.sort()란?

객체 또는 기본타입의 배열(array of objects or primitives)을 정렬하기 위해 나왔다.

여기에 사용된 정렬 알고리즘은 Dual-Pivot Quicksort 이다.

즉, 더 좋은 성능을 내기위해 Quicksort 알고리즘을 커스터마이징한 것이다.

이 방법은 싱글 쓰레드(Single-Thread)이며, 2가지 메소드(오버로딩)가 있다.

• sort(array) : 전체 배열을 오름차순 정렬
• sort(array, fromIndex, toIndex) : fromIndex 에서 toIndex까지의 요소만 정렬

int[] array = {10, 4, 6, 2, 1, 9, 7, 8, 3, 5};
int[] expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Arrays.sort(array); // 정렬
System.out.println(Arrays.equals(array,expected)); // true

• 장점
  • 작은 데이터 집합(smaller data sets)에서 빠르게 작동함
• 단점
  • 대용량 데이터 집합일 경우 성능 저하
  • 시스템의 다중 코어(multiple cores)를 사용하지 않음

 

Object.equals() : 같은 객체인지 비교하는 것 (주소값 비교)
Arrays.equals() : 배열의 요소들이 같은지 비교함
Arrays.deepEquals() : 깊은 비교를 통해 배열의 요소들이 같은지 비교함

Arrays.deepEquals()가 무엇인지 궁금하다면 아래 더보기를 눌러보자.

Arrays.deepEquals()는 두 개의 중첩 또는 다차원 배열 간의 동등성을 확인하기 위해 사용한다.
기존의 Arrays.equals()에서 2차원 배열을 비교를 하면 2차원 배열의 원소들(1차원 배열들)의 주소값을 비교한다.

즉, 다시 1차원 배열에서 요소들을 꺼내서 비교하지 않기 때문에 1차원 배열 요소 비교에서만 사용해야한다.

이 때문에 deepEquals()는 내부 요소들이 배열이면 deepEquals()를 재귀하여 제일 안에있는 요소들을 비교하게 된다.

 

 

 

 

2. Arrays.parallelSort()

이 메소드도 객체 또는 기본 타입의 배열을 정렬한다.

sort()와 유사하게 전체 배열과 부분 배열을 정렬하는 두 가지 메소드가 있다.

하지만 parallelSort는 기능적으로 다르게 동작한다.

싱글 쓰레드를 사용하여 데이터를 순차적으로 정렬하는 sort()와 다르게 parallel sort-merge sorting 알고리즘을 사용한다.

배열을 자체적으로 정렬한 다음 병합되는 하위 배열로 분할한다.

병렬 작업을 실행하기 위해 ForkJoin pool을 사용한다.

이 때 특정 조건이 충족될 때만 병렬 처리를 사용한다는 것을 알아야한다.

• (배열 크기 <= 8192) or (프로세서에 코어가 하나만 있는 경우)

위 두 조건중 하나를 충족하게 되면 순차적으로 Dual-Pivot Quicksort 알고리즘을 사용하게 된다.

위 두 조건에 해당되지 않으면 병렬 정렬(parallel sort)을 사용하게 된다.

int[] array = {10, 4, 6, 2, 1, 9, 7, 8, 3, 5};
int[] expected = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Arrays.parallelSort(array);
System.out.println(Arrays.equals(array, expected)); // true

// -------------

int[] array = {10, 4, 6, 2, 1, 9, 7, 8, 3, 5};
int[] expected = {10, 4, 1, 2, 6, 7, 8, 9, 3, 5};
Arrays.parallelSort(array, 2, 8); // 부분 정렬, array[2] ~ array[7]만 정렬
System.out.println(Arrays.equals(array, expected)); // true

• 장점
  • 대용량 데이터 집합에 대해 더 나은 성능 제공
  • 시스템의 다중 코어 활용
• 단점
  • 작은 크기의 배열일 경우 느림

 

 

2.1 parallelSort() 동작 원리

메소드를 살펴보면 if문으로 아까 말했던 조건이 있습니다.

첫 번째 조건은 8192 보다 작거나 같을 때

두 번째 조건은 공용 풀의 대상이 됐던 병렬화 수준이 1일 때

위 조건 중 하나가 해당되면 Arrays.sort()와 동일하게 동작하게 된다.

 

ForkJoinPool은 Fork & Join 프레임워크에서 제공하는 쓰레드 풀이다.

이것은 지정된 수의 쓰레드를 미리 생성해놓은 다음 반복해서 재사용할 수 있게 하는 쓰레드 풀이기도 하다.

이 쓰레드 풀은 기본적으로 코어의 개수와 동일한 개수의 쓰레드를 생성하게 된다.

따라서 컴퓨터 코어 개수에 의존하여 미리 설정된 병렬화(parallelism)를 사용하는 것이다.

System.out.println("내 컴퓨터 코어 개수 : " + Runtime.getRuntime().availableProcessors()); // 10
System.out.println("병렬 처리 가능한 쓰레드풀 : " + ForkJoinPool.getCommonPoolParallelism()); // 9

내 컴퓨터에서는 10개의 CPU코어가 존재하는데, 결과적으로 9개는 병렬화가 가능하다.

이것은 기본값으로 따로 설정도 가능하다.

 

그렇다면 실제로 저 ForkJoinPool의 COMMON_PARALLELISM에 값이 어떻게 들어가는지 디버그해서 찾아보자.

궁금한건 계속 파고드는 성격이라 자꾸 찾게된다.
책이나 공식문서에서 기본적으로 코어의 개수와 동일한 개수의 쓰레드 생성이라는데 왜 코어 개수 - 1개의 결과값이 나올까?

ForkJoinPool.java

스태틱 블록(static block)은 클래스가 로딩되고 클래스 변수가 준비된 후 자동으로 실행되는 블록이다.

따라서 저 스태틱 블록 안의 것들이 실행될 때 common 변수값과 COMMON_PARALLELISM 변수값이 초기화된다.

그럼 먼저 common부터 살펴보자.

new ForkJoinPool(0)이 만들어지고 있으므로 한번 들어가보자! (새벽이라 신남)

 

ForkJoinPool.java

현재 ForkJoinPool을 생성하고 있는데 parallelism = -1 의 값이 들어간 상태이다.

그렇게 쭉 진행해서 현재 초록줄 상태까지 왔다.

저기까지는 -1 값이 들어가있지만 이제 살펴보면 Runtime.getRuntime().availableProcessors() - 1 의 값으로 할당되는 것을 볼 수 있다. 

ForkJoinPool.java

이렇게 되니 parallelism에 9가 할당된 것을 볼 수 있다.

그리고 현재 mode 변수에는 parallelism 값으로 초기화되는 것을 볼 수 있다.

이렇게 만들어진 ForkJoinPool을 아까 스태틱 필드였던 common에 넣어지게 된다.

ForkJoinPool.java

그럼 마지막으로 Math.max(common.mode & SMASK, 1); 이 남았다.

& 연산자는 2진수 비교로 둘 다 비트가 1이 존재하면 1이 나오게 되는 것인데,

SMASK의 값은 0xffff이므로 10진수로 65535값이고 2진수로는 1111 1111 1111 1111 값이다.

common.mode는 9이므로 2진수로는 0000 0000 0000 1001 이다.

결국 common.mode의 값이 그대로 나오게 되는 것이다.

그러면 이제 9와 1 중 더 큰 것은 9 이므로 COMMON_PARALLELISM은 9로 초기화가 된다.

 

결론적으로 ForkJoinPool의 commonPool(공용풀)은 컴퓨터에서 사용 가능한 논리적 CPU 코어 수보다 하나 적은 값으로 할당되고 있는 것이다.

그렇기 때문에 (main + ForkJoinPool)을 병렬로 실행할 수 있으므로 모든 CPU 코어를 사용할 수 있다.

(이렇게 나의 궁금증이 풀렸다.)

 

 

 

 

3. 비교

(Baeldung 사이트 참고)

• 서로 다른 크기의 데이터 집합을 가지고 비교
• JMH 벤치마킹을 사용하여 분석
• 테스트 환경은 AMD A10 PRO 2.1Ghz 쿼드 코어 프로세서와 JDK 1.8.0_221 사용

 

그렇다면 1000이상의 배열 사이즈를 가진 배열을 생성해서 비교해보자.

int size = 1500;
int[] numbers = new int[size];
Random random = new Random();

// 1500개를 랜덤한 값으로 채움
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));

System.nanoTime()으로 나노초로 정밀하게 비교해보았다.

계속해서 돌려본 결과 1500개일 때도 parallelSort가 더 좋은 결과를 보였다.

 

 

 

 

4. 결론

위 성능 결과를 참고해보면 배열의 크기가 10,000부터 약 2배의 성능 차이가 보인다.

물론 값에 따라 성능차이가 다르겠지만 결과적으로 10,000부터는 parallelSort()가 성능이 더 좋다는 것이다.

반대로 1,000 이하일 경우 sort()가 더 빠른것을 볼 수 있다.

 

 

 

 

---

https://www.baeldung.com/java-arrays-sort-vs-parallelsort