易失性陣列和多線程排序

我正在考慮使用一個易失性數組進行多線程排序的實現。比方說，我有一個長度爲N的數組，以及將排序數組的子範圍的M個線程。這些子範圍是不相交的。然後，在主線程中，我將合併部分排序的數組。易失性陣列和多線程排序

示例代碼：

final int N = .... 
volatile MyClass[] array = new MyClass[N]; 
//... fill array with values 

void sort(){ 
    MyThread[] workers = new MyThread[M]; 
    int len = N/M; //length of the sub-range 
    for(int i=0;i<M;++i){ 
     workers[i] = new MyThread(i*len, (i+1)*len); 
     workers[i].start(); 
    } 
    for(int i=0;i<M;++i)workers.join(); 

    //now synchronization in memory using "happens before" 
    //will it work? 
    array = array; 

    //...merge sorted sub-ranges into one sorted array 
} 

private class MyThread extends Thread{ 

final int from; 
final int to; 

public MyThread(int from, int to){ ..... } 

public void run(){ 
    //...something like: quicksort(array, from, to); 
    //...without synchronization, ranges <from, to> are exclusive 
}

同時運行的線程，因爲該陣列的子範圍是不相交的，我不需要在存儲器中的同步。我想在完成線程後執行一次同步。請問數組的更新版本（在主線程中看到）是否包含工作線程中所做的所有更改？

如果此解決方案有效，是否對大型表有效？

非常感謝您的幫助。

編輯：

我跑的測試。無論使用volatile關鍵字，我都會收到正確的結果。但是對於易失性陣列來說，執行時間會延長几倍（約M倍）。

來源

2014-07-17 Bronowic

N和M有多大？您的目標系統可以在本地運行多少個線程？線程之間上下文切換的開銷可能會消耗大部分多線程分類階段的加速。你會留下很多複雜的代碼和（可能）性能提升。 –

N約爲10^6，M是處理器內核的數量 – Bronowic

使用簡單的'Collections.sort（）對一百萬個元素進行排序對於整數平均需要大約400ms，對於我的機器上整數的十六進制字符串平均需要650ms。除非'MyClass'有一個超級複雜的比較邏輯，否則你會看幾秒鐘，如<< 5s。你需要這樣做有多快？ –

不是一個答案，只是一些想法：

沒有這樣的事情作爲一個易變的數組。只有字段可以是不穩定的。您已經聲明瞭一個名爲「array」的易失性字段，並使用對數組對象的引用對其進行了初始化。

您看起來像是在期待陳述array = array充當內存屏障。我不知道它是否會或者不會，或者答案取決於什麼編譯器，什麼JVM以及您使用的是什麼操作系統。也許有人比我能回答更專家。

我不喜歡它，原因有兩個：一是它看起來像一個沒有操作。這是一些其他程序員的邀請，他們不明白你想要做什麼，並通過刪除代碼來「清理」代碼。像這樣一個棘手的聲明應該包含在一個名稱解釋技巧的函數中。

二是，該語句的函數與該字段引用的數組無關。使用volatile int字段或揮發性somethingelse字段會更好，因爲明顯是與數組沒有關係，因此提請注意以下事實：重要的事情不是字段的值。

更新：根據布賴恩戈茨，一個聲明不會做你想做的。您需要的是每個工作線程在完成工作後更新易失性字段，然後在它嘗試查看工作人員的結果之前，需要主線程讀取易失性字段。

另一方面......你是否需要屏障？工作線程全部終止並且master加入（）編輯它們還不夠嗎？再次，也許有人比我更專業可以回答。

來源

2014-07-17 21:54:33

是的你是對的，表不需要變動，我想我可以使用揮發性的'旗'字段。我不確定這裏的屏障是否必要。請閱讀我的編輯。 – Bronowic

你在做什麼看起來非常混亂，並建議，可能無法按預期工作。

如果你使用Java8，那麼也許並行排序是給你的。否則 -

對單個陣列進行排序，並行是一個恐怖節目。如果您創建一個新的排序元素數組，並行排序相當簡單。

創建子數組的對象（最終需要這樣做）。將每個對象傳遞給一個線程。讓線程並行排序對象。完成所有排序後，將已排序的對象合併到一個新數組中。

這意味着需要更多的內存，但它很容易，你不必擔心易失性或同步。

來源

2014-07-17 22:25:27 edharned

感謝您的建議，我考慮將我的數組分成子數組。我需要揮發性障礙嗎？ – Bronowic

不可以。你並沒有同時訪問任何字段。 – edharned

謝謝你的澄清。 – Bronowic

易失性陣列和多線程排序

回答

相關問題