C++에서 병렬 정렬 알고리즘의 성능 비교

서버 코드를 점검하다가 작은 알고리즘부터 하나씩 개선하고 있다.

병렬 프로그래밍을 조사하던 중 정렬 알고리즘에서도 최적화 여지가 있다는 것을 알게 되어 테스트해보았다.

기존 코드는 std::sort를 사용하고 있었다. 이를 concurrency::parallel_sort로 바꿀 수 있었지만, PPL은 비표준인 데다 Windows에서만 동작하는 코드였다. ChatGPT는 concurrency::parallel_sort 대신 std::sort에 std::execution::par를 조합하는 방식을 추천해주었다. (C++17 이상에서만 유효하다.)

테스트 코드

기존의 std::sort와 std::sort + std::execution::par를 비교하는 코드를 작성했다.

#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <execution>
#include <iostream>
#include <locale>

int main( void )
{
	std::vector<int> vec;

	for ( auto i = 0; i < 1000000; ++i )
		vec.push_back( i );

	std::random_device rd;
	std::mt19937 engine( rd() );
	std::shuffle( vec.begin(), vec.end(), engine );

	std::vector<int> vec1 = vec;
	std::vector<int> vec2 = vec;

	{
		// 시간 측정 시작
		auto start = std::chrono::high_resolution_clock::now();

		std::sort( vec1.begin(), vec1.end(), []( auto lhs, auto rhs )
		{
			return lhs < rhs;
		} );

		// 시간 측정 끝
		auto end = std::chrono::high_resolution_clock::now();

		// 경과 시간 계산 (단위: 마이크로초)
		auto duration = std::chrono::duration_cast<std::chrono::microseconds>( end - start );

		std::cout << "실행 시간: " << duration.count() << " 마이크로초" << std::endl;
	}

	{
		// 시간 측정 시작
		auto start = std::chrono::high_resolution_clock::now();

		std::sort( std::execution::par, vec1.begin(), vec1.end(), []( auto lhs, auto rhs )
		{
			return lhs < rhs;
		} );

		// 시간 측정 끝
		auto end = std::chrono::high_resolution_clock::now();

		// 경과 시간 계산 (단위: 마이크로초)
		auto duration = std::chrono::duration_cast<std::chrono::microseconds>( end - start );

		std::cout << "실행 시간: " << duration.count() << " 마이크로초" << std::endl;
	}

	return 0;
}

배열에 int 값을 여러 개 넣고 섞은 후 다시 정렬하는 데 걸리는 시간을 측정하는 코드이다.

테스트 결과

단위는 마이크로초(μs)이다.

원소 개수	std::sort	std::sort + std::execution::par
100	20	61
300	70	98
500	111	86
1,000	258	128
10,000	3,302	461
100,000	41,760	4,022
1,000,000	509,795	48,412
10,000,000	5,024,498	564,703
100,000,000	68,011,136	5,948,772

테스트 환경은 Intel Core i5-12400F 2.5GHz, 64GB 메모리, Visual Studio 2019 x64이다.

표를 보면 원소 개수가 300개 이하일 때는 기본 std::sort가 더 빠르다. 500개 정도부터 std::execution::par의 효과가 나타나기 시작하고, 1,000개에서는 약 절반, 10,000개 이상에서는 약 1/10 수준으로 시간이 줄어든다.

결론

원소 개수 300개 미만은 std::sort, 300개 이상은 std::sort + std::execution::par를 사용하는 것이 좋다.

아래와 같은 템플릿 함수를 만들어 사용 중이다. std::sort와 동일한 인터페이스를 유지하면서 원소 개수에 따라 정렬 전략을 자동으로 선택한다.

template<class RandomIt, class Compare>
void RzSort( RandomIt first, RandomIt last, Compare comp )
{
	auto size = std::distance( first, last );
	if ( size <= 0 )
		return;

	if ( size < 1000 )
		std::sort( first, last, comp );
	else
		std::sort( std::execution::par, first, last, comp );
}