Одним из наиболее интересных улучшений Java 7 является улучшенная поддержка параллелизма. С JSR 166 Concurrency Utilities мы получаем несколько очень полезных улучшений параллелизма. С моей точки зрения, библиотека fork-join имеет большой потенциал для практического использования в разработке программного обеспечения. Fork and join предоставляет очень простую модель программирования для алгоритмов, которая может быть реализована как рекурсивная задача. Существует множество алгоритмов, которые можно реализовать с помощью алгоритмов «разделяй и властвуй».
В ближайшие годы мы увидим увеличение количества ядер в стандартных настольных ПК, ноутбуках и серверных компьютерах. Причина этого проста: дешевле добавлять дополнительные ядра, чем создавать более быстрый одиночный процессор. Таким образом, нам нужно будет написать больше программного обеспечения, поддерживающего параллелизм, чтобы воспользоваться преимуществами лучшего оборудования.
Если честно, я не люблю параллелизм. Мое личное правило: «У вас должна быть веская причина для реализации параллелизма, и если вам нужно это делать, будьте очень осторожны». В последние годы я видел больше ошибочных реализаций, чем работающих. Вот почему мне нравится библиотека fork & join. Четкая модель программирования, в которой реализован код котельной плиты, предотвращает ошибки. Но, пожалуйста, если вы намереваетесь использовать fork и join, потратьте некоторое время, чтобы понять поведение.
Пример в файлах № 1 и № 2 очень похож на пример кода в документации по Java 7. В целом, числа Фибоначчи с рекурсивным алгоритмом не очень хорошая идея, потому что есть лучшее линейное решение (сравните http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms ), но его легче реализовать и понять чем другие. Итак, давайте посмотрим на образец:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
// File #1: FibonacciTask.java [error handling, parameter validation and asserts removed] package com.sprunck.sample;import java.util.concurrent.RecursiveTask;public class FibonacciTask extends RecursiveTask<Long> { private static final long serialVersionUID = 1L; private final long inputValue; public FibonacciTask(long inputValue) { this.inputValue = inputValue; } @Override public Long compute() { if (inputValue == 0L) { return 0L; } else if (inputValue <= 2L) { return 1L; } else { final FibonacciTask firstWorker = new FibonacciTask(inputValue - 1L); firstWorker.fork(); final FibonacciTask secondWorker = new FibonacciTask(inputValue - 2L); return secondWorker.compute() + firstWorker.join(); } }} |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// File #2: FibonacciTaskTest.java package com.sprunck.sample;import java.util.concurrent.ForkJoinPool;import junit.framework.Assert;import org.junit.Test;public class FibonacciTaskTest { // it makes no sense to create more threads than available cores (no speed improvement here) private static final int AVAILABLE_PROCESSORS = Runtime.getRuntime().availableProcessors(); // create thread pool private final ForkJoinPool pool = new ForkJoinPool(AVAILABLE_PROCESSORS); @Test public void testFibonacciArray() { // more test data: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html long results[] = { 0L, 1L, 1L, 2L, 3L, 5L, 8L, 13L, 21L, 34L, 55L, 89L, 144L, 233L, 377L, 610L, 987L, 1597L, 2584L, 4181L, 6765L }; for (int inputValue = 0; inputValue < results.length; inputValue++) { final FibonacciTask task = new FibonacciTask(inputValue); System.out.print("Fibonacci(" + inputValue + ") = "); final long result = pool.invoke(task); System.out.println(result); Assert.assertEquals(results[inputValue], result); } }} |
// Вывод FibonacciTaskTest.java
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
Fibonacci(0) = 0Fibonacci(1) = 1Fibonacci(2) = 1Fibonacci(3) = 2Fibonacci(4) = 3Fibonacci(5) = 5Fibonacci(6) = 8Fibonacci(7) = 13Fibonacci(8) = 21Fibonacci(9) = 34Fibonacci(10) = 55Fibonacci(11) = 89Fibonacci(12) = 144Fibonacci(13) = 233Fibonacci(14) = 377Fibonacci(15) = 610Fibonacci(16) = 987Fibonacci(17) = 1597Fibonacci(18) = 2584Fibonacci(19) = 4181Fibonacci(20) = 6765 |
Пока это простое и понятное решение. Нет кода котельной пластины для параллелизма, например, синхронизация потоков.
Но я хотел бы призвать вас глубже взглянуть на то, что происходит в решении. В файлах № 3 и № 4 вы найдете расширенную версию той же программы. Единственная разница между первой и второй версией — это некоторый код для отслеживания того, что происходит во время выполнения, и небольшая медленная задача () для имитации более реалистичного поведения.
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
// File #3: FibonacciTaskTraces.java package com.sprunck.sample;import java.util.concurrent.RecursiveTask;public class FibonacciTaskTraces extends RecursiveTask<Long> { private static final long serialVersionUID = 1L; // just needed to format debug output public static final String OUTPUT_PREFIX = " | "; private final String prefix; private final long inputValue; public FibonacciTaskTraces(long inputValue, final String prefix) { this.inputValue = inputValue; this.prefix = prefix; } @Override public Long compute() { if (inputValue == 0L) { slowTask(); return 0L; } else if (inputValue <= 2L) { slowTask(); return 1L; } else { final long firstValue = inputValue - 1L; System.out.println(prefix + " - Fibonacci(" + firstValue + ") <- " + Thread.currentThread().getName() + " (fork) "); final FibonacciTaskTraces firstWorker = new FibonacciTaskTraces(firstValue, prefix + OUTPUT_PREFIX); firstWorker.fork(); final long secondValue = inputValue - 2L; System.out.println(prefix + " - Fibonacci(" + secondValue + ") <- " + Thread.currentThread().getName()); final FibonacciTaskTraces secondWorker = new FibonacciTaskTraces(secondValue, prefix + OUTPUT_PREFIX); long result = secondWorker.compute() + firstWorker.join(); System.out.println(prefix + " - Fibonacci(" + inputValue + ") = " + result + " <- " + Thread.currentThread().getName() + " (join)"); slowTask(); return result; } } /** just simulate a longer running task (with out disturbing the other threads) */ private void slowTask() { for (int k = 0, i = 0; i < 1000 * 1000 * 100; i++) { i = i + k; } }} |
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
// File #4: FibonacciTaskTracesTask.javapackage com.sprunck.sample;import java.util.concurrent.ForkJoinPool;import junit.framework.Assert;import org.junit.Test;public class FibonacciTaskTracesTest { // it makes no sense to create more threads than available cores (no speed improvement here) private static final int AVAILABLE_PROCESSORS = Runtime.getRuntime().availableProcessors(); // create thread pool private final ForkJoinPool pool = new ForkJoinPool(AVAILABLE_PROCESSORS); @Test public void testFibonacciArrayTraces() { // more test data: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html long results[] = { 0L, 1L, 1L, 2L, 3L, 5L, 8L, 13L }; for (int inputValue = 0; inputValue < results.length; inputValue++) { final FibonacciTaskTraces task = new FibonacciTaskTraces(inputValue, " | "); System.out.println("invoke Fibonacci(" + inputValue + ") <- " + Thread.currentThread().getName()); final long result = pool.invoke(task); System.out.println("result = " + result + "\n"); Assert.assertEquals(results[inputValue], result); } }} |
// Вывод FibonacciTaskTracesTest.java
|
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
invoke Fibonacci(0) <- mainresult = 0invoke Fibonacci(1) <- mainresult = 1invoke Fibonacci(2) <- mainresult = 1invoke Fibonacci(3) <- main | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join)result = 2invoke Fibonacci(4) <- main | - Fibonacci(3) <- ForkJoinPool-1-worker-1 (fork) | - Fibonacci(2) <- ForkJoinPool-1-worker-1 | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-1 (join)result = 3invoke Fibonacci(5) <- main | - Fibonacci(4) <- ForkJoinPool-1-worker-1 (fork) | - Fibonacci(3) <- ForkJoinPool-1-worker-1 | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 (fork) | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join) | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-2 (join) | - Fibonacci(5) = 5 <- ForkJoinPool-1-worker-1 (join)result = 5invoke Fibonacci(6) <- main | - Fibonacci(5) <- ForkJoinPool-1-worker-1 (fork) | - Fibonacci(4) <- ForkJoinPool-1-worker-1 | | - Fibonacci(3) <- ForkJoinPool-1-worker-1 (fork) | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 | | - Fibonacci(4) <- ForkJoinPool-1-worker-2 (fork) | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | | | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join) | | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 (fork) | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-1 (join) | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-2 (join) | | - Fibonacci(5) = 5 <- ForkJoinPool-1-worker-2 (join) | - Fibonacci(6) = 8 <- ForkJoinPool-1-worker-1 (join)result = 8invoke Fibonacci(7) <- main | - Fibonacci(6) <- ForkJoinPool-1-worker-1 (fork) | - Fibonacci(5) <- ForkJoinPool-1-worker-1 | | - Fibonacci(4) <- ForkJoinPool-1-worker-1 (fork) | | - Fibonacci(3) <- ForkJoinPool-1-worker-1 | | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | | | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | | - Fibonacci(5) <- ForkJoinPool-1-worker-2 (fork) | | - Fibonacci(4) <- ForkJoinPool-1-worker-2 | | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 (fork) | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join) | | | - Fibonacci(3) <- ForkJoinPool-1-worker-1 (fork) | | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 | | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | | | | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-2 (join) | | | - Fibonacci(4) <- ForkJoinPool-1-worker-2 (fork) | | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 (fork) | | | | - Fibonacci(1) <- ForkJoinPool-1-worker-2 | | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join) | | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-1 (join) | | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-2 (join) | | - Fibonacci(5) = 5 <- ForkJoinPool-1-worker-1 (join) | | | | - Fibonacci(3) <- ForkJoinPool-1-worker-2 (fork) | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-2 | | | | | - Fibonacci(2) <- ForkJoinPool-1-worker-1 (fork) | | | | | - Fibonacci(1) <- ForkJoinPool-1-worker-1 | | | | | - Fibonacci(3) = 2 <- ForkJoinPool-1-worker-1 (join) | | | | - Fibonacci(4) = 3 <- ForkJoinPool-1-worker-2 (join) | | | - Fibonacci(5) = 5 <- ForkJoinPool-1-worker-2 (join) | | - Fibonacci(6) = 8 <- ForkJoinPool-1-worker-2 (join) | - Fibonacci(7) = 13 <- ForkJoinPool-1-worker-1 (join)result = 13 |
Вывод дает вам теперь более глубокий взгляд на обработку программы. Появляются следующие способы вычисления чисел Фибоначчи:
- первые три числа Фибоначчи обрабатываются в главном потоке,
- следующее число Фибоначчи было обработано только в одном новом потоке (ForkJoinPool-1-worker-1) и
- начиная с пятого потока Фибоначчи номер два (ForkJoinPool-1-worker-1 и ForkJoinPool-1-worker-2).
Алгоритм неэффективен, потому что в обработке много избыточных операций (пересчет того же числа Фибоначчи). В реальных приложениях вы должны быть осторожны с такими неэффективными алгоритмами. Некоторые следы помогают понять, что происходит.
Рекомендации
- Использование fork и join легко и просто, но нужно потратить некоторое время, чтобы проследить и понять вашу реализацию.
- Иногда полезно реализовать две версии одного и того же алгоритма (одну для анализа, а другую для производства).
- Потратьте некоторое время на разработку и понимание лучших алгоритмов параллелизма — это хорошая инвестиция.
Калькулятор вероятностей был разработан таким образом ( Демо калькулятор вероятностей — PCALC ).
Ссылка: Как реализовать fork и join в утилитах параллелизма Java 7 — JSR 166? от нашего партнера JCG Маркуса Спрунка в блоге Software Engineering Candies .