How ForkJoinPool works

The idea of divide and conquer

Decompose a problem of size N into K sub-problems of smaller size, which are independent of each other and have the same properties as the original problem. By finding the solution to the subproblem, you can get the solution to the original problem.

step:

Decomposition: Divide the problem to be solved into several smaller problems of the same type
Solution: When the sub-problems are divided into small enough sizes, use simpler methods to solve them.
Merge: According to the requirements of the original problem, the solutions to the sub-problems are merged layer by layer to form the solution to the original problem.

Merge sort

Merge Sort is a sorting algorithm based on the divide and conquer idea. Merge sort divides a large array into two equal-sized subarrays, sorts each subarray separately, and then merges the two subarrays into a large sorted array.

Single thread example:

1. Sort 20 million arrays

public class MergeSort {

    public static int[] mergeSort(int[] arrays, int len) {
        int mid = arrays.length / 2;
        // Termination condition
        if (mid <= len) {
            Arrays.sort(arrays);
            return arrays;
        }
        // Split the task
        int[] left = Arrays.copyOfRange(arrays, 0, mid);
        int[] right = Arrays.copyOfRange(arrays, mid, arrays.length);
        // Calculate subtasks separately
        left = mergeSort(left, len);
        right = mergeSort(right, len);
        // Combine subtask results
        return merge(left, right);
    }

    // Merge two sorted arrays
    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int leftIndex = 0, rightIndex = 0, resultIndex = 0;
        while (leftIndex < left.length & amp; & amp; rightIndex < right.length) {
            if (left[leftIndex] <= right[rightIndex]) {
                result[resultIndex + + ] = left[leftIndex + + ];
            } else {
                result[resultIndex + + ] = right[rightIndex + + ];
            }
        }
        while (leftIndex < left.length) {
            result[resultIndex + + ] = left[leftIndex + + ];
        }
        while (rightIndex < right.length) {
            result[resultIndex + + ] = right[rightIndex + + ];
        }
        return result;
    }
}

Time-consuming results

ForkJoinPool

Principle

The Fork/Join framework is a framework provided by JAVA7 for executing tasks in parallel. It is a framework that divides large tasks into several small tasks, and finally summarizes the results of each small task to obtain the results of the large task.

ForkJoinPool is based on the thread pool implemented by the Fork/Join framework, mainly using the divide-and-conquer algorithm and the work-stealing algorithm.

Task segmentation: Divide large tasks into smaller tasks with smaller granularity, allowing more threads to participate in execution

Task stealing: Make full use of idle threads and reduce competition through task stealing

Constructor

public ForkJoinPool(int parallelism, ForkJoinWorkerThreadFactory factory, UncaughtExceptionHandler handler, boolean asyncMode) { this(checkParallelism(parallelism), checkFactory(factory), handler, asyncMode ? FIFO_QUEUE : LIFO_QUEUE, "ForkJoinPool-" + nextPoolId() + "-worker-"); checkPermission(); }

parallelism: number of parallel threads

factory: Create a thread factory

handler: exception handler

asycnMode: queue working mode. true: first in first out; false: last in first out

Usage examples

Inherit the ForkJoinTask class and implement the compute method

Recursive operations provide two encapsulating abstract classes RecursiveAction and RecursiveTask

If you don’t need a return value, use RecursiveAction. If you don’t need a return value, use RecursiveTask.

Example 1: ForkJoin multi-threaded merge sort

@Getter public class MergeSortTask extends RecursiveAction { private final int len; private int[] arrays; public MergeSortTask(int len, int[] arrays) { this.len = len; this.arrays = arrays; } @Override protected void compute() { int mid = arrays.length / 2; // Termination condition if (mid <= len) { Arrays.sort(arrays); return; } // Split the task int[] left = Arrays.copyOfRange(arrays, 0, mid); int[] right = Arrays.copyOfRange(arrays, mid, arrays.length); //Create subtask MergeSortTask leftTak = new MergeSortTask(len, left); MergeSortTask rightTak = new MergeSortTask(len, right); //Multi-threading subtasks invokeAll(leftTak, rightTak); // Combine subtask results arrays = MergeSort.merge(leftTak.getArrays(), rightTak.getArrays()); } }

operation result:

Example. ForkJoin multi-threaded merge and sum

@Getter public class MergeSumTask extends RecursiveTask<Long> { private final int len; private int[] arrays; public MergeSumTask(int len, int[] arrays) { this.len = len; this.arrays = arrays; } @Override protected Long compute() { int mid = arrays.length / 2; // Termination condition if (mid <= len) { return MergeSum.sum(arrays); } // Split the task int[] left = Arrays.copyOfRange(arrays, 0, mid); int[] right = Arrays.copyOfRange(arrays, mid, arrays.length); //Create subtask MergeSumTask leftTak = new MergeSumTask(len, left); MergeSumTask rightTak = new MergeSumTask(len, right); //Multi-threading subtasks leftTak.fork(); rightTak.fork(); // Combine subtask results return leftTak.join() + rightTak.join(); } }

Execution results: It is recommended to directly use a single thread for the sum operation.

Notes

To avoid submitting a large number of blocking tasks, it is recommended to use separate thread pools for blocking tasks and non-blocking tasks.

Avoid calling links that are too deep, which may lead to stack overflow. For example, recursive calculation of the Fibonacci sequence will throw an exception.

If it is a pure function operation, consider using ForkJoin

The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge. Java skill treeControl execution processfor138432 people are learning the system