ForkJoinPool e RecursiveTask: tarefas recursivas

1. ForkJoinPool: o que é e para que serve

ForkJoinPool — é um pool de threads especial que implementa a abordagem “dividir e conquistar” (divide and conquer). Seu objetivo é paralelizar o trabalho de forma máxima quando uma tarefa grande pode ser dividida em várias subtarefas independentes, executadas em paralelo, e então ter seus resultados combinados.

• Fork (dividir) — a tarefa é dividida em subtarefas.
• Join (juntar) — os resultados das subtarefas são combinados no resultado final.

ForkJoinPool é o coração dos streams paralelos em Java: quando você escreve list.parallelStream(), é ele que é usado por baixo dos panos. Mas você também pode usá-lo diretamente, obtendo mais controle.

Quando o ForkJoinPool é especialmente útil

ForkJoinPool brilha em tarefas que podem ser facilmente divididas em partes independentes: por exemplo, o processamento de arrays muito grandes, quando cada fragmento é processado separadamente e, em seguida, os resultados são combinados.

• A tarefa é fácil de dividir em subtarefas independentes: ordenação, busca, soma.
• As subtarefas têm tamanhos semelhantes e não dependem umas das outras.
• É necessário usar todos os núcleos do processador para obter velocidade máxima.

+---------------------+
|   Tarefa grande     |
+---------------------+
          |
          v
+---------+---------+
|  Subtarefa 1      |
|  Subtarefa 2      |
|  ...              |
+-------------------+
          |
          v
+---------+---------+
|  Resultados       |
+-------------------+

É exatamente assim que funciona “dividir e conquistar”: dividimos — calculamos em paralelo — combinamos.

2. RecursiveTask e RecursiveAction: duas faces da mesma moeda

No ForkJoinPool, as tarefas são definidas por meio de classes especiais que sabem se dividir em subtarefas e combinar resultados. RecursiveTask<T> retorna um resultado, enquanto RecursiveAction — não. Na prática, usa-se mais RecursiveTask para, por exemplo, retornar uma soma, um máximo ou uma contagem.

Para criar tal tarefa, extendemos a classe e implementamos o método compute(). Nele descrevemos a lógica: se a tarefa for pequena — resolvemos imediatamente; se for grande — dividimos em subtarefas, executamos em paralelo com fork() e combinamos os resultados com join(). Assim nasce o paralelismo recursivo natural.

3. Sintaxe e exemplo: cálculo paralelo da soma de um array

Suponha que temos um array grande de números e queremos somar seus elementos rapidamente.

Etapa 1. Classe da tarefa

import java.util.concurrent.RecursiveTask;

public class ArraySumTask extends RecursiveTask<Long> {
    private static final int THRESHOLD = 1_000; // Limite para dividir a tarefa
    private final int[] array;
    private final int start, end;

    public ArraySumTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Long compute() {
        // Se a tarefa for pequena — calculamos diretamente
        if (end - start <= THRESHOLD) {
            long sum = 0;
            for (int i = start; i < end; i++) {
                sum += array[i];
            }
            return sum;
        } else {
            // Dividimos a tarefa em duas subtarefas
            int mid = (start + end) / 2;
            ArraySumTask leftTask = new ArraySumTask(array, start, mid);
            ArraySumTask rightTask = new ArraySumTask(array, mid, end);

            // Disparamos as subtarefas em paralelo
            leftTask.fork(); // Assíncrono
            long rightResult = rightTask.compute(); // Síncrono
            long leftResult = leftTask.join(); // Aguardamos a esquerda terminar

            // Combinamos o resultado
            return leftResult + rightResult;
        }
    }
}

• Se a tarefa for pequena (menor que o limite THRESHOLD) — somamos com um loop comum.
• Se for grande — dividimos em duas; uma é iniciada de forma assíncrona via fork(), a outra é computada de forma síncrona via compute(), e então combinamos com join().

Etapa 2. Execução da tarefa via ForkJoinPool

import java.util.concurrent.ForkJoinPool;

public class ForkJoinSumDemo {
    public static void main(String[] args) {
        int[] numbers = new int[10_000_000];
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = 1; // Para simplificar — a soma deve ser igual ao comprimento do array
        }

        ForkJoinPool pool = new ForkJoinPool(); // Padrão — de acordo com o número de núcleos

        ArraySumTask task = new ArraySumTask(numbers, 0, numbers.length);

        long result = pool.invoke(task); // Execução da tarefa

        System.out.println("Soma dos elementos do array: " + result);
    }
}

Como isso funciona?

• ForkJoinPool decide sozinho quantas threads usar (normalmente — igual ao número de núcleos).
• A tarefa é dividida automaticamente em subtarefas, cada uma podendo ser executada em um núcleo separado.
• O desempenho geralmente é superior ao do código sequencial (especialmente com muitos dados e em sistemas multinúcleo).

4. Como o ForkJoinPool funciona: um pouco “por baixo do capô”

Work-stealing (roubo de trabalho)

ForkJoinPool implementa o “roubo de trabalho”: se uma thread ficar sem tarefas, ela “rouba” trabalho de outra. Isso garante balanceamento de carga eficiente e uso pleno de todos os núcleos.

Algoritmo básico

