多核CPU中，利用多線程進行排序中出現了一些奇怪的現象，不知道其背後的原因是什麼，希望有人能給予解答？

抱歉了，是我冒泡寫錯了。貽笑大方了。

再次謝謝大家的幫助：）

——————————————————

這是一個利用多線程進行排序的HW。

單線程部分的要求是首先利用快排中的Partition，將數組進行分塊。要求是進行三次Partition，然後在最底層中進行冒泡排序。而多線程部分就是將Partition的部分和底層冒泡的部分用線程來實現，具體要求是首先創建15個線程並wait，然後第一個線程對數組進行Partition並且post接下來的兩個線程進行Partition。直至最後底層，然後進行冒泡排序。

我的問題是，在我最初寫的程序中

https://github.com/Cxgoal/hw/blob/tray2/os/3/main.cpp

編譯執行後，發現並沒有實現並行的效果。無論是多大的測試集，CPU始終只佔用了一個，運行效果也與單線程無異。然後我Google這一現象，有人提及有可能是false sharing的問題。於是我修改了我的程序，https://github.com/Cxgoal/hw/blob/tray2/os/main2.cpp

然後貌似解決了並行的問題，CPU的4個核心也是全部佔用，但是卻發現排序的時間特別長，甚至比單核心的更加長。

我想了幾天，也google了很久，但是還是不清楚上述兩個問題的原因是什麼？

所以希望大家能夠幫我看一下這個問題，幫我指出問題所在。

謝謝啦:)

系統環境 Linux Mint 18.1 Serena， x86 64-bit,

編譯器 g++ (Ubuntu 5.4.0-6ubuntu1~16.04.5) 5.4.0 20160609

編譯命令 g++ main.cpp -pthread

都沒說到點子上……他的多線程可能有點小毛病，但並不是這所謂「奇怪現象」的原因。

來這位正在學習計算機的同學，我來告訴你一個事情，一個程序寫完了，是要測試的。測試首先是正確，然後才是效率。我相信你壓根沒管你的結果對不對吧？但凡你寫了一個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&*(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%+。

先說個無關的但很重要的問題。

再說並行，並行編程不是這樣編的。你這樣效率只會比單線程低，這是必然的。

舉個例子，如果一個cpu只有一個核心，只支持真正意義上的一個線程。你現在用4個線程，來對一百萬個數做加法，效率肯定比用單線程對一百萬個數做加法低，因為單核單線程的CPU，你多線程只是表面並行，實際還是串列，還多了cpu切換線程耗費的好多時間片。

上述例子，如果用一個四核四線程來寫呢，四個線程分別加，最後加在一起，效率可以提高四倍。因為是真正並行的。

你開的線程數那麼多，效果就像第一個例子中的那樣，程序跑起來時，15線程必然要搶佔CPU的那幾個核，所以效果堪憂。你這是假並行。