線程合併排序比串行實現慢

對於學校，我們得到了創建多線程應用程序的任務。我們選擇了合併排序的多線程實現。線程合併排序比串行實現慢

然而，我們無法設法使其工作速度超過串行執行。

我已經試過如下：

實現無限線（代碼示例1）（是極爲緩慢的）
實現以有限的線程（代碼示例2）（4個線程最大 - 還真慢）
執行使用Parallel.Invoke（代碼示例3）（仍然較慢）
複雜的實施也與並行合併函數（只是羞恥慢）

當我在Visual Studio（Instrumentation part）中使用分析工具時，我發現所調用函數的時間安排，並且線程化解決方案總是比串行實現慢得多。

我看不出有任何可能的原因。

（例如：以500萬個的數字進行排序;串行執行：16.717,17;並行：20.259,97;只有1額外的線程結果）

我測試了它在兩臺機器上我自己：

英特爾酷睿2四核Q9450 2.66GHz的@
英特爾酷睿i7 Q720 @ 1.60GHz的

我不能爲我的生活弄清楚這怎麼可能，應該不就是加快ü過程？

如果有人能夠幫助我，我會非常樂意。

代碼示例1：

ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
Thread thread = new Thread(new ThreadStart(pMerge.parallel_merge)); 
thread.Start(); 

ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
pMerge2.parallel_merge(); 
thread.Join();

代碼示例2：

if(depthRemaining > 0) 
{ 
    ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
    thread thread = new Thread(new ThreadStart(pMerge.parallel_merge)); 
    thread.Start(); 
    ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
    pMerge2.parallel_merge(); 
    thread.Join(); 
} 
else 
{ 
    ParallelMerge pMerge = new ParallelMerge(T, p1, q1 -1, p2, q2-1, A, p3); 
    pMerge.parallel_merge(); 
    ParallelMerge pMerge2 = new ParallelMerge(T, q1 + 1, r1, q2, r2, A, q3 + 1); 
    pMerge.parallel_merge(); 
}

代碼示例3：

if (depthRemaining > 0) 
{ 
    Parallel.Invoke(
    () => threaded_merge_sort(getallen, p, q, depthRemaining-1)); 

    threaded_merge_sort(getallen, q + 1, r, 0); 
} 
else 
{ 
    threaded_merge_sort(getallen, p, q, 0); 
    threaded_merge_sort(getallen, q+1, r, 0); 
}

來源

2012-05-14 Arne Claerebout

使用TPL（Parallel.Invoke）或線程池。 –

最後，排序問題的瓶頸是I/O操作，所以並行計算不會帶來很大的性能改進。 – Cristiano

50000數字不是很多。連續線程創建/連接意味着一大堆可避免的開銷。如果你有一本教科書說使用創建它們的線程請求，然後加入（）等待結果，請將其刻錄。按照@HenkHolterman的建議查看ThreadPool/TPL。 –

看來問題不在於代碼，而是從VS的分析工具。

-Arne Claerebout

來源

2012-10-23 19:03:45 Servy

你在報告什麼單位的時間？

開始一個新線程是一個'慢'的操作。使用多線程對非常短列表進行排序/合併可能會稍慢一些。

如果您只是將數字列表的長度減半，程序運行速度會更快嗎？如果不是，你的代碼根本不會縮放。

回答這個問題沒有實際的代碼實現是有點難。

來源

2012-05-14 09:06:41 CodingBarfield

使用的變量時間以毫秒爲單位，我也注意到我錯過了幾個零。應該是5000000個數字。我在pastebin上發佈我的代碼：http://pastebin.com/LrSKrSW2 –

線程合併排序比串行實現慢

回答

相關問題