RFR: 7903: FastAccessNumberMap is slow for sparse values [v2]

[Henrik Dafgård]

On Wed, 28 Sep 2022 12:53:36 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.
>
> Richard Startin has refreshed the contents of this pull request, and previous commits have been removed. The incremental views will show differences compared to the previous content of the PR. The pull request contains one new commit since the last revision:
> 
>   7903: optimise FastAccessNumberMap.get and FastAccessNumberMap.iterate

This looks good to me, with a good performance improvement in some cases.

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

Marked as reviewed by hdafgard (Reviewer).

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