Framework Fork/Join do Java | W3Docs Learn Java

Um pool de threads comum é ótimo para "muitas tarefas independentes." Não é ótimo para "uma grande tarefa que pode ser dividida recursivamente em versões menores de si mesma." Para esse segundo formato — trabalho de divisão e conquista — o Java tem um executor especializado: o ForkJoinPool. É o pool por trás de parallelStream, CompletableFuture.supplyAsync (quando nenhum executor é fornecido), e qualquer código que você escreva com RecursiveTask/RecursiveAction.

O truque que torna o ForkJoinPool especial é o work-stealing: cada worker tem seu próprio deque, e quando seu próprio deque está vazio ele rouba uma tarefa do final do deque de outro worker. O resultado é balanceamento de carga automático — workers rápidos ajudam workers lentos sem nenhuma coordenação.

Quando usá-lo

Fork/join é a ferramenta certa para:

Divisão e conquista recursiva. Quicksort, mergesort, travessia de árvore, algoritmos numéricos recursivos, multiplicação de matrizes por halvamento.
Trabalho intensivo de CPU que pode ser paralelizado em partes aproximadamente iguais.
Trabalho cuja granularidade se adapta: divide se o bloco é grande, executa diretamente se é pequeno.

É a ferramenta errada para:

Trabalho limitado por I/O. Um worker bloqueado não rouba — e o tamanho padrão do pool é a contagem de CPUs. Bloqueie um worker e você perdeu um núcleo.
Tarefas independentes não relacionadas. Um ThreadPoolExecutor comum é mais simples e igualmente rápido para esse formato.
Tarefas que dependem de um agendamento externo fixo. Use ScheduledExecutorService.

Um modelo mental útil: se você usaria um parallelStream para isso, fork/join é o mesmo formato expresso diretamente. (Fork/join chegou no Java 7; parallelStream no Java 8 foi construído sobre ele.)

As três classes

ForkJoinPool pool;                                    // the executor
RecursiveTask<V>;                                     // an abstract task returning V
RecursiveAction;                                      // an abstract task returning nothing

Você estende RecursiveTask ou RecursiveAction, sobrescreve compute(), decide dentro de compute() se deve dividir ou executar o trabalho diretamente, e chama fork()/join() nas subtarefas.

class Sum extends RecursiveTask<Long> {
  private static final int THRESHOLD = 1000;
  private final long[] data;
  private final int lo, hi;

  Sum(long[] data, int lo, int hi) {
    this.data = data; this.lo = lo; this.hi = hi;
  }

  @Override
  protected Long compute() {
    int len = hi - lo;
    if (len <= THRESHOLD) {
      long s = 0;
      for (int i = lo; i < hi; i++) s += data[i];
      return s;
    }
    int mid = lo + len / 2;
    Sum left  = new Sum(data, lo, mid);
    Sum right = new Sum(data, mid, hi);
    left.fork();                                      // schedule left to run on another worker
    long rightResult = right.compute();               // run right on this worker (avoid extra task)
    long leftResult  = left.join();                   // wait for left
    return leftResult + rightResult;
  }
}

ForkJoinPool pool = new ForkJoinPool();
long total = pool.invoke(new Sum(data, 0, data.length));

O formato — verificar threshold → dividir → fazer fork de uma metade → calcular a outra → join — é o idioma canônico de fork/join. O truque de "calcular uma metade aqui em vez de fazer fork das duas" evita criar uma tarefa desnecessária e é um ganho pequeno, mas real.

O threshold importa

A decisão mais importante: quando parar de dividir. Um threshold muito pequeno cria milhares de tarefas para partes triviais — o overhead domina o trabalho. Muito grande e você não consegue usar totalmente os núcleos — muitos workers ficam ociosos enquanto um processa um bloco grande.

Regras práticas:

O corpo da tarefa deve levar pelo menos 10 microssegundos. Abaixo disso, o overhead de gerenciamento de tarefas é comparável ao trabalho.
Torne o threshold uma constante que você pode ajustar. 100, 1000, 10000 são típicos para arrays primitivos; o número correto depende do custo por elemento.
Para entradas muito pequenas, reverta para uma implementação puramente serial. O overhead de divisão e fork é desperdiçado em entradas que cabem no cache.

