Java: how ot optimize sum of big array

Question1 [main]: Is it possible to optimize canonicalSum?

Yes, it is. But I have no idea with what factor.

Some things you can do are:

• use the parallel pipelines introduced in Java 8. The processor has instruction for doing parallel sum of 2 arrays (and more). This can be observed in Octave when you sum two vectors with ".+" (parallel addition) or "+" it is way faster than using a loop.

• use multithreading. You could use a divide and conquer algorithm. Maybe like this:

  • divide the array into 2 or more
  • keep dividing recursively until you get an array with manageable size for a thread.
  • start computing the sum for the sub arrays (divided arrays) with separate threads.
  • finally add the sum generated (from all the threads) for all sub arrays together to produce final result

• maybe unrolling the loop would help a bit, too. By loop unrolling I mean reducing the steps the loop will have to make by doing more operations in the loop manually.

An example from http://en.wikipedia.org/wiki/Loop_unwinding :

for (int x = 0; x < 100; x++)
{
    delete(x);
}

becomes

for (int x = 0; x < 100; x+=5)
{
    delete(x);
    delete(x+1);
    delete(x+2);
    delete(x+3);
    delete(x+4);
}

but as mentioned this must be done with caution and profiling since the JIT could do this kind of optimizations itself probably.

A implementation for mathematical operations for the multithreaded approach can be seen here.

The example implementation with the Fork/Join framework introduced in java 7 that basically does what the divide and conquer algorithm above does would be:

public class ForkJoinCalculator extends RecursiveTask<Double> {

   public static final long THRESHOLD = 1_000_000;

   private final SequentialCalculator sequentialCalculator;
   private final double[] numbers;
   private final int start;
   private final int end;

   public ForkJoinCalculator(double[] numbers, SequentialCalculator sequentialCalculator) {
     this(numbers, 0, numbers.length, sequentialCalculator);
   }

   private ForkJoinCalculator(double[] numbers, int start, int end, SequentialCalculator sequentialCalculator) {
     this.numbers = numbers;
     this.start = start;
     this.end = end;
     this.sequentialCalculator = sequentialCalculator;
   }

   @Override
   protected Double compute() {
     int length = end - start;
     if (length <= THRESHOLD) {
         return sequentialCalculator.computeSequentially(numbers, start, end);
     }
     ForkJoinCalculator leftTask = new ForkJoinCalculator(numbers, start, start + length/2, sequentialCalculator);
     leftTask.fork();
     ForkJoinCalculator rightTask = new ForkJoinCalculator(numbers, start + length/2, end, sequentialCalculator);
     Double rightResult = rightTask.compute();
     Double leftResult = leftTask.join();
     return leftResult + rightResult;
  }
}

Here we develop a RecursiveTask splitting an array of doubles until the length of a subarray doesn't go below a given threshold. At this point the subarray is processed sequentially applying on it the operation defined by the following interface

The interface used is this:

public interface SequentialCalculator {
  double computeSequentially(double[] numbers, int start, int end);
}

And the usage example:

public static double varianceForkJoin(double[] population){
   final ForkJoinPool forkJoinPool = new ForkJoinPool();
   double total = forkJoinPool.invoke(new ForkJoinCalculator(population, new SequentialCalculator() {
     @Override
     public double computeSequentially(double[] numbers, int start, int end) {
       double total = 0;
       for (int i = start; i < end; i++) {
         total += numbers[i];
       }
       return total;
     }
  }));
  final double average = total / population.length;
  double variance = forkJoinPool.invoke(new ForkJoinCalculator(population, new SequentialCalculator() {
    @Override
    public double computeSequentially(double[] numbers, int start, int end) {
      double variance = 0;
      for (int i = start; i < end; i++) {
        variance += (numbers[i] - average) * (numbers[i] - average);
      }
      return variance;
    }
 }));
 return variance / population.length;
}