Integrated: 7903: FastAccessNumberMap is slow for sparse values

[Richard Startin]

On Tue, 27 Sep 2022 16:50:00 GMT, Richard Startin <duke at openjdk.org> wrote:

> 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 to iteration speed 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.

This pull request has now been integrated.

Changeset: 7cd2f3e7
Author:    Richard Startin <richard.startin at datadoghq.com>
Committer: Marcus Hirt <hirt at openjdk.org>
URL:       https://git.openjdk.org/jmc/commit/7cd2f3e730480c833930e36951f8658b4addead4
Stats:     83 lines in 1 file changed: 65 ins; 3 del; 15 mod

7903: FastAccessNumberMap is slow for sparse values

Reviewed-by: hdafgard

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

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