PlainTDigestBenchmark.java

import java.util.ArrayList;
import java.util.List;
import java.util.LongSummaryStatistics;
import java.util.Random;
import java.util.function.Supplier;
import java.util.stream.Collectors;

import com.tdunning.math.stats.AVLTreeDigest;
import com.tdunning.math.stats.MergingDigest;
import com.tdunning.math.stats.TDigest;

public class PlainTDigestBenchmark {

    public static void main(String[] args) {
        int numRecordsToAdd = 1000000;
        int numberTestRuns = 100;
        double compression = 100.0;
        System.out.println("Random Doubles\n--------------");
        runRandomValuesBenchmark(10000, 10, 100.0, true); // Warm up
        runRandomValuesBenchmark(numRecordsToAdd, numberTestRuns, compression, false);

        System.out.println("\n\nSequential Doubles\n------------------");
        runSequentialValuesBenchmark(10000, 10, 100.0, true); // Warm up
        runSequentialValuesBenchmark(numRecordsToAdd, numberTestRuns, compression, false);

        System.out.println("\n\nRepeated Doubles\n------------------");
        runRepeatedValuesBenchmark(10000, 10, 100.0, true); // Warm up
        runRepeatedValuesBenchmark(numRecordsToAdd, numberTestRuns, compression, false);
    }

    private static void runRandomValuesBenchmark(int numRecordsToAdd, int numberTestRuns, double compression, boolean warmup) {
        runBenchmark(numRecordsToAdd, numberTestRuns, compression, new RandomTestValuesSupplier(), warmup);
    }

    private static void runSequentialValuesBenchmark(int numRecordsToAdd, int numberTestRuns, double compression, boolean warmup) {
        runBenchmark(numRecordsToAdd, numberTestRuns, compression, new RandomTestValuesSupplier(), warmup);
    }

    private static void runRepeatedValuesBenchmark(int numRecordsToAdd, int numberTestRuns, double compression, boolean warmup) {
        runBenchmark(numRecordsToAdd, numberTestRuns, compression, new RepeatedTestValuesSupplier(), warmup);
    }

    private static void runBenchmark(int numRecordsToAdd, int numberTestRuns, double compression, TestValuesSupplier valuesSupplier,
            boolean warmup) {
        List<Long> avlTestResultsNanos = new ArrayList<>(numberTestRuns);
        List<Long> mergingTestResultsNanos = new ArrayList<>(numberTestRuns);

        for (int j = 0; j < numberTestRuns; j++) {
            valuesSupplier.moveToNextTest();

            AVLTreeDigest avlTreeDigest = new AVLTreeDigest(compression);
            long avlInsertTimeNanos = runTest(numRecordsToAdd, avlTreeDigest, valuesSupplier.getSupplier());
            avlTestResultsNanos.add(avlInsertTimeNanos);

            MergingDigest mergingDigest = new MergingDigest(compression);
            long mergingInsertTimeNanos = runTest(numRecordsToAdd, mergingDigest, valuesSupplier.getSupplier());
            mergingTestResultsNanos.add(mergingInsertTimeNanos);
        }

        if (warmup == false) {
            LongSummaryStatistics avlStats = avlTestResultsNanos.stream().collect(Collectors.summarizingLong(l -> l));
            System.out.println("Average AVLTreeDigest (ns): " + avlStats.getAverage());
            System.out.println("Average AVLTreeDigest (ms): " + avlStats.getAverage() / 1000000);

            LongSummaryStatistics mergingStats = mergingTestResultsNanos.stream().collect(Collectors.summarizingLong(l -> l));
            System.out.println("Average MergingDigest (ns): " + mergingStats.getAverage());
            System.out.println("Average MergingDigest (ms): " + mergingStats.getAverage() / 1000000);

            System.out.println(
                    "Average MergingDigest / Average AVLTreeDigest (%): " + (mergingStats.getAverage() / avlStats.getAverage() * 100.0));
            System.out.println(
                    "Average AVLTreeDigest / Average MergingDigest (raw value): " + (avlStats.getAverage() / mergingStats.getAverage()));
        }
    }

