One of the most interesting improvements of Java 7 is the better support of concurrency. With JSR 166 Concurrency Utilities we get some very helpful improvements of concurrency. From my point of view the fork-join library has a high potential for practical use in software engineering. Fork and join provides a very easy programming model for algorithms which can be implemented as recursive task. There are a lot of algorithms that can be implemented with divide and conquer algorithms.
In the next years we will see an increasing number of cores in standard desktops, notebooks and server computers. The reason for this is easy: It’s cheaper to add additional cores than to build a faster single processor. So, we will have to write more software which supports concurrency to take benefit of better hardware.
To be honest, I don’t like concurrency. My personal rule is „You need a good reason to implement concurrency and if you have to do it be really careful.“ In the last years, I saw more buggy implementations than working. This is the reason why I like the fork & join library. A clear programming model which implements the boiler plate code prevents you from errors. But, please if you intend to use fork and join take some time to understand the behavior.
The sample in file #1 and #2 is very similar to the sample code in Java 7 documentation. In general, Fibonacci numbers with a recursive algorithm is not a good idea because there is a better linear solution (compare http://nayuki.eigenstate.org/page/fast-fibonacci-algorithms), but it is easier to implement and understand than others. So, let’s have a look at the sample:
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); } }} |
// Output of 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 |
So far it is a simple and clear solution. No boiler plate code for concurrency, e.g. thread synchronization.
But I’d like to encourage you to have a deeper look in what happens in the solution. In files #3 and #4 you find an enhanced version of the same program. The only difference between the first and second version is some code to trace what happens during execution and a small slowTask() to simulate more realistic behavior.
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); } }} |
// Output of 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 |
The output gives you now deeper look into the processing of the program. Following ways of Fibonacci numbers calculation appear:
- the first three Fibonacci numbers are processed in the main thread,
- the next Fibonacci number has been processed in just one new thread (ForkJoinPool-1-worker-1) and
- starting wiht the fifth Fibonacci number two threads (ForkJoinPool-1-worker-1 and ForkJoinPool-1-worker-2) have been used.
The algorithm is inefficient, because there are a lot of redundant operations (re-calculation of the same Fibonacci number) in the processing. In a real life application you should be careful with this kind of inefficient algorithms. Some traces help to understand what happens.
Recomendations
- The use of fork and join is easy and straightforward, but use some time to trace and understand your implementation.
- Sometimes it is helpful to implement two versions of the same algorithm (one for analysis and a second for production).
- Spend some time in designing and understanding better concurrency algorithms is a good investment.
The probability calculator has been developed in this way (Demo of probability calculator – PCALC).
Reference: How to implement fork and join in Java 7 – JSR 166 concurrency utilities ? from our JCG partner Markus Sprunck at the Software Engineering Candies blog.
