线程的并行合并排序/比 Seq 慢很多/.合并排序.帮助 [英] Parallel Merge Sort with threads /much/ slower than Seq. Merge Sort. Help
问题描述
^ 这是我对并行归并排序的实现.基本上我所做的是，对于每个拆分，前半部分由一个线程处理，而后半部分是顺序的(即)说我们有一个包含 9 个元素的数组，[0..4] 由线程 1，[0..1] 由线程 2 处理，[5..6] 由线程 3 处理(请查看源代码以进行澄清).
^ This is my implementation of parallel merge sort. Basically what I do is, For every split, the first half is handled by a thread whereas the second half is sequential (i.e.) say we have an array of 9 elements, [0..4] is handled by Thread 1, [0..1] is handled Thread 2, [5..6] is handled by thread 3 (Look at the source code for clarification).
其他一切都保持不变，比如合并.但问题是，这比归并排序慢得多，甚至比普通冒泡排序还要慢！我的意思是 25000 个整数的数组.我不确定瓶颈在哪里:它是互斥锁吗?是合并吗?
Everything else stays the same, like Merging. But the problem is, this runs much slower than merge sort, even slower than normal bubble sort! And I mean for an array of 25000 int's. I'm not sure where the bottleneck is: Is it the mutex locking? Is it the merging?
关于如何加快速度的任何想法?
Any ideas on how to make this faster?
推荐答案
您正在创建大量线程，每个线程只做很少的工作.要对 25000 个整数进行排序，您需要创建大约 12500 个线程来生成其他线程并合并它们的结果，以及大约 12500 个线程，每个线程只对 两个 整数进行排序.
You are creating a large number of threads, each of which then only does very little work. To sort 25000 ints you create about 12500 threads that spawn other threads and merge their results, and about 12500 threads that only sort two ints each.
创建所有这些线程的开销远远超过并行处理带来的收益.
The overhead from creating all those threads far outweighs the gains you get from parallel processing.
为避免这种情况，请确保每个线程都有合理的工作量.例如，如果一个线程发现它只需要对 <10000 个数字进行排序，它可以简单地使用普通的归并排序对它们进行排序，而不是产生新的线程.
To avoid this, make sure that each thread has a reasonable amount of work to do. For example, if one thread finds that it only has to sort <10000 numbers it can simply sort them itself with a normal merge sort, instead of spawning new threads.
这篇关于线程的并行合并排序/比 Seq 慢很多/.合并排序.帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
