Java странное несоответствие производительности

Question

У меня есть простой рекурсивный метод поиска в глубину. При каждом вызове он проверяет, находится ли он в листе, в противном случае он расширяет текущий узел и вызывает себя для дочерних элементов.

Я пытаюсь сделать это параллельно, но замечаю следующую странную (для меня) проблему.

Я измеряю время выполнения с помощью System.currentTimeMillis ().

Когда я разбиваю поиск на несколько подпоисков и добавляю общее время выполнения, я получаю большее число, чем последовательный поиск. Я измеряю только время выполнения, отсутствие связи или синхронизации и т. Д. Я ожидаю получить то же время, когда добавляю время подзадач. Это происходит, даже если я просто запускаю одну задачу за другой, то есть без потоков. Если я просто разбиваю поиск на несколько подзадач и запускаю подзадачи одну за другой, у меня больше времени. Если я добавлю количество вызовов методов для подзадач, я получу тот же номер, что и при последовательном поиске. Итак, в основном, в обоих случаях я делаю одинаковое количество вызовов методов, но получаю разное время.

Я предполагаю, что некоторые начальные вызовы методов или что-то еще вызвано механизмом JVM. Есть идеи, что это может быть? Например, один последовательный поиск занимает около 3300 мс. Если я разбью его на 13 задач, это займет 3500 мсек.

Мой метод выглядит так:

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);
}

Проблема в том, что totalTime увеличивается с num_tasks, и я ожидаю, что он останется прежним, потому что переменная method_calls останется прежней.

Answer 1

Я ожидаю увидеть использованные темы. Примерно так:

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);
    }

}

Answer 2

Вы должны усреднить числа за более длинные пробеги.Во-вторых, точность currentTimeMillis может быть недостаточной, вы можете попробовать использовать System.nanoTime ().

Answer 3

Добавление системного времени для нескольких потоков кажется странной идеей.Либо вас интересует время до завершения обработки, и в этом случае добавление не имеет смысла, либо использование процессора, и в этом случае вы должны рассчитывать только тогда, когда поток действительно запланирован на выполнение.

Вероятно, случается так, что, по крайней мере, часть времени, больше потоков готовы к выполнению, чем система имеет ядра процессора, и планировщик переводит один из ваших потоков в спящий режим, что приводит к более длительному завершению,Имеет смысл, что этот эффект усугубляется тем больше потоков, которые вы используете.(Даже если ваша программа использует меньше потоков, чем у вас ядер, другие программы (например, ваша среда разработки, ...) могут).

Если вы заинтересованы в использовании процессора, вы можете запросить ThreadMXBean.getCurrentThreadCpuTime

Answer 4

Как и во всех языках программирования, всякий раз, когда вы вызываете процедуру или метод, вы должны передать среду, инициализировать новую, выполнить инструкции программы, вернуть значение в стек и, наконец, сбросить предыдущую среду.Это стоило немного!Создайте поток, который стоит еще больше!

Я полагаю, что если вы увеличите дерево исследований, вы получите выгоду от распараллеливания.