RFR: 7903: FastAccessNumberMap is slow for sparse values

[Richard Startin]

This reworks `FastAccessNumberMap` so that a small bitset can be stored in each page of values, which can be used to skip over null values during iteration. A simple benchmark shows a modest enhancement to calls to `get`, but significant improvements when the map contains sparse values (iteration now scales with the number of non-null values, not the number of pages).


import org.openjdk.jmc.common.collection.FastAccessNumberMap;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
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.concurrent.TimeUnit;

@OutputTimeUnit(TimeUnit.MICROSECONDS)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 5, time = 1)
@Fork(1)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
public class FastAccessNumberMapBenchmark {
    private FastAccessNumberMap<String> map;
    @Param({"1", "2", "3", "4", "64"})
    int period;
    private int size;
    private long[] values;

    @Setup(Level.Trial)
    public void setup() {
        map = new FastAccessNumberMap<>();
        values = new long[5000];
        for (int i = 0; i < 5000; i += period) {
            map.put(i, String.valueOf(i));
            values[size++] = i;
        }
    }

    @Benchmark
    public void get(Blackhole bh) {
        for (int i = 0; i < size; i++) {
            bh.consume(map.get(values[i]));
        }
    }

    @Benchmark
    public void iterate(Blackhole bh) {
        map.forEach(bh::consume);
    }
}
``` 

Tested with 17.0.4.1 2022-08-12 on a Mac M1 
After:

Benchmark                             (period)  Mode  Cnt   Score   Error  Units
FastAccessNumberMapBenchmark.get             1  avgt    5  17.864 ± 0.044  us/op
FastAccessNumberMapBenchmark.get             2  avgt    5   8.921 ± 0.124  us/op
FastAccessNumberMapBenchmark.get             3  avgt    5   5.916 ± 0.052  us/op
FastAccessNumberMapBenchmark.get             4  avgt    5   4.351 ± 0.011  us/op
FastAccessNumberMapBenchmark.get            64  avgt    5   0.273 ± 0.001  us/op
FastAccessNumberMapBenchmark.iterate         1  avgt    5  16.241 ± 0.581  us/op
FastAccessNumberMapBenchmark.iterate         2  avgt    5   8.768 ± 0.205  us/op
FastAccessNumberMapBenchmark.iterate         3  avgt    5   5.463 ± 0.051  us/op
FastAccessNumberMapBenchmark.iterate         4  avgt    5   4.095 ± 0.103  us/op
FastAccessNumberMapBenchmark.iterate        64  avgt    5   0.441 ± 0.002  us/op


Before:

Benchmark                             (period)  Mode  Cnt   Score    Error  Units
FastAccessNumberMapBenchmark.get             1  avgt    5  18.937 ±  0.212  us/op
FastAccessNumberMapBenchmark.get             2  avgt    5   9.419 ±  0.042  us/op
FastAccessNumberMapBenchmark.get             3  avgt    5   6.151 ±  0.108  us/op
FastAccessNumberMapBenchmark.get             4  avgt    5   4.618 ±  0.031  us/op
FastAccessNumberMapBenchmark.get            64  avgt    5   0.286 ±  0.001  us/op
FastAccessNumberMapBenchmark.iterate         1  avgt    5  19.142 ±  0.611  us/op
FastAccessNumberMapBenchmark.iterate         2  avgt    5  18.930 ±  4.756  us/op
FastAccessNumberMapBenchmark.iterate         3  avgt    5  11.579 ±  0.082  us/op
FastAccessNumberMapBenchmark.iterate         4  avgt    5  11.650 ±  0.500  us/op
FastAccessNumberMapBenchmark.iterate        64  avgt    5  11.781 ±  0.541  us/op


We use the jmc common library in a backend process at Datadog and see bigger improvements than the microbenchmark above would suggest.

-------------

Commit messages:
 - 7903: optimise FastAccessNumberMap.get and FastAccessNumberMap.iterate

Changes: https://git.openjdk.org/jmc/pull/431/files
 Webrev: https://webrevs.openjdk.org/?repo=jmc&pr=431&range=00
  Issue: https://bugs.openjdk.org/browse/JMC-7903
  Stats: 77 lines in 1 file changed: 59 ins; 3 del; 15 mod
  Patch: https://git.openjdk.org/jmc/pull/431.diff
  Fetch: git fetch https://git.openjdk.org/jmc pull/431/head:pull/431

PR: https://git.openjdk.org/jmc/pull/431