倍数

Question

私は...私のアプローチは正しいと信じていますが、私は100％確信していません。スレッドに関しては、ExecutorServiceの代わりに(new MatrixThread(...)).start()を実行するだけの理由がわかりません。私が間違っているのは何さらに

、私のベンチマーク...アプローチは、古典的なアプローチに対して、古典はずっと高速です...

？

P.S.それ以上の説明が必要な場合は教えてください。

Answer 1

あなたはたくさんのスレッドを作成しています。スレッドを作成するのは高価なだけでなく、CPUバインドされたアプリケーションの場合、使用可能なプロセッサーより多くのスレッドを必要としません（そうした場合、スレッド間の電力切り替えを処理する必要があります。ミスは非常に高価です）。

スレッドをexecuteに送信する必要もありません。必要なのはRunnableです。あなたはこれらの変更を適用することによって、大きなパフォーマンスの向上が得られます：

1. ので、それはmain後にプログラムの実行を継続しない、ExecutorService静的メンバを行い、現在のプロセッサのサイズを、そしてそれをThreadFactoryを送ります終わりました。 （おそらく、むしろ静的なフィールドとして、それを維持するよりも、メソッドのパラメータとして、それを送信するために建築きれいだろう、私は読者の練習として残しておき☺）

   private static final ExecutorService workerPool = 
       Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(), new ThreadFactory() { 
        public Thread newThread(Runnable r) { 
         Thread t = new Thread(r); 
         t.setDaemon(true); 
         return t; 
        } 
       }); 
   

2. MatrixThreadではなくRunnableを実装してください継承するよりもThreadです。スレッドは高価です。 POJOは非常に安いです。 staticにすると、インスタンスを小さくすることができます（非静的クラスは囲むオブジェクトへの暗黙の参照を取得するため）。変化から

   private static class MatrixThread implements Runnable 
   

3. （1）、あなたはもはやawaitTermination（このワーカープールなど）すべてのタスクが終了していることを確認することができます。代わりにsubmitメソッドを使用して、Future<?>を返します。リスト内のすべての未来のオブジェクトを収集し、すべてのタスクをサブミットしたら、リストを反復して、各オブジェクトに対してgetを呼び出します。

あなたmultiply方法は次のようになります。

public Matrix multiply(Matrix multiplier) throws InterruptedException { 
    Matrix result = new Matrix(dimension); 
    List<Future<?>> futures = new ArrayList<Future<?>>(); 
    for(int currRow = 0; currRow < multiplier.dimension; currRow++) { 
     for(int currCol = 0; currCol < multiplier.dimension; currCol++) {    
      Runnable worker = new MatrixThread(this, multiplier, currRow, currCol, result); 
      futures.add(workerPool.submit(worker)); 
     } 
    } 
    for (Future<?> f : futures) { 
     try { 
      f.get(); 
     } catch (ExecutionException e){ 
      throw new RuntimeException(e); // shouldn't happen, but might do 
     } 
    } 
    return result; 
} 

それはシングルスレッドのバージョンよりも高速になりますか？まあ、私の間違いなく恐ろしいボックスでは、マルチスレッド版の値はn < 1024の方が遅いです。

これは面を傷つけるだけです。あなたのメモリ消費量は非常に悪い兆候でO(n²)、ある - 本当のの問題は、あなたがたくさんMatrixThreadのインスタンスを作成することです。内側のforループをMatrixThread.runに移動すると、パフォーマンスが向上するでしょう。craploads（理想的には、ワーカースレッドより多くのタスクを作成しないでください）。

---

編集：私が行うには、より緊急のものを持っているように、私はこれをさらに最適化抵抗することができませんでした。それはまだ大きくないですが、基本的にはマルチスレッドバージョンが、患者のだろう何かを計算することができ

public Matrix multiply(Matrix multiplier) throws InterruptedException { 
    Matrix result = new Matrix(dimension); 
    List<Future<?>> futures = new ArrayList<Future<?>>(); 
    for(int currRow = 0; currRow < multiplier.dimension; currRow++) { 
     Runnable worker = new MatrixThread2(this, multiplier, currRow, result); 
     futures.add(workerPool.submit(worker)); 
    } 
    for (Future<?> f : futures) { 
     try { 
      f.get(); 
     } catch (ExecutionException e){ 
      throw new RuntimeException(e); // shouldn't happen, but might do 
     } 
    } 
    return result; 
} 


private static class MatrixThread2 implements Runnable 
{ 
    private Matrix self, mul, result; 
    private int row, col;  

    private MatrixThread2(Matrix a, Matrix b, int row, Matrix result) 
    {   
     this.self = a; 
     this.mul = b; 
     this.row = row; 
     this.result = result; 
    } 

    @Override 
    public void run() 
    { 
     for(int col = 0; col < mul.dimension; col++) { 
     int cellResult = 0; 
     for (int i = 0; i < self.getMatrixDimension(); i++) 
      cellResult += self.template[row][i] * mul.template[i][col]; 
     result.template[row][col] = cellResult; 
     } 
    } 
} 

：私は、「のみ」O(n)雇用を創出することを、この（コードの...恐ろしく醜い部分）を思い付い待機するのに十分であり、シングルスレッド版よりも高速に処理できます。

Answer 2

ExecutorServiceを使用している場合でも、スレッドの作成にはかなりのオーバーヘッドがあります。私は、あなたがマルチスレッドのアプローチをしている理由が非常に遅いと思うのは、新しいスレッドを作成するのに99％を費やし、実際の数学をやっているのはわずか1％以下です。

通常、この問題を解決するには、一連の操作をまとめて1つのスレッドで実行します。私はこの場合どのように行うのか100％ではありませんが、独自のスレッドで各セルを実行するのではなく、小さな塊（たとえば10個の小さな行列）に行列を分割してスレッド上で実行することをお勧めします。

Answer 3

まず最初に、使用しているクアッドコアのコア数と同じサイズのnewFixedThreadPoolを使用する必要があります.4つ目は、各マトリックスに対して新しいものを作成しないでください。あなたはExecutorServiceの私はまた512

のマトリクスサイズでスレッド版のほぼ一貫してより高速な実行を取得し、静的メンバ変数を作成した場合

、も実行を高速化する代わりに、拡張スレッドのRunnableを実装するMatrixThreadを変更スレッドが私のマシン上で512倍速く2倍速