JavaNotes

Фреймворк fork и join

2 min read

Fork/Join

Fork/Join из JDK 7 предназначен для CPU-bound задач, которые рекурсивно делятся на независимые части.

  • RecursiveTask<V> возвращает значение.
  • RecursiveAction результата не возвращает.
  • ForkJoinPool распределяет подзадачи через work stealing: простаивающий worker забирает работу из очереди занятого.

Сумма диапазона

final class SumTask extends RecursiveTask<Long> {
    private static final int THRESHOLD = 10_000;
    private final long[] values;
    private final int from;
    private final int to; // exclusive
 
    SumTask(long[] values, int from, int to) {
        this.values = values;
        this.from = from;
        this.to = to;
    }
 
    @Override
    protected Long compute() {
        int length = to - from;
        if (length <= THRESHOLD) {
            long sum = 0;
            for (int i = from; i < to; i++) sum += values[i];
            return sum;
        }
 
        int middle = from + length / 2;
        SumTask left = new SumTask(values, from, middle);
        SumTask right = new SumTask(values, middle, to);
 
        left.fork();
        long rightResult = right.compute();
        return left.join() + rightResult;
    }
}
 
long sum = ForkJoinPool.commonPool()
        .invoke(new SumTask(values, 0, values.length));

Одна ветка вычисляется текущим worker, другая fork-ается: это дешевле, чем бездумно fork-ать обе и ждать.

Порог разбиения

Слишком маленький THRESHOLD создает больше задач и overhead очередей, чем работы. Слишком большой оставляет ядра без работы. Порог подбирают benchmark-ом на реальных данных.

Fork/Join плохо подходит для длительного блокирующего I/O: заблокированный worker уменьшает доступный параллелизм. Для таких задач нужен отдельный executor; специальный ManagedBlocker существует, но усложняет код.

join() у ForkJoinTask отличается от Thread.join(): возвращает результат подзадачи и может помочь пулу выполнить другую работу.

На собеседовании

  • Что такое work stealing? Свободный worker забирает подзадачу у занятого.
  • RecursiveTask и RecursiveAction? С результатом и без результата.
  • Почему нужен threshold? Чтобы цена разбиения не превысила работу.
  • Почему I/O вреден common pool? Блокирует ограниченных worker-ов.
  • Зачем fork одной ветки, compute другой? Меньше scheduling overhead, текущий поток не простаивает.

Graph View

Backlinks