The Fork/Join framework is an implementation of the ExecutorService interface, through which we can implement multiple processes. Fork/Join can be used to recursively split a large task into multiple small tasks, with the goal of making full use of all resources to enhance the performance of the application as much as possible.
Like any ExecutorService interface implementation, Fork/Join also uses thread pools to manage worker threads distributedly. What's unique about the Fork/Join framework is that it uses the work-stealing algorithm. Through this algorithm, worker threads can steal other busy thread tasks to execute when nothing can be done.
The core of the Fork/Join framework is the ForkJoinPool class, a subclass of the AbstractExecutorService class. ForkJoinPool implements the core work-stealing algorithm and can perform ForkJoinTask processing.
Basic usage
The first step in using the Fork/Join framework is to write code that performs fragmented tasks. The code to be written is similar to the following pseudo-code:
If the task is small enough: Execute the task directly else: Cut the task into two small tasks to execute two small tasks and wait for the result
Use the ForkJoinTask subclass to encapsulate the code as above. Usually, some classes provided by JDK are used, including RecursiveTask (this class will return a result) and RecursiveAction.
After preparing the ForkJoinTask subclass, create an object representing all tasks and pass it to an invoke() method of a ForkJoinPool instance.
From blur to clear
To help understand how the Fork/Join framework works, we use a case to illustrate: for example, blurring an image. We represent the image using an integer array, where each numeric value represents the color of a pixel. The blurred image is also represented by an array of the same length.
Executing blur is achieved by processing each pixel representing the picture. Calculate the mean of each pixel and its surrounding pixels (the mean of the three primary colors of red, yellow and blue), and the resulting array of results is the blurred picture. Since the representation of images is usually a large array, the entire process usually takes a lot of time. The Fork/Join framework can be used to leverage the advantages of concurrent processing on multiprocessor systems to speed up. Here is a possible implementation:
package com.zhyea.robin; import java.util.concurrent.RecursiveAction; public class ForkBlur extends RecursiveAction { private int[] mSource; private int mStart; private int mLength; private int[] mDestination; // Handle window size; it needs to be an odd number. private int mBlurWidth = 15; public ForkBlur(int[] src, int start, int length, int[] dst) { mSource = src; mStart = start; mLength = length; mDestination = dst; } protected void computeDirectly() { int sidePixels = (mBlurWidth - 1) / 2; for (int index = mStart; index < mStart + mLength; index++) { // Calculate the average value. float rt = 0, gt = 0, bt = 0; for (int mi = -sidePixels; mi <= sidePixels; mi++) { int mindex = Math.min(Math.max(mi + index, 0), mSource.length - 1); int pixel = mSource[mindex]; rt += (float) ((pixel & 0x00ff0000) >> 16) / mBlurWidth; gt += (float) ((pixel & 0x00000ff00) >> 8) / mBlurWidth; bt += (float) ((pixel & 0x000000ff) >> 0) / mBlurWidth; } // Reorganize the target pixel. int dpixel = (0xff0000000) | (((int) rt) << 16) | (((int) gt) << 8) | (((int) bt) << 0); mDestination[index] = dpixel; } } ....}Now implement the abstract method compute(), in which both fuzzy operations are implemented, and splitting a task into two small tasks is implemented. Here we simply decide whether to execute the task directly or split it into two small tasks based on the length of the array:
protected static int sThreshold = 100000; protected void compute() { if (mLength < sThreshold) { computeDirectly(); return; } int split = mLength / 2; invokeAll(new ForkBlur(mSource, mStart, split, mDestination), new ForkBlur(mSource, mStart + split, mLength - split, mDestination)); }Because the implementation of the above methods is defined in a subclass of RecursiveAction, tasks can be created and run directly in a ForkJoinPool. The specific steps are as follows:
1. Create an object representing the task to be performed:
// src represents an array of pixels of the source image // dst represents the pixels of the generated image ForkBlur fb = new ForkBlur(src, 0, src.length, dst);
2. Create a ForkJoinPool instance that runs the task:
ForkJoinPool pool = new ForkJoinPool();
3. Run the task:
pool.invoke(fb);
The source code also contains some code to create the target image. For details, refer to ForkBlur example.
Standard implementation
To use the Fork/Join framework to execute concurrent tasks on multi-core systems according to custom algorithms, of course, you need to implement custom classes (such as the ForkBlur class we implemented before). In addition, some features of the Fork/Join framework have been widely used in JavaSE. For example, the parallelSort() method of the java.util.Arrays class in Java8 uses the Fork/Join framework. For details, please refer to the Java API documentation.
Another implementation of the Fork/Join framework is under the java.util.streams package, which is also part of the Lambda feature of java8.