멀티스레드로 소수 엄청 빨리 구하기

인프런 강의에서 제공된 연습문제를 생각해본 내용입니다.

사실 저 강의 아직 안들었어요..^^

일단 제공된 문제를 기반으로 제 생각으로 구현한 내용입니다. 그래서 비효율적일 수도, 뭔가 잘못되었을 수도 있어요 그래도 개인공부로 적은 내용이니 아 얘가 부족하구나 하고 댓글주시면 매우 감사하겠습니당..

조건

1'000'000 이하의 소수 (1과 자기 자신으로만 나누어 떨어지는 수)의 개수를 구하자.
멀티스레드 환경에서 구하도록 실습!
이외의 조건은 없습니다.

혼자 생각 생각...

산책하며 머리를 샥샥 굴려보자

부끄러우니까 사진으로 첨부
말도 안되는거죠
그래도 일단 올려놔봐요 나중에 보면 제가 작성했다고 생각한 최종 코드도 머저리같을거니까요

일단 소수 구하기 알고리즘

에라토스테네스의 체

소수구하기 알고리즘 하면 가장 먼저 떠오르는거 있잖아요 그래 그거요

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    std::vector<bool> vec(n+1, true);
    
    for (int tgt = 2 ; tgt <= n ; ++tgt)
    {
        // 이미 특정 숫자의 배수이므로, 검사하지 않습니다.
        if (false == vec[tgt]) continue;
        
        // 아래 연산을 하는 순간, 소수로 가정하고 결과값을 1 증가시켜줍니다.
        ++answer;
        
        // 해당 숫자로 나누어 떨어지는 숫자들을 false로 변경합니다.
        for (int loop{tgt * 2} ; loop <= n ; loop += tgt)
            vec[loop] = false;
    }
    return answer;
}

그래서 일단 만들어봐요

1안!!

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
#include <vector>
using namespace std;
using namespace std::chrono_literals;

uint32_t tgtNum{ 1'000'000 };
atomic<uint32_t> counter = 2;
atomic<uint32_t> result = 0;
thread_local uint32_t LCalcNum;
std::vector<bool> flags(tgtNum + 1, true);
mutex myMutex;

uint32_t CalculateInSingle()
{
	std::vector<bool> vec(tgtNum + 1, true);
	vec[0] = false;
	vec[1] = false;
	uint32_t result = 0;

	for (uint32_t num{ 2 }; num <= tgtNum; ++num)
	{
		if (false == vec[num]) continue;
		result++;

		for (uint32_t idx{ num * 2 }; idx <= tgtNum; idx += num)
			vec[idx] = false;
	}
	return result;
}

bool Calculate()
{
	if (tgtNum < LCalcNum)						return false;

	if (false == flags[LCalcNum])				return true;
	
	std::lock_guard<mutex> lock(myMutex);
	for (uint32_t idx{ LCalcNum * 2 }; idx <= tgtNum; idx += LCalcNum)
		flags[idx] = false;
	return true;
}

void Process()
{
	while (true)
	{
		LCalcNum = counter.fetch_add(1);
		
		if (false == Calculate())
			break;
	}
}

int main()
{
	auto startSingle = chrono::steady_clock::now();
	cout << "싱글스레드 : " << CalculateInSingle() << endl;
	auto endSingle = chrono::steady_clock::now();
	cout << "싱글스레드 실행 시간: " << chrono::duration_cast<chrono::milliseconds>(endSingle - startSingle).count() << "ms" << endl;

	flags[0] = false;
	flags[1] = false;

	size_t num_threads = thread::hardware_concurrency();
	std::vector<thread> threads;

	auto startMulti = chrono::steady_clock::now();
	for (size_t loop{}; loop < num_threads; ++loop)
		threads.emplace_back(Process);

	for (auto& thread : threads)
		thread.join();

	uint32_t val{};
	for (const bool& flag : flags)
	{
		if (true == flag)
			val++;
	}
	auto endMulti = chrono::steady_clock::now();
	cout << "멀티스레드 : " << val << endl;
	cout << "멀티스레드 실행 시간: " << chrono::duration_cast<chrono::milliseconds>(endMulti - startMulti).count() << "ms" << endl;

	while (true);
}

주요 내용

1. LCalcNum
   thread_local 변수로 각 스레드에서 현재 처리할 수를 얻어와 저장해놓고 사용합니다.
   LCalcNum에 들어갈 변수는 atomic 변수의 fetch_add함수를 이용해서 ㅓㅊ리합니다.
   각 스레드는 1씩 증가해가며 처리할 숫자를 얻어내용.

2. 소수를 구하는 방식
   위에서 말씀드린 대로, 에라토스테네스의 체 방식을 이용합니다.
   flags 벡터의 경우, 한 번 false로 바뀌면 true로 다시 바뀔 일이 없기 때문에 읽을 때에는 lock을 걸지 않습니다.
   다만, 배수들에 대한 flags 처리가 중복될 가능성이 있기 때문에 result는 추후에 한 번에 검사하고 있습니다.

후회안하니

이렇게 하면 어떻게든 처리는 됩니다
다만... 멀티스레드인데 ㅋㅋ 시간이 두 배 걸린다는 점

너 뭐하묘?

왜 오래걸리게?

로직에서 대부분의 시간을 차지하는 것은 배수 처리인데, 이 부분에서 데이터 레이스가 발생할 수 밖에 없으므로 락을 걸어버립니다.
그러면? 사실상 싱글스레드와 크게 다를 바가 없죵