• A tarefa principal é dividida em subtarefas.
• As subtarefas são colocadas em filas especializadas.
• As threads pegam tarefas de suas filas e, quando as esvaziam, “procuram” trabalho nas filas vizinhas.
• Quando tudo termina, os resultados são combinados.

Diagrama de funcionamento

flowchart TD
    A[Tarefa principal] --> B1[Subtarefa 1]
    A --> B2[Subtarefa 2]
    B1 --> C1[Tarefa pequena 1]
    B1 --> C2[Tarefa pequena 2]
    B2 --> C3[Tarefa pequena 3]
    B2 --> C4[Tarefa pequena 4]
    C1 --> D[Combinação dos resultados]
    C2 --> D
    C3 --> D
    C4 --> D

5. RecursiveAction — quando não é necessário retornar resultado

Se você precisa apenas executar algo em paralelo e não retornar resultado, use RecursiveAction. Exemplos típicos — paralelizar o preenchimento de um array, impressão, ordenação “in-place” etc.

import java.util.concurrent.RecursiveAction;

public class PrintTask extends RecursiveAction {
    private static final int THRESHOLD = 100;
    private final int[] array;
    private final int start, end;

    public PrintTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if (end - start <= THRESHOLD) {
            for (int i = start; i < end; i++) {
                System.out.print(array[i] + " ");
            }
        } else {
            int mid = (start + end) / 2;
            invokeAll(
                new PrintTask(array, start, mid),
                new PrintTask(array, mid, end)
            );
        }
    }
}

6. Prática: busca paralela do valor máximo em um array

import java.util.concurrent.RecursiveTask;

public class MaxFindTask extends RecursiveTask<Integer> {
    private static final int THRESHOLD = 1000;
    private final int[] array;
    private final int start, end;

    public MaxFindTask(int[] array, int start, int end) {
        this.array = array;
        this.start = start;
        this.end = end;
    }

    @Override
    protected Integer compute() {
        if (end - start <= THRESHOLD) {
            int max = array[start];
            for (int i = start + 1; i < end; i++) {
                if (array[i] > max) max = array[i];
            }
            return max;
        } else {
            int mid = (start + end) / 2;
            MaxFindTask left = new MaxFindTask(array, start, mid);
            MaxFindTask right = new MaxFindTask(array, mid, end);
            left.fork();
            int rightResult = right.compute();
            int leftResult = left.join();
            return Math.max(leftResult, rightResult);
        }
    }
}

Execução:

import java.util.concurrent.ForkJoinPool;

public class ForkJoinMaxDemo {
    public static void main(String[] args) {
        int[] array = new int[5_000_000];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int)(Math.random() * 1_000_000);
        }

        ForkJoinPool pool = new ForkJoinPool();
        MaxFindTask task = new MaxFindTask(array, 0, array.length);

        int max = pool.invoke(task);

        System.out.println("Valor máximo: " + max);
    }
}

7. Vantagens e limitações do ForkJoinPool

Vantagens

• Balanceamento automático de carga. O work-stealing permite usar todos os núcleos de forma eficiente.
• Comodidade. Não é preciso criar e gerenciar threads manualmente.
• Alto desempenho. Especialmente em tarefas grandes e sistemas multinúcleo.
• Flexibilidade. Você pode dividir as tarefas em quantas partes forem necessárias.

Limitações

• Forte acoplamento entre subtarefas. Se as subtarefas esperam com frequência umas pelas outras, o ganho diminui.
• Tarefas pequenas demais. A sobrecarga de divisão/sincronização pode “comer” a vantagem.
• Efeitos colaterais. Não altere variáveis compartilhadas sem sincronização — você terá race condition.
• Aplicabilidade. Bom para tarefas divisíveis em partes independentes.

8. Erros comuns ao trabalhar com ForkJoinPool e RecursiveTask

Erro nº 1: divisão da tarefa fina demais. Se o limite (THRESHOLD) for muito pequeno, haverá muitas tarefinhas — o custo de criação e sincronização superará o ganho do paralelismo. Experimente com o limite: valores ideais costumam estar na casa dos milhares ou dezenas de milhares de elementos.

Erro nº 2: uso de variáveis mutáveis compartilhadas. Se as subtarefas escreverem em uma variável comum sem sincronização — você terá condições de corrida (race condition). Retorne o resultado via compute() e combine apenas em join().

Erro nº 3: uso incorreto de fork/join. Esqueceu de chamar fork() ou join() — e a subtarefa não será executada em paralelo ou o resultado “se perderá”. Observe atentamente a ordem das chamadas.

Erro nº 4: executar ForkJoinTask fora do ForkJoinPool. Se você simplesmente chamar compute() na tarefa, ela será executada na thread atual, sem paralelismo. Para a “mágica” de verdade, use pool.invoke() ou pool.submit().

Erro nº 5: ignorar exceções. Se ocorrer uma exceção na tarefa, ela aparecerá ao chamar join() ou invoke(). Não deixe de tratar erros.

Erro nº 6: usar ForkJoinPool para tarefas com bloqueios. ForkJoinPool não é apropriado para tarefas que bloqueiam com frequência (espera de I/O etc.). Nesses casos, prefira ExecutorService.