    private static long runTest(int numRecordsToAdd, TDigest mergingDigest, Supplier<Double> valuesSupplier) {
        long mergingInsertStart = System.nanoTime();
        for (int i = 0; i < numRecordsToAdd; i++) {
            mergingDigest.add(valuesSupplier.get());
        }
        long mergingInsertEnd = System.nanoTime();
        return mergingInsertEnd - mergingInsertStart;
    }

    public static interface TestValuesSupplier {
        void moveToNextTest();

        Supplier<Double> getSupplier();
    }

    public static class RandomTestValuesSupplier implements TestValuesSupplier {

        private final Random seedGenerator;
        private long seed;

        public RandomTestValuesSupplier() {
            this.seedGenerator = new Random();
            moveToNextTest();
        }

        @Override
        public void moveToNextTest() {
            this.seed = this.seedGenerator.nextLong();
        }

        @Override
        public Supplier<Double> getSupplier() {
            Random r = new Random(seed);
            return () -> r.nextDouble();
        }

    }

    public static class SequentialTestValuesSupplier implements TestValuesSupplier {

        private long currentValue;

        public SequentialTestValuesSupplier() {
            moveToNextTest();
        }

        @Override
        public void moveToNextTest() {
            this.currentValue = 0;
        }

        @Override
        public Supplier<Double> getSupplier() {
            return () -> Double.valueOf(currentValue++);
        }

    }

    public static class RepeatedTestValuesSupplier implements TestValuesSupplier {

        private final Random valueGenerator;
        private double value;

        public RepeatedTestValuesSupplier() {
            this.valueGenerator = new Random();
            moveToNextTest();
        }

        @Override
        public void moveToNextTest() {
            this.value = valueGenerator.nextDouble();
        }

        @Override
        public Supplier<Double> getSupplier() {
            return () -> value;
        }

    }
}

TDigestBenchmark.java

package org.elasticsearch.benchmark.search.aggregations;

import com.tdunning.math.stats.AVLTreeDigest;
import com.tdunning.math.stats.MergingDigest;
import com.tdunning.math.stats.TDigest;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import org.openjdk.jmh.infra.Blackhole;

import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.util.function.Supplier;

@Fork(value = 3)
@Warmup(iterations = 10)
@Measurement(iterations = 10)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
@SuppressWarnings("unused") //invoked by benchmarking framework
public class TDigestBenchmark {
    private static final long SEED = 13;

    @Param(value = {"100000", "1000000"})
    public int numRecordsToAdd;

    @Param(value = {"100.0"})
    public double compression;

    @Param(value = {"avl", "merging"})
    public String algorithm;

    public TDigest digest;

    public Random random;

    @Setup
    public void setUp() {
        switch (algorithm) {
            case "avl":
                this.digest = new AVLTreeDigest(compression);
                break;
            case "merging":
                this.digest = new MergingDigest(compression);
                break;
            default:
                throw new IllegalArgumentException("Unknown t-digest algorithm [" + algorithm + "]");
        }
        this.random = new Random(SEED);
    }

    @Benchmark
    public void measureSequentialValues(Blackhole bh) {
        long currentValue = 0;
        insert(new Supplier<Double>() {
            private long currentValue = 0;

            @Override
            public Double get() {
                return (double) currentValue++;
            }
        }, bh);
    }

    @Benchmark
    public void measureRandomValues(Blackhole bh) {
        insert(random::nextDouble, bh);
    }

    @Benchmark
    public void measureRepeatedValues(Blackhole bh) {
        double value = random.nextDouble();
        insert(() -> value, bh);
    }

    public void insert(Supplier<Double> supplier, Blackhole bh) {
        for (int i = 0; i < numRecordsToAdd; i++) {
            double v = supplier.get();
            digest.add(v);
            // prevent loop unrolling to happen by adding a data dependency.
            bh.consume(v);
        }
    }
}