Javaの奇妙なパフォーマンスの不一致

Question

私は単純な再帰的な方法、深さの最初の検索している。それぞれの呼び出しで、それがリーフにあるかどうかをチェックし、そうでなければ、現在のノードを展開し、子でそれ自身を呼び出します。

私はそれを平行にしようとしていますが、私は次の奇妙な（私にとっては）問題に気付いています。

私はSystem.currentTimeMillis（）で実行時間を測定します。

検索をいくつかのサブアークに分割し、実行時間を合計すると、順次検索よりも大きな数字が得られます。私は実行時間、通信や同期などを測定しません。私はサブタスクの時間を追加するときに同じ時間を得ることが期待されます。これは、たとえスレッドを使わずに他のタスクを実行したとしても発生します。検索をいくつかのサブタスクに分割して、サブタスクを順番に実行すると、より大きな時間が得られます。 サブタスクのメソッド呼び出しの数を追加すると、私は逐次検索と同じ番号を取得します。だから、基本的には、どちらの場合でも同じ数のメソッド呼び出しを行いますが、私は異なる時を得ます。

最初のメソッド呼び出しやJVMメカニズムに起因する何らかのオーバーヘッドがあると思います。どのようなアイデアでもありますか？ たとえば、1回の順次検索には約3300ミリ秒かかります。私が13のタスクに分割すると、合計時間は3500msになります。

私の方法は、次のようになります。私はそれを呼び出すたび

private static final int dfs(State state) { 
    method_calls++; 
    if(state.isLeaf()){ 
      return 1; 
    } 
    State[] children = state.expand(); 
    int result = 0; 
    for (int i = 0; i < children.length; i++) { 
      result += dfs(children[i]); 
    } 
    return result; 
} 

、私はこのようにそれを行う：

for(int i = 0; i < num_tasks; i++){ 
    long start = System.currentTimeMillis(); 
    dfs(tasks[i]); 
    totalTime += (System.currentTimeMillis() - start); 
} 

問題はnum_tasksとTOTALTIME増加であり、私はので、同じとどまることを期待しますmethod_calls変数は同じままです。

Answer 1

長時間実行した場合には平均をとる必要があります。第2に、currentTimeMillisの精度が十分でない場合があります。System.nanoTime（）を使用してみてください。

Answer 2

プロシージャまたはメソッドを呼び出すときはいつでも、環境をプッシュし、新しいものを初期化し、プログラムの命令を実行し、スタック上の値を返し、最後に前の環境をリセットする必要があります。それは少しコストがかかります！さらにスレッドコストを作成！

リサーチツリーを拡大すると、並列化のメリットがあると思います。

Answer 3

複数のスレッドのシステムクロック時間を追加するのは奇妙な考えです。処理が完了するまでの時間に興味がある場合は、追加が意味をなさないか、CPU使用率になります。この場合、実際にスレッドの実行がスケジュールされたときだけカウントする必要があります。

システムのCPUよりも多くのスレッドが実行可能な状態になっており、スケジューラがスレッドの1つをスリープ状態にしてしまい、完了に時間がかかることがあります。この効果は、使用するスレッドが増えるほど悪化します。 （あなたのプログラムがあなたのコアよりもスレッドを少なくしても、他のプログラム（あなたの開発環境など）はそうかもしれません）。

CPU使用率に興味があるなら、あなたは私がスレッドを使用見ることを期待したいThreadMXBean.getCurrentThreadCpuTime

Answer 4

を照会したいかもしれません。このような何か：このような実行可能なビットで

import java.util.concurrent.Executor; 
import java.util.concurrent.ExecutorService; 
import java.util.concurrent.Executors; 


public class Puzzle { 

    static volatile long totalTime = 0; 
    private static int method_calls = 0; 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     final int num_tasks = 13; 
     final State[] tasks = new State[num_tasks]; 
     ExecutorService threadPool = Executors.newFixedThreadPool(5); 
     for(int i = 0; i < num_tasks; i++){ 
      threadPool.submit(new DfsRunner(tasks[i])); 
     } 
     try { 
     threadPool.shutdown(); 
     threadPool.awaitTermination(1, TimeUnit.SECONDS); 
     } catch (InterruptedException e) { 
      System.out.println("Interrupted"); 
    } 
     System.out.println(method_calls + " Methods in " + totalTime + "msecs"); 
    } 

    static final int dfs(State state) { 
     method_calls++; 
     if(state.isLeaf()){ 
       return 1; 
     } 
     State[] children = state.expand(); 
     int result = 0; 
     for (int i = 0; i < children.length; i++) { 
       result += dfs(children[i]); 
     } 
     return result; 
    } 
} 

：

public class DfsRunner implements Runnable { 
    private State state; 
    public DfsRunner(State state) { 
     super(); 
     this.state = state; 
    } 
    @Override 
    public void run() { 
     long start = System.currentTimeMillis(); 
     Puzzle.dfs(state); 
     Puzzle.totalTime += (System.currentTimeMillis() - start); 
    } 

}