fjava: A Java repository from ikaver

#FJava: Fork Join for Java

##What is FJava? FJava is a high level fork join framework for the Java programming language. Our framework outperforms the native Java Fork Join framework under some workloads, and gets competitive results for others. With our implementation, we demonstrate that private deques are an effective work stealing algorithm for a Fork Join framework.

##Sample code

public class FJavaQuickSort extends FJavaTask {

  private long [] array;
  private int left;
  private int right;
  
  private static final SEQUENTIAL_THRESHOLD = 100;

  public FJavaQuickSort(long [] array, int left, int right) {
    this.array = array;
    this.left = left;
    this.right = right;
  }

  @Override
  public void compute() {
    if(right <= left) return;

    if(right - left <= SEQUENTIAL_THRESHOLD) {
      Arrays.sort(array, left, right+1);
      return;
    }
    int mid = partition();
    new FJavaQuickSort(array, left, mid-1).runAsync(this);
    new FJavaQuickSort(array, mid+1, right).runSync(this);
    sync();
  }

  private int partition() {
    int i = left, j = right+1;
    long tmp;
    long pivot = array[left];
   
    while (true) {
      while(array[++i] <= pivot) 
        if(i == right) break;
      while(array[--j] >= pivot) 
        if(j == left) break;
      if(i >= j) break;
      tmp = array[i];
      array[i] = array[j];
      array[j] = tmp;
    }

    tmp = array[j];
    array[j] = pivot;
    array[left] = tmp;
     
    return j;
  }

  public static void sort(long[] array, int left, int right) {
    FJavaPool pool = FJavaPoolFactory.getInstance().createPool();
    FJavaQuickSort task = new FJavaQuickSort(array, left, right);
    pool.run(task);
  }
}

##Preliminary results The next figure shows the relative speedups achieved by FJava and Java Fork Join relative to the sequential version of the code for several problems.

Primes: Call isPrime for an array of 5,000,000 primes
Matrix Multiplication: Multiply two 2048x2048 matrices recursively
Fibonacci: Solve fibonacci(50) recursively
QuickSort: Sort 10,000,000 longs using QuickSort
LU Decomposition: Decompose a 4096x4096 matrix

For different values of the sequential threshold T, the results vary. FJava uses Private Deques, therefore, as expected, for larger values of T, Java's native Fork Join outperforms FJava (but not by a large margin).

To address this issue, we have added tryLoadBalance function to our API. This call allows FJava to perform competitively with Java 8 Fork Join even for tasks that have large sequential thresholds. On the downside, the user is responsible for making sure they call tryLoadBalance periodically during their long computations. For example:

  @Override
  public void compute() { 
    if(right - left <= SEQUENTIAL_THRESHOLD) {
      for(int i = left; i <= right; ++i) {
        this.result[i] = this.mapFunc.map(this.array[i]);
        if(i % ITERATIONS_FOR_BALANCE == 0) this.tryLoadBalance();
      }
      return;
    }
    //create child tasks using runAsync here
  }

ikaver/fjava