Fork/Join with non-recursive Task

Most tutorials use some recursive Task to calculate a Fibonacci number or something similar. This leads to the false impression that Fork/Join can only handle recursive Tasks (e.g. Divide-And-Conquer). Here’s a very simple example of a non-recursive Task.

Step 1: Define Task1

Just extend ForkJoinTask like so:

class Task1 extends ForkJoinTask<RESULT_TYPE> { …

Use any actual type (String, Integer etc.) as “RESULT_TYPE“. I use Integer in my example.

Then implement it, but leave exec() empty for now. You might want to define a constructor that takes some input.
And define some private field for the raw result and return it in getRawResult().

Step 2: Define Task2

You can just copy Task1, because this will be mostly the same. You can already implement exec if you know what this should do.
Just implement any long running task that produces a partial result. Again, you want to define a constructor that takes some input. It defines which partial result should be calculated or produced.

If you really just need to run two things in parallel, you should just use a regular thread pool (cached or fixed). You don’t need a work stealing fork/join-pool. Or just use thenCombineAsync. That’s why in most examples the algorithm is recursive. Such an algorithm will create many small tasks.

Step 3: Implement Task1.exec()

I invoke two instances of Task2, which is the most basic kind of fork/join logic. Divide the problem into two parts and run them in parallel. So it should take only about half as much time.
The code looks like this:

@Override protected boolean exec() {
  ForkJoinTask<Integer> a = new Task2(this.input).fork();
  ForkJoinTask<Integer> b = new Task2(this.input + 1).fork();
  setRawResult(a.join() + b.join());
  return true;
}

Note: You can not inline a and b. They must both fork before they both join!
But you can create more than two subtasks.
I used Integer so I can do a simple addition of both values. In most cases you simply merge the two partial results into one final result.

Step 4: Run it!

That’s very simple and might look like this:

Integer result = ForkJoinPool.commonPool().invoke(new Task1(5));

In this case the result is : 52 + 62 = 25 + 36 = 61

Note that this will block the current Thread until you get the result. You could use CompletableFuture instead:

CompletableFuture.supplyAsync(new Task1(5)::invoke).thenAccept(System.out::println);

Complete Code

The complete code is on pastebin: https://pastebin.com/PSrEUrPw

Note that the Thread.sleep(5000) in Task2.exec() is just there to demonstrate that both instances of Task2 run in parallel. It only takes about five seconds, not ten. You’d remove it and use some actual code for some long running task. And if it takes too long you can split it up even more.

Matrix Multiplication

Here’s an example that actually does something: https://pastebin.com/zaTwZkTY

The code is very similar, but it actually calculates the matrix product of two given matrices. Note that this is still an example and isn’t necesarrily faster than just doing this in a single thread. But it shows how you can fork many subtasks and then join them to get a single result.
There’s no recursion. But there will be a task for each entry of the resulting matrix. The variable names are taken from the Wikipedia definition on matrix multiplication. You can compare the code to the formula given there.

Leave a Reply

Your email address will not be published. Required fields are marked *