`fork()`, `join()`, `invoke()`

As três operações em uma RecursiveTask:

Método	Comportamento
`fork()`	Agenda a tarefa no pool atual; retorna imediatamente
`join()`	Aguarda a tarefa e retorna seu resultado (ou lança o que ela lançou)
`invoke()`	Combinação de `fork` + `join` para esta thread — síncrono
`compute()`	Executa o corpo diretamente na thread chamadora (sem fork)

No padrão acima, left.fork(); right.compute(); left.join(); faz a coisa certa — faz fork de uma metade para outro worker, executa a outra metade aqui, depois aguarda o fork terminar.

Você não deve escrever left.fork(); right.fork(); left.join(); right.join();. O lado direito é forked e o worker atual aguarda — não há thread de execução disponível para realmente executar right até que o worker chegue ao join. A combinação desperdiça o slot de tempo do worker atual.

O pool comum

ForkJoinPool.commonPool() é um pool compartilhado em toda a JVM, dimensionado para Runtime.getRuntime().availableProcessors() - 1 por padrão. Ele alimenta:

Stream.parallelStream()
CompletableFuture.supplyAsync(supplier) (a sobrecarga sem executor)
Arrays.parallelSort()

Você pode configurar o tamanho do pool comum via a propriedade do sistema java.util.concurrent.ForkJoinPool.common.parallelism na inicialização da JVM. Você não deve usar o pool comum para I/O — uma única chamada bloqueante prende um worker que toda a JVM compartilha.

Work-stealing em imagens

worker-1 deque:  [t1 t2 t3 t4]            (it forked these; t4 just got pushed)
worker-2 deque:  []                       (empty — workers steal)
worker-3 deque:  [t10 t11]                (still has its own)

worker-2 finds its deque empty; steals t1 from the BOTTOM of worker-1's deque
worker-1 keeps pulling its own tasks from the TOP

A fila de extremidade dupla é o coração do design: workers empurram e puxam de uma extremidade (LIFO — localidade de referência para acertos de cache), ladrões pegam da outra extremidade (FIFO — contenção mínima com o proprietário). É por isso que fork/join tem tão bom desempenho: workers raramente disputam as estruturas de dados uns dos outros, mesmo sob carga pesada.

Um exemplo prático: soma paralela vs. serial

O programa abaixo soma um array de 10 milhões de elementos de duas formas — loop serial e recursão fork/join — e imprime o tempo de relógio de parede para cada um.

java— editable, runs on the server

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ForkJoinDemo {
  public static void main(String[] args) {
    int n = 10_000_000;
    long[] data = new long[n];
    for (int i = 0; i < n; i++) data[i] = (i * 2654435761L) & 0xFFFF;     // some non-trivial values

int cores = Runtime.getRuntime().availableProcessors();
    System.out.println("cores: " + cores);
    System.out.println("common pool parallelism: " + ForkJoinPool.commonPool().getParallelism());

// 1. Serial baseline
    long t1 = System.nanoTime();
    long serialSum = 0;
    for (int i = 0; i < n; i++) serialSum += data[i];
    long serialMs = (System.nanoTime() - t1) / 1_000_000;
    System.out.printf("%nserial:    sum=%d   %d ms%n", serialSum, serialMs);

// 2. Fork/Join
    long t2 = System.nanoTime();
    long pjSum = ForkJoinPool.commonPool().invoke(new Sum(data, 0, n));
    long pjMs = (System.nanoTime() - t2) / 1_000_000;
    System.out.printf("fork/join: sum=%d   %d ms   (about %.1fx faster)%n",
        pjSum, pjMs, Math.max(1.0, (double) serialMs / Math.max(1, pjMs)));

System.out.println("\nsums equal? " + (serialSum == pjSum));

// 3. Threshold matters: too-small THRESHOLD makes it slower
    long t3 = System.nanoTime();
    long tinySum = ForkJoinPool.commonPool().invoke(new SumTiny(data, 0, n));
    long tinyMs = (System.nanoTime() - t3) / 1_000_000;
    System.out.printf("fork/join (threshold=10): sum=%d   %d ms  -- excessive task overhead%n",
        tinySum, tinyMs);
  }

// Sensible threshold
  static class Sum extends RecursiveTask<Long> {
    static final int THRESHOLD = 100_000;
    private final long[] data;
    private final int lo, hi;
    Sum(long[] data, int lo, int hi) { this.data = data; this.lo = lo; this.hi = hi; }
    @Override protected Long compute() {
      int len = hi - lo;
      if (len <= THRESHOLD) {
        long s = 0;
        for (int i = lo; i < hi; i++) s += data[i];
        return s;
      }
      int mid = lo + len / 2;
      Sum left  = new Sum(data, lo, mid);
      Sum right = new Sum(data, mid, hi);
      left.fork();
      long r = right.compute();
      long l = left.join();
      return l + r;
    }
  }

// Threshold WAY too small — millions of micro-tasks; overhead dominates
  static class SumTiny extends RecursiveTask<Long> {
    static final int THRESHOLD = 10;
    private final long[] data;
    private final int lo, hi;
    SumTiny(long[] data, int lo, int hi) { this.data = data; this.lo = lo; this.hi = hi; }
    @Override protected Long compute() {
      int len = hi - lo;
      if (len <= THRESHOLD) {
        long s = 0;
        for (int i = lo; i < hi; i++) s += data[i];
        return s;
      }
      int mid = lo + len / 2;
      SumTiny left  = new SumTiny(data, lo, mid);
      SumTiny right = new SumTiny(data, mid, hi);
      left.fork();
      long r = right.compute();
      long l = left.join();
      return l + r;
    }
  }
}

