FindMaxBenchmark.java

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.TimeUnit;
import java.util.stream.DoubleStream;

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Benchmark)
public class FindMaxBenchmark {
  //@Param({"100", "1000", "10000", "100000", "1000000", "10000000"})
  @Param({"1000000", "10000000"})
  int arrayLen;

  // @Param({"1", "2", "4", "8", "16", "256"})
  @Param("32")
  int pieces;

  double[] values;
  double trueMaxValue;

  double maxValue;

  @Setup
  public void prepare() {
    values = new double[arrayLen];
    final Random gen = new Random();
    for (int i = 0; i < arrayLen; i++) {
      values[i] = gen.nextDouble();
    }
    trueMaxValue = DoubleStream.of(values).max().getAsDouble();
  }

  @TearDown
  public void check() {
    assert maxValue == trueMaxValue : "max should be right";
  }

  public static class RecursiveFindMax extends RecursiveTask<Double> {
    final int lo;
    final int hi;
    final double[] array;
    final int threshold;
    final int pieces;

    RecursiveFindMax(final double[] array, final int pieces) {
      this(array, 0, array.length, pieces);
    }

    RecursiveFindMax(final double[] array, final int lo, final int hi, final int pieces) {
      this.array = array;
      this.lo = lo;
      this.hi = hi;
      this.pieces = pieces;
      threshold = array.length / pieces;
    }

    @Override
    protected Double compute() {
      if (hi - lo <= threshold) {
        double max = array[lo];
        for (int i = lo + 1; i < hi; i++) {
          if (array[i] > max) {
            max = array[i];
          }
        }
        return max;
      } else {
        final int mid = lo + (hi - lo) / 2;
        final RecursiveFindMax left  = new RecursiveFindMax(array, lo, mid, pieces);
        final RecursiveFindMax right = new RecursiveFindMax(array, mid, hi, pieces);
        right.fork();
        final double leftAns  = left.compute();
        final double rightAns = right.join();

        return Math.max(leftAns, rightAns);
      }
    }

    public static double apply(final double[] array, final int pieces) {
      return ForkJoinPool.commonPool().invoke(new RecursiveFindMax(array, pieces));
    }
  }
  
  double findMax(final double[] array) {
    double max = array[0];
    for (final double x : array) {
      if (x > max) {
        max = x;
      }
    }
    return max;
  }

  @Benchmark
  public void simpleMax() {
    maxValue = findMax(values);
  }

  @Benchmark
  public void fjMax1() {
    maxValue = RecursiveFindMax.apply(values, pieces);
  }

  public static void main(final String[] args) throws RunnerException {
    final Options opts = new OptionsBuilder()
        .include(".*" + FindMaxBenchmark.class.getSimpleName() + ".*")
        .forks(1)
        .build();

    new Runner(opts).run();
  }

}