퀵정렬 Phtread 사용하면 더 느린이유?

[코리올란(121.172)]

엉아덜

일반 퀵정렬과  정렬할때 배열 갯수만큼 쓰레드를 만들어서 만든 쓰레드 퀵정렬 두개 만들어봤는데

일반은 0.008sec

쓰레드는 0.064sec초가 나오더라고

쓰레드가 더 빠를줄알았는데 왜그런겨

[씹죶(116.33)]

배열개수만큼 만들어서 문제 스레드 존나 많네

[씹죶(116.33)]

스레드는 코어개수(제일좋음)~코어개수16배 이내로 만들어라 그리고 병렬처리를 원하면 언어에서 스레드말고 멀티코어 지원하는거 쓰고 task 어쩌고 하는 이름이 대부분일게다

[숲속의 참치(roqkqwnsmstkfka)]

스레드 두개 정도만 해서 해봐 퀵소트가 1단계 진행 할때마다 Left Right 구간으로 둘로 쪼개지는데 두스레드간 상대 스레드가 놀고 있으면 분할된걸 던지는 식으로 하면된다. 상대가 안놀고 있으면 스택에 보관하고. 그런식으로 해봤는데 동기화 비용, 균일하게 분할되지 않는 다는 점이 있어, 2배에 조금 못미치게 빨라진다. 그리고 소팅하는 시점에 프로세서2개를 사용 가능 해야겠지

[숲속의 참치(roqkqwnsmstkfka)]

하지만 omp나 threadpool을 std::sort에 적용하면 더 많은 프로세서를 사용할 수 있겠지

[씹죶(116.33)]

곰곰히 생각해보니 퀵소트를 멀티스레드로 생각을 해보질 않아서 잘 몰랐거만, 꽤 좋은 주제네 병렬처리 공부하는데 도움이 좀 되겠군 , 재귀적으로 함수 호출하는 퀵소트 로직을 그대로 살리는 경우는 작업이 두단계로 나뉜다. 1. 남아있는 스레드 개수에 작업을 할당할수 있도록 퀵소트를 처음 몇단계 진행하며 구간을 구한다 (이때는 원스레드) 2. 스레드 개수만큼 구간이 모두 할당되었으면 개별 스레드들이 자신이 맡은 구간을 정렬한다. 3. 할당할 스레드 개수가 2의 배수이면 가장 좋지만 (완전랜덤 배열일때 N개로 분할됨) 아닐경우 효율이 떨어짐 (예: 스레드 6개인 경우 구간 6개 배열80개를 정렬시 10개 10개 10개 10개 20개 20개) 정렬할 개수가 무지막지하게 커지면 위 참치말대로

[씹죶(116.33)]

위 참치말대로 스레드 풀링을 사용하면 더 균등하게 작업 분할할수 있는데 재귀호출 퀵소드 로직을 버리고 다시 로직짜야될걸?? 설계가 존나 더 복잡해질껄? ㅋㅋ

[숲속의 참치(roqkqwnsmstkfka)]

해봤는대 대충 1.5~1.9배 빠르더라 1개 스레드 이용할때보다

[숲속의 참치(roqkqwnsmstkfka)]

omp나 스레드풀을 std 기본sort를 수정하면 별로 할것도 없을거야

[코리올란(121.172)]

병렬 공부중이라 소스 개선보다는 왜 그런지 이유를 알고 싶어 ㅇㅇ

[ㄱㄴㄴ(175.198)]

소스좀 보자 이유야 여러가지니