并行归并排序与线程/多/比SEQ慢。归并排序。帮帮我 [英] Parallel Merge Sort with threads /much/ slower than Seq. Merge Sort. Help
问题描述
^这是我实现并行归并排序的。基本上我做什么，对于每一个分，上半场是由一个线程来处理，而下半年是顺序（即）说，我们有9个元素的数组，[0..4]是由线程1，[0处理..1]处理线程2，[5..6]被线程处理3（查看源$ C $ C澄清）。
^ 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 INT的数组。我不知道在哪里的瓶颈是：是否有互斥锁？它是合并？
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?
推荐答案
您正在创建大量线程，每个然后只做很少的工作。要你创造约12500线程产生其他线程，并合并他们的成果，并约12500线程排序25000整数只有排序的两个的每一个整数。
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.
要避免这种情况，确保每个线程都有工作，合理数量的事情。例如，如果一个线程发现它只有排序＆LT; 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屋！
