多核CPU中，利用多线程进行排序中出现了一些奇怪的现象，不知道其背后的原因是什么，希望有人能给予解答？ 第1页

都没说到点子上……他的多线程可能有点小毛病，但并不是这所谓「奇怪现象」的原因。

来这位正在学习计算机的同学，我来告诉你一个事情，一个程序写完了，是要测试的。测试首先是正确，然后才是效率。我相信你压根没管你的结果对不对吧？但凡你写了一个Sanity Check，比如在写到文件的时候看看是不是升序输出，你就会发现你这个程序的问题——你 BubbleSort() 写错了。

是的，你这奇怪的现象背后的原因既不是和多核多线程相关，也不是和什么奇怪的瓶颈相关，你就是冒泡排序写错了而已……

       void BubbleSort(DATATYPE * arr, POSITION left_index, POSITION right_index){     struct timeval start, end;     int sec=0, usec=0;     gettimeofday(&start,0);     for(POSITION i=left_index; i<right_index+1; i++){         for(POSITION j=left_index; j<right_index+1-i; j++){             if(*(arr+j)>*(arr+j+1)){                 Exchange(arr+j, arr+(j+1));             }         }     }     gettimeofday(&end,0);     sec = end.tv_sec-start.tv_sec;     usec = end.tv_usec-start.tv_usec;     printf("%f sec.",sec+(usec/1000000.0));     printf("Left Index is %d, Right Index is %d.
", left_index, right_index); }     

这是你的冒泡排序，我们看到第二个for loop，看到问题了么？

这个问题会导致什么咧？会导致当你left_index不是从0开始的时候，冒泡排序不会进行完。而你single thread的时候left_index并不总是0，就导致了你其实后面的排序根本就没排完，不快才怪了。而multi thread的时候，由于你程序的处理方式，left_index总是0，这个错误的函数恰好得到了正确的结果（其实有一处index overflow，能看出来么），所以完整地执行了排序，因此速度比single thread慢非常多。

在修改掉这个 BubbleSort() 的bug之后，在整个程序其他部分完全不动的情况下，multi thread就比single thread快了……但是快的并不明显，这又是为什么？

主要原因是，你的工作分配不均。在你随机把数组分为8份的情况下，multi thread的速度取决于你最大的一份，而平均来看，最大的一份大约是数组长度的40%。但是由于 BubbleSort() 是O(n^2)的算法，所以最大一份所占用的时间平均大概是63%。也就是说，在一切都完美的情况下（CPU支持8线程），你的算法也只能带来平均37%的提升。而多线程编程本身的overhead是不可避免的，所以我在我的电脑上大概能跑出来20-30%的性能提升。

如果你想要成倍的性能提升，在你确定了CPU支持多核的情况下，需要解决两点。

第一，平均分配任务。你现在的算法如果分成八份肯定是很难做到平均的，可以考虑 MergeSort() 。

第二，把 BubbleSort() 换成QuickSort() ，把O(n^2)变成平均O(nlogn)，这样在同样随机的情况下，可以把理论性能提高提升到50%+。