This is the 19th day of my participation in the August More Text Challenge
Fork/Join framework
Fork/Join framework applies the idea of “divide and conquer”, that is, Fork () is used to disassemble molecular tasks and Join () is used to obtain the calculation results of sub-tasks.
- When is the minimum executable task
- When do you split tasks
- When do you summarize the results of a task
Merge sort using the Fork/Join framework
public class MergeSortTask extends RecursiveTask<int[]> { private int array[]; private int n; public MergeSortTask(int[] array, int n) { this.array = array; this.n = n; } @Override protected int[] compute() { if (array.length <= n) { Arrays.sort(array); return array; } else { MergeSortTask task1 = new MergeSortTask(Arrays.copyOf(array, array.length / 2), n); task1.fork(); MergeSortTask task2 = new MergeSortTask(Arrays.copyOfRange(array, array.length / 2, array.length), n); task2.fork(); return merge(task1.join(), task2.join()); } } private static int[] merge(int array1[], int array2[]) { int length1 = array1.length; int length2 = array2.length; int[] result = new int[length1 + length2]; for (int index = 0, index1 = 0, index2 = 0; index < result.length; index++) { int value1 = index1 >= length1 ? Integer.MAX_VALUE : array1[index1]; int value2 = index2 >= length2 ? Integer.MAX_VALUE : array2[index2]; if (value1 < value2) { index1++; result[index] = value1; } else { index2++; result[index] = value2; } } return result; }}Copy the codeForkJoinPool parsing
ForkJoinPool is pooled based on the Fork/Join framework. As shown in the following figure, the submitted tasks are routed to different dual-ended queues (an array of workqueues), one thread for each queue
There are two sources of work: external commits in the even index of the WorkQueue array, and internal forks in the odd index that only threads correspond to, while tasks in other queues are done by work stealing.
Since WorkQueue is a two-ended queue, there must be two consumption methods: FIFO and LIFO. The default is LIFO, which is treated as a stack. When consuming, tasks are fetched from the top and when work is stolen, tasks are fetched from the base, ensuring that large tasks are broken down into smaller tasks first.
In addition, the join operation does not block the thread and puts the blocked task back on the queue to continue processing the next task. The fork-Join framework introduces an “intermediate layer” between the executing thread and the task, allowing the thread to put the blocked task aside and wait until all the subtasks it depends on have been processed before processing the task that is blocked because of the subtask. That is, assuming that task 1 depends on Task 5 (where task 5 is a subtask created by Task 1), task 1 is put aside to perform Task 5.
As shown in Figure 1, 2 channels and 3 layers of fork-join produce 2^3 concurrent threads, that is, K channels and N layers of fork-join produce K^N concurrent threads, so how to determine the depth of recursion is a problem that needs to be considered.
We test sorting a random number group with a length of 1 million, and the minimum number of sorting ranges from 1 to 1 million. The results show that when n=1, the number of tasks takes a long time due to complete segmentation, while when n=2, the number of tasks is immediately reduced to half and the operation is simple, which significantly improves the speed. When n>= length, the task is not segmented at all, which is equivalent to fast sorting by a thread, and the speed slows down significantly.
Specific data of test results
Minimum number of sorts =1, time =76.2
Minimum number of sorts =11, time =39.4
Minimum number of sorts =21, time =36.1
Minimum number of sorts =31, time =36.2
Minimum number of sorts =41, time =37.9
Minimum number of sorts =51, time =36.0
Minimum number of sorts =61, time =66.8
Minimum number of sorts =71, time =44.5
Minimum number of sorts =81, time =36.6
Minimum number of sorts =91, time =37.5
Minimum number of sorts =10000, time =36.4
Minimum number of sorts =20000, time =39.2
Minimum number of sorts =30000, time =29.8
Minimum number of sorts =40000, time =29.7
Minimum number of sorts =50000, time =30.9
Minimum number of sorts =60000, time =28.5
Minimum number of sorts =70000, time =29.6
Minimum number of sorts =80000, time =31.2
Minimum number of sorts =90000, time =29.5
Minimum number of sorts =100000, time =40.0
Minimum number of sorts =110000, time =34.6
Minimum number of sorts =120000, time =29.6
Minimum number of sorts = 130,000, time =34.1
Minimum number of sorts = 140,000, time =52.7
Minimum number of sorts = 150,000, time =33.9
Minimum number of sorts =160000, time =33.3
Minimum number of sorts =170000, time =29.9
Minimum number of sorts =180000, time =34.1
Minimum number of sorts = 190,000, time =32.4
Minimum number of sorts =200000, time =33.3
Minimum number of sorts =210000, time =32.5
Minimum number of sorts =220000, time =32.2
Minimum number of sorts =230000, time =33.9
Minimum number of sorts = 240,000, time =32.3
Minimum number of sorts = 250,000, time =32.8
Minimum number of sorts =260000, time =33.1
Minimum number of sorts =270000, time =34.3
Minimum number of sorts =280000, time =33.9
Minimum number of sorts =290000, time =32.2
Minimum number of sorts =300000, time =41.5
Minimum number of sorts =310000, time =33.0
Minimum number of sorts =320000, time =34.7
Minimum number of sorts =330000, time =34.5
Minimum number of sorts =340000, time =33.2
Minimum number of sorts =350000, time =33.6
Minimum number of sorts =360000, time =32.2
Minimum number of sorts =370000, time =35.1
Minimum number of sorts =380000, time =34.2
Minimum number of sorts =390000, time =32.7
Minimum number of sorts =400000, time =33.0
Minimum number of sorts =410000, time =33.4
Minimum number of sorts =420000, time =34.3
Minimum number of sorts =430000, time =34.2
Minimum number of sorts =440000, time =32.3
Minimum number of sorts =450000, time =34.9
Minimum number of sorts =460000, time =34.3
Minimum number of sorts =470000, time =32.9
Minimum number of sorts =480000, time =34.2
Minimum number of sorts = 490,000, time =34.4
Minimum number of sorts =500000, time =47.0
Minimum number of sorts =510000, time =45.9
Minimum number of sorts =520000, time =50.1
Minimum number of sorts =530000, time =49.2
Minimum number of sorts =540000, time =50.7
Minimum number of sorts =550000, time =46.4
Minimum number of sorts =560000, time =49.6
Minimum number of sorts =570000, time =48.0
Minimum number of sorts =580000, time =46.2
Minimum number of sorts =590000, time =44.8
Minimum number of sorts =600000, time =47.9
Minimum number of sorts =610000, time =49.2
Minimum number of sorts =620000, time =58.5
Minimum number of sorts =630000, time =65.2
Minimum number of sorts =640000, time =55.8
Minimum number of sorts =650000, time =45.9
Minimum number of sorts =660000, time =50.8
Minimum number of sorts =670000, time =44.3
Minimum number of sorts =680000, time =45.6
Minimum number of sorts =690000, time =48.5
Minimum number of sorts =700000, time =45.6
Minimum number of sorts =710000, time =44.7
Minimum number of sorts =720000, time =45.0
Minimum number of sorts =730000, time =46.7
Minimum number of sorts =740000, time =45.9
Minimum number of sorts =750000, time =45.4
Minimum number of sorts =760000, time =45.0
Minimum number of sorts =770000, time =45.2
Minimum number of sorts =780000, time =45.6
Minimum number of sorts =790000, time =50.8
Minimum number of sorts =800000, time =45.9
Minimum number of sorts =810000, time =45.3
Minimum number of sorts =820000, time =47.9
Minimum number of sorts =830000, time =44.0
Minimum number of sorts =840000, time =45.6
Minimum number of sorts =850000, time =47.9
Minimum number of sorts =860000, time =45.5
Minimum number of sorts =870000, time =46.1
Minimum number of sorts =880000, time =45.2
Minimum number of sorts =890000, time =48.5
Minimum number of sorts =900000, time =45.7
Minimum number of sorts =910000, time =45.4
Minimum number of sorts =920000, time =49.3
Minimum number of sorts =930000, time =46.1
Minimum number of sorts =940000, time =46.7
Minimum number of sorts =950000, time =44.4
Minimum number of sorts =960000, time =45.4
Minimum number of sorts =970000, time =45.0
Minimum number of sorts =980000, time =47.2
Minimum number of sorts =990000, time =48.4
Minimum number of sorts =1000000, time =84.3
Minimum number of sorts =1010000, time =84.6