Fibonacci on Java ExecutorService работает быстрее последовательно, чем параллельно

Я пробую службу исполнителя на Java и написал следующий код для запуска Фибоначчи (да, массово рекурсивную версию, просто чтобы подчеркнуть службу исполнителя).

Удивительно, но он будет работать быстрее, если я установлю для nThreads значение 1. Это может быть связано с тем, что размер каждой «задачи», отправляемой службе-исполнителю, очень мал. Но все же это должно быть то же число, если я установлю nThreads на 1.

Чтобы увидеть, может ли доступ к общим переменным Atomic вызвать эту проблему, я закомментировал три строки комментарием «см. текст» и посмотрел на системный монитор, чтобы увидеть, сколько времени занимает выполнение. Но результаты такие же.

Любая идея, почему это происходит?

Кстати, я хотел сравнить это с аналогичной реализацией с Fork/Join. Это оказывается намного медленнее, чем реализация F/J.

public class MainSimpler {
    static int N=35;
    static AtomicInteger result = new AtomicInteger(0), pendingTasks = new AtomicInteger(1);
    static ExecutorService executor;

    public static void main(String[] args) {
        int nThreads=2;
        System.out.println("Number of threads = "+nThreads);
        executor = Executors.newFixedThreadPool(nThreads);
        Executable.inQueue = new AtomicInteger(nThreads);
        long before = System.currentTimeMillis();
        System.out.println("Fibonacci "+N+" is ... ");
        executor.submit(new FibSimpler(N));
        waitToFinish();
        System.out.println(result.get());
        long after = System.currentTimeMillis();        
        System.out.println("Duration: " + (after - before) + " milliseconds\n");
    }

    private static void waitToFinish() {
        while (0 < pendingTasks.get()){
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        executor.shutdown();
    }
}



class FibSimpler implements Runnable {
    int N;
    FibSimpler (int n) { N=n; }

    @Override
    public void run() {
        compute();
        MainSimpler.pendingTasks.decrementAndGet(); // see text
    }

    void compute() {
        int n = N;
        if (n <= 1) {
            MainSimpler.result.addAndGet(n); // see text
            return;
        }
        MainSimpler.executor.submit(new FibSimpler(n-1));
        MainSimpler.pendingTasks.incrementAndGet(); // see text
        N = n-2;
        compute();  // similar to the F/J counterpart
    }
}

Время работы (приблизительно):

  • 1 поток: 11 секунд
  • 2 потока: 19 секунд
  • 4 потока: 19 секунд

Обновление: я заметил, что даже если я использую один поток внутри службы-исполнителя, вся программа будет использовать все четыре ядра моей машины (каждое ядро ​​​​в среднем использует около 80%). Это может объяснить, почему использование большего количества потоков внутри службы-исполнителя замедляет весь процесс, но почему эта программа использует 4 ядра, если внутри службы-исполнителя активен только один поток?


java parallel-processing executorservice
person Mahdi    schedule 30.11.2012    source источник
comment
Как сказано в моем [связанном вопросе] [1], я подозреваю, что это связано со сборкой мусора. [1]: stackoverflow.com/questions/13645428/   -  person Mahdi    schedule 30.11.2012

Ответы (1)


arrow_upward
2
arrow_downward

Возможно, это связано с тем, что размер каждой «задачи», отправляемой в службу-исполнитель, очень мал.

Это, безусловно, так, и в результате вы в основном измеряете накладные расходы на переключение контекста. Когда n == 1, нет переключения контекста и, следовательно, производительность выше.

Но все же это должно быть то же число, если я установлю nThreads на 1.

Я предполагаю, что вы имели в виду «выше 1».

Вы сталкиваетесь с проблемой жесткой конкуренции за блокировку. Когда у вас есть несколько потоков, блокировка result постоянно оспаривается. Потоки должны ждать друг друга, прежде чем они смогут обновить result, и это их замедляет. Когда есть только один поток, JVM, вероятно, обнаруживает это и выполняет исключение блокировки, то есть фактически не выполняет никакой блокировки.

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

person Confusion    schedule 30.11.2012
comment
Как я уже упоминал в тексте, я проверил вашу теорию, удалив доступ к общим переменным. Время выполнения не меняется (сейчас смотрю на системный монитор, чтобы увидеть время выполнения). - person Mahdi; 30.11.2012
comment
Что касается использования задач N/nThreads, я согласен с тем, что вы говорите. Но в целом такое решение может оказаться непростым. Поэтому я действительно хотел бы лучше понять, почему многие мелкие задачи приводят к неблагоприятным последствиям! - person Mahdi; 30.11.2012