Understanding Fork Join

Overview

This page will walk you through reading documentation and understanding what the functions do in a practical manner. There is an assumption that you have attended class and watched the lectures, so the terms are familiar, but there is trouble knowing what everything means/does.

Fork

Reading the Documentation

When we look at the docs, we are greeted with the following:

public static <T> Future<T> fork(TaskSupplier<T> task)

What does this mean? Let's break it down

Static

static means that the function is related to the class, FJ as opposed to a specific instance of that class. This means that we can call FJ.fork directly, we don't need to create an instance of that class to do so. In our code, we typically just write fork because Professor Cosgrove has imported the appropriate dependencies for you! In fact, this entire library is static, so you should just be calling these functions by their function name.

Lambda Functions

We see that fork takes in one parameter of type TaskSupplier<T>. If we follow the link, we see that a TaskSupplier<T> is just a single function, which has a return type T and can throw InterruptedException and ExecutionException.

T get() throws InterruptedException,ExecutionException

Thus, any function that takes in no parameters and returns anything qualifies as a TaskSupplier<T>. In code for this course, you will often see code such as:

Lambda function
public int count(/* parameters */) { Future<Integer> firstHalfFuture = fork(() -> { /* Parallel task */ }); /* Main task */ int firstHalf = join(firstHalfFuture); /* more code */ }

This is the same as:

Explicit function
public int myFunc() { /* Parallel task */ } public int count(/* parameters */) { Future<Integer> firstHalfFuture = fork(() -> myFunc()); /* Main task */ int firstHalf = join(firstHalfFuture); /* more code */ }

In the first case, we defined the function inline at the fork method call, while the second case is more akin to what you may be used to.

Generics

You may have the question, what is a value of type T? <T> means that we have a generic type called T. T isn't any one type in particular, but instead is just a guarantee that in the following code, whenever we see T, it is referring to the same type. An example you may be more familiar with is the ArrayList<E> class. If we look at the documentation for ArrayList<E>, we see, among other things:

public class ArrayList<E>

public boolean add(E e)

public E get(int index)

In the case of ArrayList<E>, E is the name of the generic type. And thus, everywhere we see E, it is the same type E as was supplied to the class constructor. That is why when you create an ArrayList<Integer>, you are able to use it for Integer, but not some other type such as String. Then, when you create an ArrayList<String>, you are able to use it for String, but not other types such as Integer.

Coming back to the fork function, we next see that the return type is Future<T>. We can follow the link to the java documentation for Future to see that when we call Future.get(), it will return a value of type T. Generally, in this course, we use T when referring to the type of the data that is passed into the parallel task, and R when referring to the type of the data that is returned by the parallel task.

Practical Explanation

So putting all of this together, the fork function is a static function that is tied to the FJ class, and not any specific instance of that class. It takes in a function that returns any type T, and itself returns a Future<T> object, which will return a value of that same type T when the get function is called on it. The function that is passed into the fork function is run in parallel to the main process. Thus, code in the following structure leads to a parallel program:

Fork template
// Parallel task and Main task will run in parallel to one another Future<SomeType> myFuture = fork(() -> { /* Parallel task */ }); /* Main task */ SomeType myValue = join(myFuture); }

Fork Loop

1 down, 32 to go! Don't worry, things will get faster now as there is less to explain.

Forking by Index

The first fork_loop we are going to explore has the following signature:

public static <R> Future<R>[] fork_loop(int min, int maxExclusive, TaskIntFunction<R> function)

So this version of fork_loop takes in two integers, min and maxExclusive, then a TaskIntFunction<R>. The function as a whole returns a, Future<R>[], an array of Future<R>. Following the link for the TaskIntFunction<R> reveals that it is a function that has one parameter of type int and returns a value of type R. Under the hood, the fork_loop function creates one fork, one parallel branch, for each integer in the range [min, maxExclusive), and passes to each branch its corresponding integer. This join_fork function is very similar to a "standard" for loop for(int i = min; i < maxExclusive; i++), just parallel. An example use case of this fork_loop is as follows:

join_fork example
public int[] parallel_double(int[] array) { Future<Integer> updatedFuture = join_fork(0, array.length, (index) -> { return array[index] * 2; }); return join(updatedFuture); }