Divide and conquer in real life

The idea of divide and rule, as the name implies, divide and rule. For example, if the ancient king wanted to govern the world well, it was not enough for him alone. He also needed the assistance of his ministers to divide the world into sections, and those under him were assigned to take charge, and then those under him were assigned to his subordinates.

Divide-and-conquer has many applications in algorithms, such as MapReduce of big data, merge algorithm and quicksort algorithm. JUC also provides a parallel computing framework called Fork/Join to handle divide-and-conquer situations, similar to the stand-alone version of MapReduce.

Fork/Join

Divide and conquer is divided into two stages. In the first stage, tasks are decomposed into small tasks until the small tasks can be easily calculated and returned.

In the second stage, the results of each small task are combined and returned to get the final result. Fork is a decomposition task and Join is a merge result.

The Fork/Join framework consists of two main parts: ForkJoinPool and ForkJoinTask.

ForkJoinPool

This is the thread pool that governs divide-and-conquer tasks. It shares an implementation of the consumer-producer pattern with the ThreadPoolExecutor thread pool mentioned in the previous article, but has some differences. A ThreadPoolExecutor thread pool has only one task queue, whereas ForkJoinPool has multiple task queues. Tasks submitted through ForkJoinPool invoke or Submit or Execute are assigned to different task queues according to certain rules, and the task queue is double-ended.

Execute async, invoke async, return result (will block) Submit async, return result (Future)

Why a double-endian queue? This is because the ForkJoinPool has a mechanism by which a worker thread can steal tasks from the end of another busy queue when the queue is idle. The busy queue then heads out tasks to its corresponding worker thread. So the two ends are in order and there’s no jostling.

ForkJoinTask

This is a divide-and-conquer task, the equivalent of a Runnable. It is an abstract class whose core methods are fork and Join. The fork method is used to execute a subtask asynchronously, and the Join method blocks the current thread until the subtask returns.

ForkJoinTask has two subclasses called RecursiveAction and RecursiveTask. These two subclasses are also abstract classes that perform divide-and-conquer tasks recursively. Each subclass has an abstract method compute. The difference is that RecursiveAction does not return a value and RecursiveTask does.

Simple application

The classic example of a recursive implementation of divide-and-conquer is the Fibonacci sequence.

Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34… Formula: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n >=3, n∈N*)

public static void main(String[] args) { ForkJoinPool forkJoinPool = new ForkJoinPool(4); Fibonacci = new Fibonacci(20); long startTime = System.currentTimeMillis(); Integer result = forkJoinPool.invoke(fibonacci); long endTime = System.currentTimeMillis(); System.out.println("Fork/join sum: " + result + " in " + (endTime - startTime) + " ms."); Static class Fibonacci extends RecursiveTask<Integer> {final int n; Fibonacci(int n) { this.n = n; } @Override protected Integercompute() {
            if (n <= 1) {
                return n;
            }
            Fibonacci f1 = new Fibonacci(n - 1);
            f1.fork(); 
            Fibonacci f2 = new Fibonacci(n - 2);
            returnf2.compute() + f1.join(); }}Copy the code

If both tasks are forked, f1.fork(), f2.fork(), f2.join(), f1.join() will cause performance problems. The official JDK documentation explains this, if you are interested, you can go and study it.

I recommend using invokeAll

            Fibonacci f1 = new Fibonacci(n - 1);
            Fibonacci f2 = new Fibonacci(n - 2);
            invokeAll(f1,f2);
            return f2.join() + f1.join();
Copy the code

Method invokeAll (available in multiple versions) performs the most common form of parallel invocation: forking a set of tasks and joining them all.

This is what the official API documentation says, so use invokeAll every day. The invokeAll invokes the first incoming task to the current thread, and all other tasks are forked to the work queue, thus using the current thread to execute the task. Here is the invokeAll source code

public static void invokeAll(ForkJoinTask<? >... tasks) { Throwable ex = null; int last = tasks.length - 1;for(int i = last; i >= 0; --i) { ForkJoinTask<? > t = tasks[i];if (t == null) {
                if (ex == null)
                    ex = new NullPointerException();
            }
            else if(i ! = 0) // all except the first fork. fork();else if(t.toinvoke () < NORMAL && ex == null) // Invoke ex = t.geexception (); }for(int i = 1; i <= last; ++i) { ForkJoinTask<? > t = tasks[i];if(t ! = null) {if(ex ! = null) t.cancel(false);
                else if(t.doJoin() < NORMAL) ex = t.getException(); }}if(ex ! = null) rethrow(ex); }Copy the code

conclusion

Fork/Join is a framework formed by using the idea of divide and conquer, which can be used in many scenes in daily life. ForkJoinPool, the core of the framework, makes better use of resources because of its task queuing and stealing features.

Finally, I wish you a happy May Day!

If there are mistakes welcome to correct! Personal public account: Yes training level guide

There are relevant interview information waiting to receive