O que tirar da execução:

A versão fork/join foi várias vezes mais rápida que o loop serial. Em uma máquina com N núcleos, o limite superior é aproximadamente N× — o número real foi menor porque a JVM, o GC e outras threads da JVM também queriam CPU, e o trabalho de threshold não é perfeitamente balanceado. Ainda assim, um speedup substancial por algumas linhas de código recursivo.
Ambas as somas eram iguais. Esse é o teste de correção de partição e fusão: cada folha somou sua fatia não sobreposta; a etapa de combinação (l + r) as adicionou; sem dupla contagem ou condições de corrida de dados porque cada folha escreveu em sua própria variável local.
A variante SumTiny com threshold 10 foi mais lenta que o loop serial. Com 10M de elementos divididos em blocos de 10, você cria cerca de 2M de tarefas — e o overhead de gerenciamento de tarefas supera o trabalho real de adição. O threshold é um botão real; faça benchmark com entrada representativa.
O padrão left.fork(); long r = right.compute(); long l = left.join(); usou uma tarefa a menos do que fork(); fork(); join(); join(); usaria. O worker atual tem tempo livre durante o compute() — usá-lo para uma das metades economiza uma alocação de tarefa inteira. Esse é o ganho pequeno, mas cumulativo em muitas cargas de trabalho reais.
ForkJoinPool.commonPool() foi o executor usado nesta demonstração. Para uma execução única, o pool comum é adequado. Para um programa de longa duração que mistura trabalho fork/join com chamadas parallel de stream e futures assíncronas, dê à carga de trabalho pesada de fork/join seu próprio pool — o pool comum é destinado a rajadas curtas, não a computação pesada em estado estável.

O que vem a seguir

O próximo capítulo, Coleções Concorrentes do Java, aborda as estruturas de dados projetadas para serem usadas por múltiplas threads — ConcurrentHashMap, CopyOnWriteArrayList, BlockingQueue, e o restante de java.util.concurrent.

Prática

Dentro de `compute()` de uma `RecursiveTask`, você tem duas subtarefas `left` e `right`. Qual padrão de chamada é o idioma canônico de fork/join?

`left.fork(); long r = right.compute(); long l = left.join();` — faz fork de uma metade, calcula a outra no worker atual, join do fork`left.fork(); right.fork(); long l = left.join(); long r = right.join();` — fork em ambas e join em ambas`left.invoke(); right.invoke();` — invoca execuções síncronas em paralelo automaticamente`left.start(); right.start(); left.join(); right.join();` — igual à API de `Thread` simples