JMH benchmark of Bifurcan's LinearMap

Bench.java

package bench;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import java.util.concurrent.*;
import io.lacuna.bifurcan.LinearMap;

@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 3, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Fork(value=1, jvmArgsAppend = {})
public class Bench {

    public static Long randKey() {
        return new Long((long)(Math.random() * 10000000));
    }

    public static Long[] makeKeys(int n) {
        Long[] arr = new Long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = randKey();
        }
        return arr;
    }

    @State(Scope.Thread)
    public static class BenchState {

        @Param({"100", "1000", "100000", "1000000"})
        int size;

        Long[] keys;
        LinearMap map;

        @Setup(Level.Iteration)
        public void prepare() {
            keys = makeKeys(size);
            map = new LinearMap();

            Long[] mapKeys = new Long[size];
            // Copy half existing keys
            for (int i = 0; i < size/2; i++)
                mapKeys[i] = new Long(keys[i]);
            // Generate half non-existing keys
            for (int i = size/2; i < size; i++)
                mapKeys[i] = randKey();

            for (Long k : mapKeys)
                map.put(k, Boolean.TRUE);
        }
    }

    @Benchmark
    public void baseline(BenchState state, Blackhole bh) {
        // Just iterating
        for (Long k : state.keys)
            bh.consume(k);
    }

    @Benchmark
    public void lookupWoBH(BenchState state, Blackhole bh) {
        for (Long k : state.keys)
            state.map.get(k);
    }

    @Benchmark
    public void lookupWithBH(BenchState state, Blackhole bh) {
        for (Long k : state.keys)
            bh.consume(state.map.get(k));
    }
}

build.boot

(set-env!
 :dependencies '[[io.lacuna/bifurcan "0.1.0-alpha6"]
                 [org.openjdk.jmh/jmh-core "1.21"]
                 [org.openjdk.jmh/jmh-generator-annprocess "1.21"]]
 :target "target/")

(deftask jmh []
  (comp (sift :add-source #{"."} :include #{#"target/"} :invert true)
        (javac)
        (target)
        (with-pass-thru _
          (import 'org.openjdk.jmh.Main)
          (let [boot-classpath
                (str (System/getProperty "fake.class.path")
                     java.io.File/pathSeparator
                     "./target/")]
            (System/setProperty "java.class.path" boot-classpath)
            (org.openjdk.jmh.Main/main (into-array String []))))))

;; Launch as `boot jmh`
#_(boot (jmh))

results.txt

## Benchmarked on c5.18xlarge, Ubuntu 16.04, OpenJDK 8
## Timings were normalized manually, default JMH runner can't do that.

Benchmark               (size)            Score

Bench.baseline             100       2.7 ± 0.0 ns/op
Bench.baseline            1000       2.5 ± 0.8 ns/op
Bench.baseline          100000       2.6 ± 0.3 ns/op
Bench.baseline         1000000       2.7 ± 0.0 ns/op

Bench.lookupWoBH           100       7.0 ± 0.5 ns/op
Bench.lookupWoBH          1000       7.7 ± 0.2 ns/op
Bench.lookupWoBH        100000      17.9 ± 0.7 ns/op
Bench.lookupWoBH       1000000      39.9 ± 3.1 ns/op

Bench.lookupWithBH         100      10.0 ± 3.1 ns/op
Bench.lookupWithBH        1000      11.3 ± 2.8 ns/op
Bench.lookupWithBH      100000      22.9 ± 2.4 ns/op
Bench.lookupWithBH     1000000      50.1 ± 5.1 ns/op