이 상황에서 멀티스레드로 인한 기본적인 오버헤드 + 락에 대한 오버헤드 + 다시 전체탐색을 하는 점 = 당연히 오래걸림 ㅋㅋ

시원하게 수정해부리기

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
#include <vector>
#include <cmath>
using namespace std;
using namespace std::chrono_literals;

uint32_t tgtNum{ 1'000'000 };
thread_local uint32_t LResult = 0;
atomic<uint32_t> result = 0;
mutex myMutex;

uint32_t CalculateInSingle()
{
	std::vector<bool> vec(tgtNum + 1, true);
	vec[0] = false;
	vec[1] = false;
	uint32_t result = 0;

	for (uint32_t num{ 2 }; num <= tgtNum; ++num)
	{
		if (false == vec[num]) continue;
		result++;

		for (uint32_t idx{ num * 2 }; idx <= tgtNum; idx += num)
			vec[idx] = false;
	}
	return result;
}

bool IsPrime(const uint32_t& _num)
{
	if (_num < 2) return false;
	if (2 == _num || 3 == _num) return true;
	if (0 == _num % 2 || 0 == _num % 3) return false;

	uint32_t sqrtNum{ static_cast<uint32_t>(sqrt(_num)) };
	for (uint32_t loop{ 5 }; loop <= sqrtNum; ++loop)
	{
		if (0 == _num % loop) return false;
	}
	return true;
}
void Process(const uint32_t& _startIdx, const uint32_t& _endIdx)
{
	for (uint32_t idx{ _startIdx }; idx <= _endIdx; ++idx)
	{
		if (true == IsPrime(idx))
			++LResult;
	}
	result.fetch_add(LResult);
}

int main()
{
	auto startSingle = chrono::steady_clock::now();
	cout << "싱글스레드 : " << CalculateInSingle() << endl;
	auto endSingle = chrono::steady_clock::now();
	cout << "싱글스레드 실행 시간: " << chrono::duration_cast<chrono::milliseconds>(endSingle - startSingle).count() << "ms" << endl;

	std::vector<thread> threads;
	uint32_t num_threads = thread::hardware_concurrency();
	uint32_t chunk_size = tgtNum / num_threads;

	auto startMulti = chrono::steady_clock::now();
	for (uint32_t loop{}; loop < num_threads; ++loop)
	{
		uint32_t start = loop * chunk_size + 1;
		uint32_t end = (loop == num_threads - 1) ? tgtNum : (loop + 1) * chunk_size;
		threads.emplace_back(Process, start, end);
	}

	for (auto& thread : threads)
		thread.join();
	cout << "멀티스레드 : " << result << endl;
	auto endMulti = chrono::steady_clock::now();
	cout << "멀티스레드 실행 시간: " << chrono::duration_cast<chrono::milliseconds>(endMulti - startMulti).count() << "ms" << endl;

	while (true);
}

결과
싱글스레드 : 78498
싱글스레드 실행 시간: 1056ms
멀티스레드 : 78498
멀티스레드 실행 시간: 42ms

수정한 코드가 빠른 이유?

각 스레드 별로 처리할 숫자를 나눠줬습니다.
물론 뒤에 생성된 스레드일 수록 연산이 더 무거워지겠지만..ㅇㅅㅇ

이렇게 하고, 각 스레드에서 한 행동을 각자 로컬로 가지고 있다가, 행위 연산이 모두 끝나면 atomic 변수에 더해줍니다.

(물론 LResult의 경우, 그냥 지역변수로 선언하면 스택에 올라갑니다. 따라서 스레드마다 고유하게 할당되니까 굳이 thread_local로 선언하지 않아도 정상 작동됩니다.)
thread_local 변수 써보고 싶어서 저렇게 해봤습니다 ㅋㅅㅋ

배운점

싱글스레드에서 빠르다고 멀티스레드에서 무조건 빠른건 아니다.

싱글스레드에서 소수구하기는 무조건 에라토스테네스의 체! 라고 생각해서,, 아무 생각없이 손가락을 쇽쇽 움직였는데..8ㅅ8
이러면 그냥 전체를 락 걸어버리는거랑 얼마 차이가 안나는 것 같은거죠...

왜 느릴까?
생각해보자.

일단 에라토스테네스의 체 방식은, 방문 여부를 담아두는 전역 배열이 필요하다.
각 스레드에서 숫자 한 개씩 처리한다고 했을 때, 전역 배열의 값을 수정해야 하므로 락을 걸어줄 수 밖에 없고,, 그러면 멀티스레드로 수행하는 의미가 전혀 없다.

멀티스레드로 처리할 때는 여러 스레드에서 공유자원에 접근하는 것을 줄이는 것이 중요하다.
솔직히 싱글스레드 로직으로 보면, 누가 봐도 루프돌면서 체크하는게 느리다.
그렇지만 멀티스레드로 처리하려면 사고방식을 약간 옆으로 돌려서? 한 30도 틀어서 생각해야겠다.

어떻게 하면 하나의 스레드에서 최고의 성능을 뽑되, 다른 스레드와의 간섭을 최소화할 수 있을까?
단독 행동을 빠르게 시켜야 한다.
라고 생각해야 하는데,,
최근 싱글스레드만 만지다보니^^;

멀티스레드에 대한 사고를 다시금 깨우치도록 도와주는 간단한 문제였슴미다.