runtime: use SwissTable #54766

zhangyunhao116 · 2022-08-30T06:49:13Z

Abstract

From ByteDance Programming Language Team

We suggest using SwissTable in the runtime to replace the original implementation of the hashmap.

SwissTable is now used in abseil and rust by default. We borrowed ideas from the two implementations and combined some optimization ideas of Go's original hashmap to construct the current implementation.

See the following comment for performance comparison(the GitHub issue has a character limit).

Motivations

We need to improve the performance of the hashmap as much as possible. At ByteDance, our Go service consumes about 4% of the CPU on hashmap. It is worth noting that on many services, the CPU consumption of mapassign and mapaccess are almost 1:1, so the improvement of insertion performance is equally important.
Support dynamic adjustment of the capacity of the hashmap. Some Go services will make a map too large due to burst traffic, which will cause a lot of pressure on the memory, but the map does not shrink after elements removal. We found that there are also many related discussions in the community:

Implementations

Basic version: https://go-review.googlesource.com/c/go/+/426614
SIMD version: TODO

Tasks

Basic version: without SIMD, follow the original memory layout.
Add SIMD support for x86: WIP, in the following CL.
Aggregates all tophash into an array: In the plan, it requires more performance comparison data.
Support hashmap resizing: More discussion is needed.
Set bucketCnt to 4 on 32-bit platforms: More discussion is needed.

Advantages compared to the original implementation

The overall performance is better, and we can also use SIMD to improve performance.
SwissTable's LoadFactor can be set higher to save some memory.
Open-addressing and making dynamic adjustments to the capacity is easier to implement.
After allocating a fixed-size hashmap, if the number of inserted elements does not exceed the capacity, no additional memory is required, and the performance will be significantly improved, which has a greater advantage over reused fixed-size hashmap. (The original hashmap may still allocate additional memory even when the limit is not exceeded)

Disadvantages compared to the original implementation

The rehash is done at once, so
- Some services that are sensitive to latency may experience performance degradation. (but we do not observe this for now)
- In some cases, when the hashmap needs to grow, it may consume more CPU than the original implementation. (The previous implementation uses incremental rehash)
Since SwissTable needs to ensure that each bucket has at least one empty slot, it will cause performance degradation in some cases. For example, if we insert an element when there are seven elements in the hashmap, the CPU consumption will significantly increase because the hashmap needs to grow.

Implementation details

Here is an overview of the basic version. For more detailed implementation, you can read the code. Before reading the code, it is recommended to check the video or the article in the references to get a general idea of how it works.

Differences with SwissTable

Move tophash into the bucket, not as an array alone.

The classic SwissTable aggregates all tophash into an array (also called control bytes array, here we follow the convention, called tophash), while the original hashmap of Go puts tophash and items in the same bucket.

Our experiments outside the runtime found that if tophash is used as an array alone, we couldn’t find any performance wins. This is probably because we need two memory allocations when initializing the hashmap.

So we use the bucket memory layout almost the same as the original in the current version. In the future, we may consider aggregating all tophash into an array, using a data structure similar to sync.Pool, so that all tophash of the hashmap can be reused to improve performance.

Due to this change, when we delete a key/value, we only need to determine whether the current bucket still has empty slots, because the location where we access the bucket is relatively fixed, unlike the classic implementation, which can be accessed from different addresses.

Differences with the original implementation

For hashmap header (hmap) and hiter

Removed fields about overflow and incremental rehash.

For bucket (bmap)

The tophash is still 8-bit(uint8), but 7-bit for hash info and 1-bit as flags.
Removed overflow pointer.

For the way of querying

The query process changes from querying the overflow pointer to finding the next bucket (using triangular probing) until the first empty slot is found. SwissTable theoretically guarantees that there is at least one empty slot.

For initializing bucket arrays

The initial state of the tophash is 0xff instead of 0; 0xff represents the empty slot now.

References

The text was updated successfully, but these errors were encountered:

zhangyunhao116 · 2022-08-30T06:49:22Z

Performance comparison

Here the SwissTable is just a basic version. To avoid a CL bringing too many changes, it does not use SIMD and is compatible with the previous hashmap memory layout(it means many optimizations are not included in this version). Its performance still has room for improvement; we will add these optimizations in subsequent CLs.

In general, the performance changes for the basic version of SwissTable are as follows.

There is a significant improvement (20% ~ 50%) when querying a large hashmap or querying an element that does not exist in the hashmap. When querying a hashmap with fewer elements, performance degradation is up to 20%.
Insertions and deletions have been significantly improved in almost all cases (20% ~ 50%).
The performance of iterate is improved by about 10%.
Memory usage is reduced by 0% ~ 25% in most cases. Reusing a fixed-size hashmap no longer consumes any extra memory.
Since the growth is done at once, the CPU usage is significantly reduced in the case of continuous growth, but in some cases, the CPU consumption may also increase significantly.

Platform

GO: linux/amd64
CPU: AMD 3700x(8C16T)
OS: Ubuntu 22.04.1 LTS (GNU/Linux 5.15.0-43-generic x86_64)
MEMORY: 16G x 2 (DDR4 3200MHz)

Benchmark-1

Located in https://github.com/zhangyunhao116/gomapbench

This benchmark contains performance comparisons of common operations of common types in different situations.

INFO

name                                   old time/op    new time/op    delta
MapIter/Int/6-16                         60.2ns ± 1%    55.7ns ± 0%    -7.35%  (p=0.000 n=9+7)
MapIter/Int/12-16                         121ns ±10%     102ns ± 3%   -15.51%  (p=0.000 n=10+10)
MapIter/Int/18-16                         173ns ± 2%     165ns ± 1%    -4.58%  (p=0.000 n=10+8)
MapIter/Int/24-16                         214ns ± 4%     194ns ± 3%    -9.46%  (p=0.000 n=10+10)
MapIter/Int/30-16                         287ns ± 3%     272ns ± 2%    -5.22%  (p=0.000 n=10+9)
MapIter/Int/64-16                         609ns ± 0%     572ns ± 3%    -6.10%  (p=0.000 n=7+10)
MapIter/Int/128-16                       1.21µs ± 4%    1.17µs ± 2%    -3.63%  (p=0.004 n=10+10)
MapIter/Int/256-16                       2.46µs ± 2%    2.23µs ± 2%    -9.31%  (p=0.000 n=10+10)
MapIter/Int/512-16                       4.98µs ± 4%    4.38µs ± 2%   -12.22%  (p=0.000 n=10+10)
MapIter/Int/1024-16                      9.94µs ± 3%    8.84µs ± 2%   -11.11%  (p=0.000 n=10+10)
MapIter/Int/2048-16                      20.1µs ± 3%    17.8µs ± 1%   -11.33%  (p=0.000 n=10+10)
MapIter/Int/4096-16                      39.7µs ± 1%    35.5µs ± 2%   -10.49%  (p=0.000 n=10+10)
MapIter/Int/8192-16                      79.3µs ± 2%    71.8µs ± 1%    -9.42%  (p=0.000 n=10+10)
MapIter/Int/65536-16                      631µs ± 2%     571µs ± 1%    -9.52%  (p=0.000 n=10+9)
MapAccessHit/Int64/6-16                  4.24ns ± 1%    3.71ns ± 1%   -12.37%  (p=0.000 n=8+9)
MapAccessHit/Int64/12-16                 6.61ns ± 6%    6.63ns ±11%      ~     (p=0.796 n=9+9)
MapAccessHit/Int64/18-16                 6.74ns ± 4%    7.01ns ± 1%    +4.02%  (p=0.002 n=9+8)
MapAccessHit/Int64/24-16                 7.81ns ± 8%    8.17ns ± 5%    +4.62%  (p=0.034 n=10+8)
MapAccessHit/Int64/30-16                 6.23ns ± 6%    6.99ns ± 1%   +12.34%  (p=0.000 n=10+7)
MapAccessHit/Int64/64-16                 6.68ns ± 6%    7.22ns ± 2%    +8.08%  (p=0.000 n=10+9)
MapAccessHit/Int64/128-16                6.98ns ± 6%    7.32ns ± 6%    +4.93%  (p=0.004 n=10+10)
MapAccessHit/Int64/256-16                7.12ns ± 2%    7.28ns ± 2%    +2.21%  (p=0.002 n=9+10)
MapAccessHit/Int64/512-16                7.68ns ± 4%    7.40ns ± 2%    -3.65%  (p=0.000 n=9+10)
MapAccessHit/Int64/1024-16               8.85ns ± 2%    7.35ns ± 2%   -16.92%  (p=0.000 n=10+9)
MapAccessHit/Int64/2048-16               11.2ns ± 3%     7.7ns ± 1%   -31.23%  (p=0.000 n=10+8)
MapAccessHit/Int64/4096-16               14.1ns ± 1%     7.9ns ± 1%   -43.96%  (p=0.000 n=7+8)
MapAccessHit/Int64/8192-16               16.2ns ± 2%     8.2ns ± 2%   -49.14%  (p=0.000 n=10+10)
MapAccessHit/Int64/65536-16              19.6ns ± 2%    10.5ns ± 1%   -46.18%  (p=0.000 n=10+9)
MapAccessHit/Int32/6-16                  3.78ns ± 1%    3.86ns ± 1%    +2.12%  (p=0.000 n=10+8)
MapAccessHit/Int32/12-16                 6.23ns ± 6%    6.16ns ± 4%      ~     (p=0.483 n=10+9)
MapAccessHit/Int32/18-16                 6.42ns ± 5%    6.99ns ± 3%    +8.91%  (p=0.000 n=10+9)
MapAccessHit/Int32/24-16                 7.46ns ± 5%    8.60ns ± 8%   +15.32%  (p=0.000 n=9+10)
MapAccessHit/Int32/30-16                 6.07ns ± 5%    6.97ns ± 1%   +14.88%  (p=0.000 n=10+8)
MapAccessHit/Int32/64-16                 6.50ns ± 4%    7.18ns ± 5%   +10.34%  (p=0.000 n=9+10)
MapAccessHit/Int32/128-16                6.68ns ± 6%    7.15ns ± 4%    +7.12%  (p=0.000 n=10+10)
MapAccessHit/Int32/256-16                6.81ns ± 4%    7.32ns ± 4%    +7.45%  (p=0.000 n=10+10)
MapAccessHit/Int32/512-16                7.40ns ± 3%    7.30ns ± 3%      ~     (p=0.156 n=9+10)
MapAccessHit/Int32/1024-16               8.46ns ± 2%    7.38ns ± 1%   -12.79%  (p=0.000 n=10+9)
MapAccessHit/Int32/2048-16               11.0ns ± 3%     7.6ns ± 2%   -31.46%  (p=0.000 n=10+10)
MapAccessHit/Int32/4096-16               13.9ns ± 2%     7.8ns ± 2%   -44.12%  (p=0.000 n=10+10)
MapAccessHit/Int32/8192-16               15.8ns ± 2%     8.1ns ± 1%   -48.99%  (p=0.000 n=10+10)
MapAccessHit/Int32/65536-16              19.0ns ± 2%    10.3ns ± 2%   -45.85%  (p=0.000 n=10+10)
MapAccessHit/Str/6-16                    13.5ns ± 1%    12.7ns ± 2%    -5.88%  (p=0.000 n=9+10)
MapAccessHit/Str/12-16                   9.77ns ±11%    9.40ns ± 2%      ~     (p=0.460 n=10+8)
MapAccessHit/Str/18-16                   9.05ns ± 7%    9.47ns ± 1%    +4.66%  (p=0.001 n=9+9)
MapAccessHit/Str/24-16                   9.92ns ± 7%   10.07ns ± 9%      ~     (p=0.604 n=9+10)
MapAccessHit/Str/30-16                   8.46ns ± 7%    9.43ns ± 1%   +11.50%  (p=0.000 n=10+8)
MapAccessHit/Str/64-16                   8.91ns ± 5%    9.57ns ± 2%    +7.39%  (p=0.000 n=10+8)
MapAccessHit/Str/128-16                  9.82ns ± 4%   10.58ns ± 5%    +7.75%  (p=0.000 n=10+10)
MapAccessHit/Str/256-16                  11.8ns ± 4%    11.4ns ± 1%    -3.01%  (p=0.008 n=10+8)
MapAccessHit/Str/512-16                  14.6ns ± 2%    11.9ns ± 2%   -18.89%  (p=0.000 n=8+9)
MapAccessHit/Str/1024-16                 17.9ns ± 2%    12.7ns ± 1%   -29.02%  (p=0.000 n=10+9)
MapAccessHit/Str/2048-16                 21.5ns ± 3%    13.0ns ± 2%   -39.43%  (p=0.000 n=10+9)
MapAccessHit/Str/4096-16                 25.1ns ± 1%    13.2ns ± 2%   -47.63%  (p=0.000 n=10+10)
MapAccessHit/Str/8192-16                 26.6ns ± 1%    14.2ns ± 1%   -46.62%  (p=0.000 n=9+9)
MapAccessHit/Str/65536-16                31.8ns ± 1%    17.3ns ± 2%   -45.64%  (p=0.000 n=10+10)
MapAccessMiss/Int64/6-16                 8.03ns ± 1%    7.35ns ± 1%    -8.39%  (p=0.000 n=10+10)
MapAccessMiss/Int64/12-16                10.2ns ± 2%    18.3ns ± 3%   +79.48%  (p=0.000 n=8+8)
MapAccessMiss/Int64/18-16                10.3ns ± 1%     7.2ns ± 1%   -29.85%  (p=0.000 n=9+8)
MapAccessMiss/Int64/24-16                13.9ns ± 2%    10.8ns ± 2%   -22.43%  (p=0.000 n=7+8)
MapAccessMiss/Int64/30-16                10.1ns ± 3%     7.1ns ± 3%   -29.69%  (p=0.000 n=8+8)
MapAccessMiss/Int64/64-16                10.3ns ± 1%     7.9ns ±12%   -23.29%  (p=0.000 n=7+10)
MapAccessMiss/Int64/128-16               10.2ns ± 2%     7.6ns ± 8%   -25.64%  (p=0.000 n=10+9)
MapAccessMiss/Int64/256-16               10.4ns ± 2%     7.9ns ± 7%   -23.40%  (p=0.000 n=9+9)
MapAccessMiss/Int64/512-16               10.3ns ± 3%     7.9ns ± 8%   -23.37%  (p=0.000 n=9+10)
MapAccessMiss/Int64/1024-16              10.4ns ± 2%     8.0ns ± 4%   -22.40%  (p=0.000 n=9+10)
MapAccessMiss/Int64/2048-16              10.4ns ± 2%     7.9ns ± 3%   -23.97%  (p=0.000 n=10+10)
MapAccessMiss/Int64/4096-16              10.4ns ± 2%     8.2ns ± 3%   -21.67%  (p=0.000 n=10+10)
MapAccessMiss/Int64/8192-16              10.3ns ± 2%     8.6ns ± 3%   -16.95%  (p=0.000 n=10+10)
MapAccessMiss/Int64/65536-16             13.5ns ± 2%    10.9ns ± 3%   -19.23%  (p=0.000 n=9+8)
MapAccessMiss/Int32/6-16                 6.17ns ± 2%    7.45ns ± 2%   +20.86%  (p=0.000 n=10+10)
MapAccessMiss/Int32/12-16                8.50ns ± 1%   15.94ns ± 3%   +87.44%  (p=0.000 n=8+8)
MapAccessMiss/Int32/18-16                8.49ns ± 2%    8.21ns ±30%      ~     (p=0.156 n=9+10)
MapAccessMiss/Int32/24-16                11.9ns ± 2%    10.8ns ± 2%    -9.03%  (p=0.000 n=8+7)
MapAccessMiss/Int32/30-16                8.48ns ± 1%    7.53ns ±15%      ~     (p=0.138 n=10+10)
MapAccessMiss/Int32/64-16                8.49ns ± 1%    8.11ns ±17%    -4.50%  (p=0.034 n=8+10)
MapAccessMiss/Int32/128-16               8.89ns ± 2%    7.86ns ±10%   -11.57%  (p=0.000 n=7+10)
MapAccessMiss/Int32/256-16               8.72ns ± 3%    7.83ns ± 3%   -10.23%  (p=0.000 n=10+9)
MapAccessMiss/Int32/512-16               8.79ns ± 4%    7.70ns ± 4%   -12.40%  (p=0.000 n=10+9)
MapAccessMiss/Int32/1024-16              8.81ns ± 1%    7.74ns ± 5%   -12.10%  (p=0.000 n=9+10)
MapAccessMiss/Int32/2048-16              9.16ns ± 1%    7.91ns ± 2%   -13.64%  (p=0.000 n=7+9)
MapAccessMiss/Int32/4096-16              9.40ns ± 2%    8.15ns ± 3%   -13.29%  (p=0.000 n=9+9)
MapAccessMiss/Int32/8192-16              9.47ns ± 2%    8.29ns ± 2%   -12.45%  (p=0.000 n=9+9)
MapAccessMiss/Int32/65536-16             12.9ns ± 2%    10.6ns ± 2%   -18.32%  (p=0.000 n=8+10)
MapAccessMiss/Str/6-16                   5.69ns ± 1%    6.89ns ± 1%   +21.05%  (p=0.000 n=10+9)
MapAccessMiss/Str/12-16                  11.7ns ± 5%    10.6ns ±11%    -9.74%  (p=0.001 n=10+10)
MapAccessMiss/Str/18-16                  10.2ns ± 1%     9.6ns ± 1%    -5.81%  (p=0.000 n=8+8)
MapAccessMiss/Str/24-16                  12.5ns ±11%    11.4ns ± 9%    -8.83%  (p=0.011 n=10+10)
MapAccessMiss/Str/30-16                  10.8ns ± 4%     8.9ns ± 1%   -17.66%  (p=0.000 n=10+8)
MapAccessMiss/Str/64-16                  10.8ns ± 4%     9.3ns ± 8%   -13.63%  (p=0.000 n=10+10)
MapAccessMiss/Str/128-16                 12.0ns ± 7%     9.9ns ±10%   -17.57%  (p=0.000 n=10+10)
MapAccessMiss/Str/256-16                 11.2ns ± 3%    10.0ns ± 5%   -11.09%  (p=0.000 n=10+10)
MapAccessMiss/Str/512-16                 11.1ns ± 3%     9.6ns ± 6%   -13.51%  (p=0.000 n=10+10)
MapAccessMiss/Str/1024-16                12.3ns ± 2%     9.7ns ± 3%   -20.85%  (p=0.000 n=10+10)
MapAccessMiss/Str/2048-16                15.7ns ± 2%    10.1ns ± 4%   -35.32%  (p=0.000 n=10+10)
MapAccessMiss/Str/4096-16                14.0ns ± 3%    10.2ns ± 3%   -27.20%  (p=0.000 n=10+10)
MapAccessMiss/Str/8192-16                14.1ns ± 2%    10.9ns ± 4%   -22.70%  (p=0.000 n=10+10)
MapAccessMiss/Str/65536-16               19.2ns ± 2%    13.6ns ± 4%   -29.47%  (p=0.000 n=10+10)
MapAssignGrow/Int64/6-16                 69.1ns ± 1%    69.5ns ± 1%      ~     (p=0.133 n=9+10)
MapAssignGrow/Int64/12-16                 759ns ± 0%     539ns ± 0%   -28.91%  (p=0.000 n=7+10)
MapAssignGrow/Int64/18-16                1.67µs ± 0%    1.19µs ± 1%   -28.56%  (p=0.000 n=10+10)
MapAssignGrow/Int64/24-16                2.02µs ± 0%    1.36µs ± 0%   -32.89%  (p=0.000 n=10+10)
MapAssignGrow/Int64/30-16                3.53µs ± 0%    2.53µs ± 0%   -28.19%  (p=0.000 n=8+10)
MapAssignGrow/Int64/64-16                7.84µs ± 1%    5.38µs ± 1%   -31.36%  (p=0.000 n=10+10)
MapAssignGrow/Int64/128-16               15.5µs ± 0%    10.9µs ± 0%   -29.52%  (p=0.000 n=9+10)
MapAssignGrow/Int64/256-16               30.2µs ± 0%    21.9µs ± 0%   -27.59%  (p=0.000 n=10+10)
MapAssignGrow/Int64/512-16               58.8µs ± 0%    43.7µs ± 0%   -25.58%  (p=0.000 n=10+9)
MapAssignGrow/Int64/1024-16               116µs ± 0%      88µs ± 0%   -24.24%  (p=0.000 n=10+9)
MapAssignGrow/Int64/2048-16               231µs ± 0%     175µs ± 0%   -24.04%  (p=0.000 n=10+10)
MapAssignGrow/Int64/4096-16               458µs ± 0%     351µs ± 0%   -23.49%  (p=0.000 n=10+10)
MapAssignGrow/Int64/8192-16               919µs ± 0%     712µs ± 0%   -22.51%  (p=0.000 n=10+10)
MapAssignGrow/Int64/65536-16             8.69ms ± 1%    6.29ms ± 0%   -27.66%  (p=0.000 n=10+7)
MapAssignGrow/Int32/6-16                 71.7ns ± 1%    67.6ns ± 1%    -5.72%  (p=0.000 n=9+10)
MapAssignGrow/Int32/12-16                 734ns ± 0%     521ns ± 0%   -29.00%  (p=0.000 n=9+10)
MapAssignGrow/Int32/18-16                1.61µs ± 1%    1.15µs ± 0%   -28.59%  (p=0.000 n=10+7)
MapAssignGrow/Int32/24-16                1.97µs ± 0%    1.32µs ± 0%   -33.10%  (p=0.000 n=10+9)
MapAssignGrow/Int32/30-16                3.41µs ± 0%    2.43µs ± 1%   -28.67%  (p=0.000 n=10+10)
MapAssignGrow/Int32/64-16                7.45µs ± 0%    5.13µs ± 0%   -31.09%  (p=0.000 n=10+10)
MapAssignGrow/Int32/128-16               15.0µs ± 0%    10.7µs ± 0%   -28.89%  (p=0.000 n=10+9)
MapAssignGrow/Int32/256-16               29.8µs ± 0%    22.0µs ± 1%   -26.05%  (p=0.000 n=9+10)
MapAssignGrow/Int32/512-16               58.1µs ± 0%    42.9µs ± 0%   -26.07%  (p=0.000 n=10+8)
MapAssignGrow/Int32/1024-16               115µs ± 0%      86µs ± 0%   -24.96%  (p=0.000 n=10+10)
MapAssignGrow/Int32/2048-16               226µs ± 1%     171µs ± 1%   -24.44%  (p=0.000 n=10+10)
MapAssignGrow/Int32/4096-16               445µs ± 1%     341µs ± 0%   -23.31%  (p=0.000 n=10+10)
MapAssignGrow/Int32/8192-16               900µs ± 0%     686µs ± 0%   -23.72%  (p=0.000 n=10+10)
MapAssignGrow/Int32/65536-16             7.96ms ± 0%    6.11ms ± 1%   -23.18%  (p=0.000 n=7+10)
MapAssignGrow/Str/6-16                   86.5ns ± 2%    91.6ns ± 2%    +5.88%  (p=0.000 n=10+10)
MapAssignGrow/Str/12-16                   908ns ± 0%     719ns ± 0%   -20.87%  (p=0.000 n=10+10)
MapAssignGrow/Str/18-16                  2.01µs ± 0%    1.59µs ± 0%   -20.98%  (p=0.000 n=7+8)
MapAssignGrow/Str/24-16                  2.36µs ± 0%    1.79µs ± 1%   -23.93%  (p=0.000 n=10+10)
MapAssignGrow/Str/30-16                  4.17µs ± 0%    3.22µs ± 0%   -22.72%  (p=0.000 n=10+10)
MapAssignGrow/Str/64-16                  9.21µs ± 0%    6.73µs ± 0%   -26.96%  (p=0.000 n=7+9)
MapAssignGrow/Str/128-16                 18.6µs ± 0%    13.4µs ± 1%   -27.60%  (p=0.000 n=8+10)
MapAssignGrow/Str/256-16                 35.5µs ± 0%    26.8µs ± 0%   -24.53%  (p=0.000 n=10+10)
MapAssignGrow/Str/512-16                 70.6µs ± 0%    53.3µs ± 0%   -24.58%  (p=0.000 n=10+10)
MapAssignGrow/Str/1024-16                 142µs ± 1%     109µs ± 0%   -23.46%  (p=0.000 n=9+10)
MapAssignGrow/Str/2048-16                 289µs ± 1%     221µs ± 0%   -23.54%  (p=0.000 n=10+9)
MapAssignGrow/Str/4096-16                 588µs ± 0%     448µs ± 0%   -23.83%  (p=0.000 n=9+9)
MapAssignGrow/Str/8192-16                1.27ms ± 1%    0.91ms ± 0%   -28.82%  (p=0.000 n=10+10)
MapAssignGrow/Str/65536-16               12.4ms ± 1%     9.9ms ± 1%   -20.47%  (p=0.000 n=10+9)
MapAssignPreAllocate/Pointer/6-16         310ns ± 1%     281ns ± 0%    -9.41%  (p=0.000 n=10+7)
MapAssignPreAllocate/Pointer/12-16        864ns ± 0%     668ns ± 1%   -22.73%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/18-16       1.31µs ± 0%    0.97µs ± 0%   -25.94%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/24-16       1.77µs ± 0%    1.26µs ± 0%   -29.07%  (p=0.000 n=10+9)
MapAssignPreAllocate/Pointer/30-16       2.16µs ± 0%    1.60µs ± 1%   -26.13%  (p=0.000 n=10+9)
MapAssignPreAllocate/Pointer/64-16       4.73µs ± 1%    3.23µs ± 0%   -31.72%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/128-16      9.18µs ± 0%    6.36µs ± 1%   -30.65%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/256-16      18.0µs ± 0%    12.4µs ± 0%   -30.98%  (p=0.000 n=8+10)
MapAssignPreAllocate/Pointer/512-16      36.2µs ± 1%    24.6µs ± 0%   -32.11%  (p=0.000 n=10+8)
MapAssignPreAllocate/Pointer/1024-16     72.4µs ± 1%    50.3µs ± 0%   -30.49%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/2048-16      145µs ± 1%     102µs ± 0%   -29.93%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/4096-16      291µs ± 0%     209µs ± 1%   -28.18%  (p=0.000 n=10+9)
MapAssignPreAllocate/Pointer/8192-16      590µs ± 0%     444µs ± 1%   -24.76%  (p=0.000 n=10+10)
MapAssignPreAllocate/Pointer/65536-16    6.21ms ± 1%    5.68ms ± 1%    -8.48%  (p=0.000 n=9+9)
MapAssignPreAllocate/Int64/6-16          74.7ns ± 2%    71.2ns ± 2%    -4.68%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int64/12-16          540ns ± 0%     360ns ± 0%   -33.39%  (p=0.000 n=9+9)
MapAssignPreAllocate/Int64/18-16          811ns ± 0%     525ns ± 0%   -35.20%  (p=0.000 n=9+9)
MapAssignPreAllocate/Int64/24-16         1.16µs ± 0%    0.68µs ± 1%   -41.94%  (p=0.000 n=9+10)
MapAssignPreAllocate/Int64/30-16         1.33µs ± 1%    0.87µs ± 1%   -34.60%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int64/64-16         2.97µs ± 1%    1.75µs ± 0%   -41.01%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int64/128-16        5.73µs ± 0%    3.39µs ± 0%   -40.79%  (p=0.000 n=9+8)
MapAssignPreAllocate/Int64/256-16        11.0µs ± 0%     6.5µs ± 0%   -40.50%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int64/512-16        21.8µs ± 0%    12.9µs ± 0%   -40.91%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int64/1024-16       43.6µs ± 0%    26.4µs ± 0%   -39.42%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int64/2048-16       88.0µs ± 1%    52.5µs ± 0%   -40.40%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int64/4096-16        175µs ± 0%     108µs ± 0%   -38.60%  (p=0.000 n=9+10)
MapAssignPreAllocate/Int64/8192-16        362µs ± 0%     224µs ± 1%   -38.10%  (p=0.000 n=8+10)
MapAssignPreAllocate/Int64/65536-16      3.78ms ± 0%    3.21ms ± 2%   -15.14%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/6-16          72.8ns ± 1%    69.2ns ± 1%    -4.98%  (p=0.000 n=9+10)
MapAssignPreAllocate/Int32/12-16          503ns ± 0%     342ns ± 0%   -32.02%  (p=0.000 n=10+9)
MapAssignPreAllocate/Int32/18-16          770ns ± 1%     498ns ± 1%   -35.29%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int32/24-16         1.11µs ± 1%    0.65µs ± 0%   -41.79%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int32/30-16         1.26µs ± 0%    0.81µs ± 1%   -35.71%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int32/64-16         2.79µs ± 1%    1.63µs ± 0%   -41.60%  (p=0.000 n=10+9)
MapAssignPreAllocate/Int32/128-16        5.60µs ± 1%    3.39µs ± 1%   -39.52%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/256-16        11.1µs ± 1%     6.7µs ± 1%   -39.66%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/512-16        21.6µs ± 0%    12.2µs ± 0%   -43.30%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/1024-16       42.4µs ± 1%    24.2µs ± 0%   -42.91%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/2048-16       84.9µs ± 0%    50.0µs ± 0%   -41.08%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int32/4096-16        173µs ± 0%     104µs ± 0%   -40.04%  (p=0.000 n=10+10)
MapAssignPreAllocate/Int32/8192-16        347µs ± 1%     212µs ± 1%   -39.07%  (p=0.000 n=10+8)
MapAssignPreAllocate/Int32/65536-16      3.69ms ± 1%    3.07ms ± 2%   -16.96%  (p=0.000 n=10+10)
MapAssignPreAllocate/Str/6-16            89.6ns ± 2%    94.6ns ± 1%    +5.49%  (p=0.000 n=9+7)
MapAssignPreAllocate/Str/12-16            641ns ± 1%     504ns ± 0%   -21.37%  (p=0.000 n=9+9)
MapAssignPreAllocate/Str/18-16           1.01µs ± 0%    0.76µs ± 0%   -24.98%  (p=0.000 n=7+8)
MapAssignPreAllocate/Str/24-16           1.36µs ± 0%    0.96µs ± 0%   -29.74%  (p=0.000 n=9+9)
MapAssignPreAllocate/Str/30-16           1.68µs ± 0%    1.22µs ± 0%   -27.15%  (p=0.000 n=10+9)
MapAssignPreAllocate/Str/64-16           3.82µs ± 0%    2.43µs ± 0%   -36.29%  (p=0.000 n=10+10)
MapAssignPreAllocate/Str/128-16          7.60µs ± 0%    4.66µs ± 0%   -38.67%  (p=0.000 n=9+10)
MapAssignPreAllocate/Str/256-16          13.8µs ± 0%     9.2µs ± 0%   -33.55%  (p=0.000 n=10+10)
MapAssignPreAllocate/Str/512-16          27.5µs ± 0%    18.2µs ± 0%   -33.89%  (p=0.000 n=10+9)
MapAssignPreAllocate/Str/1024-16         55.4µs ± 0%    37.8µs ± 0%   -31.90%  (p=0.000 n=10+10)
MapAssignPreAllocate/Str/2048-16          111µs ± 0%      77µs ± 0%   -30.20%  (p=0.000 n=9+9)
MapAssignPreAllocate/Str/4096-16          226µs ± 0%     159µs ± 0%   -29.57%  (p=0.000 n=10+9)
MapAssignPreAllocate/Str/8192-16          481µs ± 0%     368µs ± 1%   -23.34%  (p=0.000 n=9+10)
MapAssignPreAllocate/Str/65536-16        4.83ms ± 1%    4.11ms ± 1%   -14.86%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/6-16               330ns ± 2%     290ns ± 1%   -12.18%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/12-16              757ns ± 1%     550ns ± 1%   -27.35%  (p=0.000 n=9+9)
MapAssignReuse/Pointer/18-16             1.16µs ± 1%    0.81µs ± 1%   -30.13%  (p=0.000 n=9+10)
MapAssignReuse/Pointer/24-16             1.61µs ± 1%    1.08µs ± 1%   -32.59%  (p=0.000 n=8+10)
MapAssignReuse/Pointer/30-16             1.91µs ± 2%    1.31µs ± 1%   -31.72%  (p=0.000 n=10+9)
MapAssignReuse/Pointer/64-16             4.12µs ± 1%    2.75µs ± 1%   -33.26%  (p=0.000 n=8+9)
MapAssignReuse/Pointer/128-16            8.22µs ± 2%    5.50µs ± 1%   -33.03%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/256-16            16.4µs ± 1%    11.0µs ± 1%   -33.01%  (p=0.000 n=9+10)
MapAssignReuse/Pointer/512-16            33.1µs ± 2%    21.9µs ± 1%   -33.72%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/1024-16           66.7µs ± 2%    44.8µs ± 1%   -32.78%  (p=0.000 n=10+9)
MapAssignReuse/Pointer/2048-16            132µs ± 2%      92µs ± 1%   -30.11%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/4096-16            268µs ± 1%     187µs ± 1%   -30.25%  (p=0.000 n=9+10)
MapAssignReuse/Pointer/8192-16            546µs ± 4%     389µs ± 1%   -28.67%  (p=0.000 n=10+10)
MapAssignReuse/Pointer/65536-16          5.14ms ± 3%    4.18ms ± 1%   -18.60%  (p=0.000 n=10+10)
MapAssignReuse/Int64/6-16                81.1ns ± 1%    74.8ns ± 2%    -7.75%  (p=0.000 n=10+10)
MapAssignReuse/Int64/12-16                413ns ± 3%     152ns ± 1%   -63.04%  (p=0.000 n=9+10)
MapAssignReuse/Int64/18-16                429ns ± 3%     223ns ± 1%   -48.00%  (p=0.000 n=8+10)
MapAssignReuse/Int64/24-16               1.01µs ± 4%    0.30µs ± 1%   -69.93%  (p=0.000 n=10+9)
MapAssignReuse/Int64/30-16                618ns ± 3%     358ns ± 2%   -42.00%  (p=0.000 n=9+10)
MapAssignReuse/Int64/64-16               1.31µs ± 1%    0.75µs ± 2%   -42.74%  (p=0.000 n=8+8)
MapAssignReuse/Int64/128-16              2.64µs ± 3%    1.51µs ± 2%   -42.96%  (p=0.000 n=9+10)
MapAssignReuse/Int64/256-16              5.23µs ± 4%    3.00µs ± 2%   -42.59%  (p=0.000 n=10+10)
MapAssignReuse/Int64/512-16              10.3µs ± 3%     6.0µs ± 1%   -41.70%  (p=0.000 n=10+8)
MapAssignReuse/Int64/1024-16             21.0µs ± 2%    12.1µs ± 2%   -42.09%  (p=0.000 n=10+10)
MapAssignReuse/Int64/2048-16             42.2µs ± 2%    25.5µs ± 2%   -39.56%  (p=0.000 n=10+10)
MapAssignReuse/Int64/4096-16             85.3µs ± 3%    51.3µs ± 2%   -39.88%  (p=0.000 n=10+10)
MapAssignReuse/Int64/8192-16              176µs ± 3%     107µs ± 2%   -39.54%  (p=0.000 n=10+10)
MapAssignReuse/Int64/65536-16            1.73ms ± 3%    1.16ms ± 2%   -33.33%  (p=0.000 n=10+10)
MapAssignReuse/Int32/6-16                79.6ns ± 1%    72.4ns ± 2%    -9.14%  (p=0.000 n=10+10)
MapAssignReuse/Int32/12-16                356ns ± 7%     150ns ± 1%   -57.73%  (p=0.000 n=9+10)
MapAssignReuse/Int32/18-16                394ns ± 5%     217ns ± 2%   -44.82%  (p=0.000 n=9+9)
MapAssignReuse/Int32/24-16               1.01µs ± 7%    0.29µs ± 2%   -70.98%  (p=0.000 n=10+10)
MapAssignReuse/Int32/30-16                618ns ± 5%     348ns ± 2%   -43.68%  (p=0.000 n=10+10)
MapAssignReuse/Int32/64-16               1.29µs ± 4%    0.73µs ± 2%   -43.23%  (p=0.000 n=10+10)
MapAssignReuse/Int32/128-16              2.61µs ± 3%    1.46µs ± 2%   -43.88%  (p=0.000 n=10+10)
MapAssignReuse/Int32/256-16              5.21µs ± 3%    2.92µs ± 2%   -43.90%  (p=0.000 n=10+10)
MapAssignReuse/Int32/512-16              10.2µs ± 3%     5.9µs ± 1%   -42.54%  (p=0.000 n=10+9)
MapAssignReuse/Int32/1024-16             20.5µs ± 3%    11.8µs ± 1%   -42.72%  (p=0.000 n=10+9)
MapAssignReuse/Int32/2048-16             41.7µs ± 3%    24.8µs ± 2%   -40.50%  (p=0.000 n=9+10)
MapAssignReuse/Int32/4096-16             84.5µs ± 2%    50.8µs ± 1%   -39.93%  (p=0.000 n=10+9)
MapAssignReuse/Int32/8192-16              170µs ± 1%     103µs ± 2%   -39.52%  (p=0.000 n=10+8)
MapAssignReuse/Int32/65536-16            1.68ms ± 3%    1.12ms ± 2%   -33.25%  (p=0.000 n=10+10)
MapAssignReuse/Str/6-16                  96.8ns ± 3%   102.0ns ± 1%    +5.33%  (p=0.000 n=10+10)
MapAssignReuse/Str/12-16                  491ns ± 3%     202ns ± 1%   -58.99%  (p=0.000 n=8+9)
MapAssignReuse/Str/18-16                  500ns ± 4%     292ns ± 2%   -41.68%  (p=0.000 n=10+10)
MapAssignReuse/Str/24-16                 1.13µs ± 3%    0.40µs ± 1%   -64.33%  (p=0.000 n=9+10)
MapAssignReuse/Str/30-16                  783ns ± 5%     480ns ± 2%   -38.77%  (p=0.000 n=10+10)
MapAssignReuse/Str/64-16                 1.53µs ± 2%    1.02µs ± 2%   -33.00%  (p=0.000 n=10+10)
MapAssignReuse/Str/128-16                3.06µs ± 1%    2.04µs ± 2%   -33.22%  (p=0.000 n=10+10)
MapAssignReuse/Str/256-16                6.15µs ± 3%    4.08µs ± 2%   -33.59%  (p=0.000 n=9+10)
MapAssignReuse/Str/512-16                12.3µs ± 3%     8.2µs ± 1%   -33.49%  (p=0.000 n=10+10)
MapAssignReuse/Str/1024-16               25.3µs ± 2%    17.1µs ± 2%   -32.55%  (p=0.000 n=10+10)
MapAssignReuse/Str/2048-16               50.7µs ± 3%    34.6µs ± 2%   -31.79%  (p=0.000 n=10+10)
MapAssignReuse/Str/4096-16                103µs ± 2%      70µs ± 2%   -31.98%  (p=0.000 n=10+10)
MapAssignReuse/Str/8192-16                218µs ± 1%     157µs ± 2%   -28.32%  (p=0.000 n=9+10)
MapAssignReuse/Str/65536-16              2.03ms ± 1%    1.64ms ± 2%   -19.62%  (p=0.000 n=10+9)
name MapIter/Int/6-16 MapIter/Int/12-16 MapIter/Int/18-16 MapIter/Int/24-16 MapIter/Int/30-16 MapIter/Int/64-16 MapIter/Int/128-16 MapIter/Int/256-16 MapIter/Int/512-16 MapIter/Int/1024-16 MapIter/Int/2048-16 MapIter/Int/4096-16 MapIter/Int/8192-16 MapIter/Int/65536-16 MapAccessHit/Int64/6-16 MapAccessHit/Int64/12-16 MapAccessHit/Int64/18-16 MapAccessHit/Int64/24-16 MapAccessHit/Int64/30-16 MapAccessHit/Int64/64-16 MapAccessHit/Int64/128-16 MapAccessHit/Int64/256-16 MapAccessHit/Int64/512-16 MapAccessHit/Int64/1024-16 MapAccessHit/Int64/2048-16 MapAccessHit/Int64/4096-16 MapAccessHit/Int64/8192-16 MapAccessHit/Int64/65536-16 MapAccessHit/Int32/6-16 MapAccessHit/Int32/12-16 MapAccessHit/Int32/18-16 MapAccessHit/Int32/24-16 MapAccessHit/Int32/30-16 MapAccessHit/Int32/64-16 MapAccessHit/Int32/128-16 MapAccessHit/Int32/256-16 MapAccessHit/Int32/512-16 MapAccessHit/Int32/1024-16 MapAccessHit/Int32/2048-16 MapAccessHit/Int32/4096-16 MapAccessHit/Int32/8192-16 MapAccessHit/Int32/65536-16 MapAccessHit/Str/6-16 MapAccessHit/Str/12-16 MapAccessHit/Str/18-16 MapAccessHit/Str/24-16 MapAccessHit/Str/30-16 MapAccessHit/Str/64-16 MapAccessHit/Str/128-16 MapAccessHit/Str/256-16 MapAccessHit/Str/512-16 MapAccessHit/Str/1024-16 MapAccessHit/Str/2048-16 MapAccessHit/Str/4096-16 MapAccessHit/Str/8192-16 MapAccessHit/Str/65536-16 MapAccessMiss/Int64/6-16 MapAccessMiss/Int64/12-16 MapAccessMiss/Int64/18-16 MapAccessMiss/Int64/24-16 MapAccessMiss/Int64/30-16 MapAccessMiss/Int64/64-16 MapAccessMiss/Int64/128-16 MapAccessMiss/Int64/256-16 MapAccessMiss/Int64/512-16 MapAccessMiss/Int64/1024-16 MapAccessMiss/Int64/2048-16 MapAccessMiss/Int64/4096-16 MapAccessMiss/Int64/8192-16 MapAccessMiss/Int64/65536-16 MapAccessMiss/Int32/6-16 MapAccessMiss/Int32/12-16 MapAccessMiss/Int32/18-16 MapAccessMiss/Int32/24-16 MapAccessMiss/Int32/30-16 MapAccessMiss/Int32/64-16 MapAccessMiss/Int32/128-16 MapAccessMiss/Int32/256-16 MapAccessMiss/Int32/512-16 MapAccessMiss/Int32/1024-16 MapAccessMiss/Int32/2048-16 MapAccessMiss/Int32/4096-16 MapAccessMiss/Int32/8192-16 MapAccessMiss/Int32/65536-16 MapAccessMiss/Str/6-16 MapAccessMiss/Str/12-16 MapAccessMiss/Str/18-16 MapAccessMiss/Str/24-16 MapAccessMiss/Str/30-16 MapAccessMiss/Str/64-16 MapAccessMiss/Str/128-16 MapAccessMiss/Str/256-16 MapAccessMiss/Str/512-16 MapAccessMiss/Str/1024-16 MapAccessMiss/Str/2048-16 MapAccessMiss/Str/4096-16 MapAccessMiss/Str/8192-16 MapAccessMiss/Str/65536-16 MapAssignGrow/Int64/6-16 MapAssignGrow/Int64/12-16 MapAssignGrow/Int64/18-16 MapAssignGrow/Int64/24-16 MapAssignGrow/Int64/30-16 MapAssignGrow/Int64/64-16 MapAssignGrow/Int64/128-16 MapAssignGrow/Int64/256-16 MapAssignGrow/Int64/512-16 MapAssignGrow/Int64/1024-16 MapAssignGrow/Int64/2048-16 MapAssignGrow/Int64/4096-16 MapAssignGrow/Int64/8192-16 MapAssignGrow/Int64/65536-16 MapAssignGrow/Int32/6-16 MapAssignGrow/Int32/12-16 MapAssignGrow/Int32/18-16 MapAssignGrow/Int32/24-16 MapAssignGrow/Int32/30-16 MapAssignGrow/Int32/64-16 MapAssignGrow/Int32/128-16 MapAssignGrow/Int32/256-16 MapAssignGrow/Int32/512-16 MapAssignGrow/Int32/1024-16 MapAssignGrow/Int32/2048-16 MapAssignGrow/Int32/4096-16 MapAssignGrow/Int32/8192-16 MapAssignGrow/Int32/65536-16 MapAssignGrow/Str/6-16 MapAssignGrow/Str/12-16 MapAssignGrow/Str/18-16 MapAssignGrow/Str/24-16 MapAssignGrow/Str/30-16 MapAssignGrow/Str/64-16 MapAssignGrow/Str/128-16 MapAssignGrow/Str/256-16 MapAssignGrow/Str/512-16 MapAssignGrow/Str/1024-16 MapAssignGrow/Str/2048-16 MapAssignGrow/Str/4096-16 MapAssignGrow/Str/8192-16 MapAssignGrow/Str/65536-16 MapAssignPreAllocate/Pointer/6-16 MapAssignPreAllocate/Pointer/12-16 MapAssignPreAllocate/Pointer/18-16 MapAssignPreAllocate/Pointer/24-16 MapAssignPreAllocate/Pointer/30-16 MapAssignPreAllocate/Pointer/64-16 MapAssignPreAllocate/Pointer/128-16 MapAssignPreAllocate/Pointer/256-16 MapAssignPreAllocate/Pointer/512-16 MapAssignPreAllocate/Pointer/1024-16 MapAssignPreAllocate/Pointer/2048-16 MapAssignPreAllocate/Pointer/4096-16 MapAssignPreAllocate/Pointer/8192-16 MapAssignPreAllocate/Pointer/65536-16 MapAssignPreAllocate/Int64/6-16 MapAssignPreAllocate/Int64/12-16 MapAssignPreAllocate/Int64/18-16 MapAssignPreAllocate/Int64/24-16 MapAssignPreAllocate/Int64/30-16 MapAssignPreAllocate/Int64/64-16 MapAssignPreAllocate/Int64/128-16 MapAssignPreAllocate/Int64/256-16 MapAssignPreAllocate/Int64/512-16 MapAssignPreAllocate/Int64/1024-16 MapAssignPreAllocate/Int64/2048-16 MapAssignPreAllocate/Int64/4096-16 MapAssignPreAllocate/Int64/8192-16 MapAssignPreAllocate/Int64/65536-16 MapAssignPreAllocate/Int32/6-16 MapAssignPreAllocate/Int32/12-16 MapAssignPreAllocate/Int32/18-16 MapAssignPreAllocate/Int32/24-16 MapAssignPreAllocate/Int32/30-16 MapAssignPreAllocate/Int32/64-16 MapAssignPreAllocate/Int32/128-16 MapAssignPreAllocate/Int32/256-16 MapAssignPreAllocate/Int32/512-16 MapAssignPreAllocate/Int32/1024-16 MapAssignPreAllocate/Int32/2048-16 MapAssignPreAllocate/Int32/4096-16 MapAssignPreAllocate/Int32/8192-16 MapAssignPreAllocate/Int32/65536-16 MapAssignPreAllocate/Str/6-16 MapAssignPreAllocate/Str/12-16 MapAssignPreAllocate/Str/18-16 MapAssignPreAllocate/Str/24-16 MapAssignPreAllocate/Str/30-16 MapAssignPreAllocate/Str/64-16 MapAssignPreAllocate/Str/128-16 MapAssignPreAllocate/Str/256-16 MapAssignPreAllocate/Str/512-16 MapAssignPreAllocate/Str/1024-16 MapAssignPreAllocate/Str/2048-16 MapAssignPreAllocate/Str/4096-16 MapAssignPreAllocate/Str/8192-16 MapAssignPreAllocate/Str/65536-16 MapAssignReuse/Pointer/6-16 MapAssignReuse/Pointer/12-16 MapAssignReuse/Pointer/18-16 MapAssignReuse/Pointer/24-16 MapAssignReuse/Pointer/30-16 MapAssignReuse/Pointer/64-16 MapAssignReuse/Pointer/128-16 MapAssignReuse/Pointer/256-16 MapAssignReuse/Pointer/512-16 MapAssignReuse/Pointer/1024-16 MapAssignReuse/Pointer/2048-16 MapAssignReuse/Pointer/4096-16 MapAssignReuse/Pointer/8192-16 MapAssignReuse/Pointer/65536-16 MapAssignReuse/Int64/6-16 MapAssignReuse/Int64/12-16 MapAssignReuse/Int64/18-16 MapAssignReuse/Int64/24-16 MapAssignReuse/Int64/30-16 MapAssignReuse/Int64/64-16 MapAssignReuse/Int64/128-16 MapAssignReuse/Int64/256-16 MapAssignReuse/Int64/512-16 MapAssignReuse/Int64/1024-16 MapAssignReuse/Int64/2048-16 MapAssignReuse/Int64/4096-16 MapAssignReuse/Int64/8192-16 MapAssignReuse/Int64/65536-16 MapAssignReuse/Int32/6-16 MapAssignReuse/Int32/12-16 MapAssignReuse/Int32/18-16 MapAssignReuse/Int32/24-16 MapAssignReuse/Int32/30-16 MapAssignReuse/Int32/64-16 MapAssignReuse/Int32/128-16 MapAssignReuse/Int32/256-16 MapAssignReuse/Int32/512-16 MapAssignReuse/Int32/1024-16 MapAssignReuse/Int32/2048-16 MapAssignReuse/Int32/4096-16 MapAssignReuse/Int32/8192-16 MapAssignReuse/Int32/65536-16 MapAssignReuse/Str/6-16 MapAssignReuse/Str/12-16 MapAssignReuse/Str/18-16 MapAssignReuse/Str/24-16 MapAssignReuse/Str/30-16 MapAssignReuse/Str/64-16 MapAssignReuse/Str/128-16 MapAssignReuse/Str/256-16 MapAssignReuse/Str/512-16 MapAssignReuse/Str/1024-16 MapAssignReuse/Str/2048-16 MapAssignReuse/Str/4096-16 MapAssignReuse/Str/8192-16 MapAssignReuse/Str/65536-16

old alloc/op   new alloc/op   delta
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 317B ± 0%      288B ± 0%    -9.15%  (p=0.000 n=10+10)
 931B ± 0%      864B ± 0%    -7.20%  (p=0.000 n=10+10)
 1.01kB ± 0%    0.86kB ± 0%   -14.37%  (p=0.000 n=9+10)
 2.22kB ± 0%    2.02kB ± 0%    -9.13%  (p=0.000 n=10+10)
 5.18kB ± 0%    4.32kB ± 0%   -16.55%  (p=0.000 n=10+10)
 10.8kB ± 0%     9.2kB ± 0%   -15.18%  (p=0.000 n=10+10)
 21.5kB ± 0%    18.7kB ± 0%   -13.15%  (p=0.000 n=10+10)
 43.2kB ± 0%    37.1kB ± 0%   -14.11%  (p=0.000 n=10+10)
 86.6kB ± 0%    78.0kB ± 0%    -9.84%  (p=0.000 n=10+10)
 173kB ± 0%     152kB ± 0%   -12.43%  (p=0.000 n=10+10)
 347kB ± 0%     299kB ± 0%   -13.72%  (p=0.000 n=10+8)
 685kB ± 0%     594kB ± 0%   -13.32%  (p=0.000 n=10+8)
 5.45MB ± 0%    4.72MB ± 0%   -13.26%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 248B ± 0%      224B ± 0%    -9.68%  (p=0.000 n=10+10)
 728B ± 0%      672B ± 0%    -7.69%  (p=0.000 n=10+10)
 793B ± 0%      672B ± 0%   -15.26%  (p=0.000 n=10+10)
 1.74kB ± 0%    1.57kB ± 0%    -9.70%  (p=0.000 n=10+10)
 4.01kB ± 0%    3.36kB ± 0%   -16.15%  (p=0.000 n=9+10)
 8.34kB ± 0%    7.46kB ± 0%   -10.56%  (p=0.000 n=10+10)
 17.0kB ± 0%    15.6kB ± 0%    -7.90%  (p=0.000 n=10+10)
 34.2kB ± 0%    30.0kB ± 0%   -12.26%  (p=0.000 n=10+10)
 68.5kB ± 0%    58.7kB ± 0%   -14.39%  (p=0.000 n=10+10)
 137kB ± 0%     116kB ± 0%   -15.43%  (p=0.000 n=10+10)
 266kB ± 0%     231kB ± 0%   -13.33%  (p=0.000 n=10+10)
 532kB ± 0%     460kB ± 0%   -13.57%  (p=0.000 n=10+10)
 4.25MB ± 0%    3.67MB ± 0%   -13.70%  (p=0.000 n=10+8)
 0.00B          0.00B           ~     (all equal)
 446B ± 0%      416B ± 0%    -6.73%  (p=0.000 n=10+10)
 1.38kB ± 0%    1.31kB ± 0%    -5.13%  (p=0.000 n=10+10)
 1.47kB ± 0%    1.31kB ± 0%   -10.63%  (p=0.000 n=10+10)
 3.32kB ± 0%    3.10kB ± 0%    -6.62%  (p=0.000 n=10+10)
 7.76kB ± 0%    6.56kB ± 0%   -15.42%  (p=0.000 n=10+10)
 16.1kB ± 0%    13.3kB ± 0%   -16.91%  (p=0.000 n=10+10)
 30.5kB ± 0%    26.9kB ± 0%   -11.71%  (p=0.000 n=10+10)
 61.1kB ± 0%    54.2kB ± 0%   -11.30%  (p=0.000 n=10+10)
 122kB ± 0%     112kB ± 0%    -8.66%  (p=0.000 n=10+10)
 244kB ± 0%     218kB ± 0%   -10.63%  (p=0.000 n=10+10)
 487kB ± 0%     431kB ± 0%   -11.58%  (p=0.000 n=10+10)
 974kB ± 0%     857kB ± 0%   -12.05%  (p=0.000 n=10+9)
 7.74MB ± 0%    6.82MB ± 0%   -11.89%  (p=0.000 n=10+10)
 48.0B ± 0%     48.0B ± 0%      ~     (all equal)
 405B ± 0%      384B ± 0%    -5.09%  (p=0.000 n=10+10)
 731B ± 0%      720B ± 0%    -1.50%  (p=0.000 n=10+10)
 837B ± 0%      768B ± 0%    -8.24%  (p=0.000 n=9+10)
 1.40kB ± 0%    1.39kB ± 0%    -0.71%  (p=0.000 n=10+10)
 3.22kB ± 0%    2.82kB ± 0%   -12.66%  (p=0.000 n=10+10)
 6.42kB ± 0%    5.89kB ± 0%    -8.34%  (p=0.000 n=10+10)
 12.3kB ± 0%    11.5kB ± 0%    -6.43%  (p=0.000 n=10+10)
 24.6kB ± 0%    22.5kB ± 0%    -8.42%  (p=0.000 n=10+10)
 49.2kB ± 0%    49.2kB ± 0%    -0.05%  (p=0.000 n=10+10)
 98.3kB ± 0%    90.1kB ± 0%    -8.36%  (p=0.000 n=10+10)
 197kB ± 0%     180kB ± 0%    -8.34%  (p=0.000 n=9+10)
 385kB ± 0%     360kB ± 0%    -6.39%  (p=0.000 n=10+8)
 3.03MB ± 0%    2.88MB ± 0%    -4.87%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 317B ± 0%      288B ± 0%    -9.15%  (p=0.000 n=10+10)
 591B ± 0%      576B ± 0%    -2.54%  (p=0.000 n=10+10)
 672B ± 0%      576B ± 0%   -14.29%  (p=0.000 n=10+10)
 1.17kB ± 0%    1.15kB ± 0%    -1.20%  (p=0.000 n=10+10)
 2.72kB ± 0%    2.30kB ± 0%   -15.29%  (p=0.000 n=10+10)
 5.42kB ± 0%    4.86kB ± 0%   -10.23%  (p=0.000 n=10+10)
 10.3kB ± 0%     9.5kB ± 0%    -8.03%  (p=0.000 n=10+10)
 20.6kB ± 0%    18.4kB ± 0%   -10.39%  (p=0.000 n=10+10)
 41.1kB ± 0%    41.0kB ± 0%    -0.37%  (p=0.000 n=10+10)
 82.2kB ± 0%    73.7kB ± 0%   -10.30%  (p=0.000 n=10+10)
 164kB ± 0%     147kB ± 0%   -10.29%  (p=0.006 n=7+9)
 321kB ± 0%     295kB ± 0%    -7.99%  (p=0.000 n=10+9)
 2.51MB ± 0%    2.36MB ± 0%    -6.19%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 248B ± 0%      224B ± 0%    -9.68%  (p=0.000 n=10+10)
 461B ± 0%      448B ± 0%    -2.82%  (p=0.000 n=10+10)
 528B ± 0%      448B ± 0%   -15.15%  (p=0.000 n=10+10)
 908B ± 0%      896B ± 0%    -1.32%  (p=0.000 n=10+10)
 2.08kB ± 0%    1.79kB ± 0%   -13.85%  (p=0.000 n=10+10)
 4.14kB ± 0%    4.10kB ± 0%    -1.01%  (p=0.000 n=10+10)
 8.25kB ± 0%    8.19kB ± 0%    -0.71%  (p=0.000 n=10+10)
 16.5kB ± 0%    14.3kB ± 0%   -12.98%  (p=0.000 n=10+10)
 32.9kB ± 0%    28.7kB ± 0%   -12.91%  (p=0.000 n=10+10)
 65.8kB ± 0%    57.3kB ± 0%   -12.87%  (p=0.000 n=10+10)
 123kB ± 0%     115kB ± 0%    -7.07%  (p=0.000 n=10+10)
 247kB ± 0%     229kB ± 0%    -7.06%  (p=0.000 n=10+10)
 1.96MB ± 0%    1.84MB ± 0%    -6.28%  (p=0.000 n=10+9)
 0.00B          0.00B           ~     (all equal)
 446B ± 0%      416B ± 0%    -6.73%  (p=0.000 n=10+10)
 912B ± 0%      896B ± 0%    -1.75%  (p=0.000 n=10+10)
 1.00kB ± 0%    0.90kB ± 0%   -10.04%  (p=0.002 n=8+10)
 1.81kB ± 0%    1.79kB ± 0%    -0.81%  (p=0.000 n=10+10)
 4.12kB ± 0%    3.46kB ± 0%   -16.12%  (p=0.000 n=10+10)
 8.22kB ± 0%    6.78kB ± 0%   -17.43%  (p=0.000 n=10+10)
 14.4kB ± 0%    13.6kB ± 0%    -5.52%  (p=0.000 n=10+10)
 28.7kB ± 0%    27.3kB ± 0%    -4.99%  (p=0.000 n=10+10)
 57.4kB ± 0%    57.3kB ± 0%    -0.04%  (p=0.000 n=10+10)
 115kB ± 0%     106kB ± 0%    -7.16%  (p=0.000 n=10+10)
 229kB ± 0%     213kB ± 0%    -7.15%  (p=0.000 n=10+8)
 459kB ± 0%     426kB ± 0%    -7.15%  (p=0.001 n=8+9)
 3.62MB ± 0%    3.41MB ± 0%    -5.88%  (p=0.000 n=9+10)
 48.0B ± 0%     48.0B ± 0%      ~     (all equal)
 117B ± 1%       96B ± 0%   -17.74%  (p=0.000 n=10+10)
 155B ± 0%      144B ± 0%    -7.10%  (p=0.000 n=10+10)
 261B ± 0%      192B ± 0%   -26.52%  (p=0.000 n=10+10)
 250B ± 0%      240B ± 0%    -4.00%  (p=0.000 n=10+10)
 512B ± 0%      512B ± 0%      ~     (all equal)
 1.02kB ± 0%    1.02kB ± 0%      ~     (all equal)
 2.05kB ± 0%    2.05kB ± 0%      ~     (all equal)
 4.10kB ± 0%    4.10kB ± 0%      ~     (all equal)
 8.19kB ± 0%    8.19kB ± 0%      ~     (all equal)
 16.4kB ± 0%    16.4kB ± 0%      ~     (all equal)
 32.8kB ± 0%    32.8kB ± 0%      ~     (all equal)
 65.5kB ± 0%    65.5kB ± 0%      ~     (all equal)
 524kB ± 0%     524kB ± 0%      ~     (p=0.137 n=10+8)
 0.00B          0.00B           ~     (all equal)
 25.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 13.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 85.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 12.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 8.00B ± 0%     0.00B       -100.00%  (p=0.000 n=10+10)
 18.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 34.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 66.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 128B ± 0%        0B       -100.00%  (p=0.000 n=9+10)
 252B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
 506B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
 1.03kB ± 0%    0.00kB       -100.00%  (p=0.000 n=9+10)
 8.21kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 20.7B ± 3%      0.0B       -100.00%  (p=0.000 n=10+10)
 11.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 69.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 10.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 8.00B ± 0%     0.00B       -100.00%  (p=0.000 n=10+10)
 18.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 34.0B ± 0%      0.0B       -100.00%  (p=0.002 n=8+10)
 66.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 128B ± 0%        0B       -100.00%  (p=0.000 n=9+10)
 252B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
 506B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
 1.03kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
 8.21kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 30.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 16.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)
 100B ± 0%        0B       -100.00%  (p=0.000 n=10+10)
 14.7B ± 5%      0.0B       -100.00%  (p=0.000 n=10+10)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.30B ±233%     0.00B           ~     (p=0.211 n=10+10)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
 0.00B          0.00B           ~     (all equal)
name                                   old allocs/op  new allocs/op  delta

MapIter/Int/6-16                           0.00           0.00           ~     (all equal)

MapIter/Int/12-16                          0.00           0.00           ~     (all equal)

MapIter/Int/18-16                          0.00           0.00           ~     (all equal)

MapIter/Int/24-16                          0.00           0.00           ~     (all equal)

MapIter/Int/30-16                          0.00           0.00           ~     (all equal)

MapIter/Int/64-16                          0.00           0.00           ~     (all equal)

MapIter/Int/128-16                         0.00           0.00           ~     (all equal)

MapIter/Int/256-16                         0.00           0.00           ~     (all equal)

MapIter/Int/512-16                         0.00           0.00           ~     (all equal)

MapIter/Int/1024-16                        0.00           0.00           ~     (all equal)

MapIter/Int/2048-16                        0.00           0.00           ~     (all equal)

MapIter/Int/4096-16                        0.00           0.00           ~     (all equal)

MapIter/Int/8192-16                        0.00           0.00           ~     (all equal)

MapIter/Int/65536-16                       0.00           0.00           ~     (all equal)

MapAccessHit/Int64/6-16                    0.00           0.00           ~     (all equal)

MapAccessHit/Int64/12-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int64/18-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int64/24-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int64/30-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int64/64-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int64/128-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int64/256-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int64/512-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int64/1024-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int64/2048-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int64/4096-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int64/8192-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int64/65536-16                0.00           0.00           ~     (all equal)

MapAccessHit/Int32/6-16                    0.00           0.00           ~     (all equal)

MapAccessHit/Int32/12-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int32/18-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int32/24-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int32/30-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int32/64-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Int32/128-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int32/256-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int32/512-16                  0.00           0.00           ~     (all equal)

MapAccessHit/Int32/1024-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int32/2048-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int32/4096-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int32/8192-16                 0.00           0.00           ~     (all equal)

MapAccessHit/Int32/65536-16                0.00           0.00           ~     (all equal)

MapAccessHit/Str/6-16                      0.00           0.00           ~     (all equal)

MapAccessHit/Str/12-16                     0.00           0.00           ~     (all equal)

MapAccessHit/Str/18-16                     0.00           0.00           ~     (all equal)

MapAccessHit/Str/24-16                     0.00           0.00           ~     (all equal)

MapAccessHit/Str/30-16                     0.00           0.00           ~     (all equal)

MapAccessHit/Str/64-16                     0.00           0.00           ~     (all equal)

MapAccessHit/Str/128-16                    0.00           0.00           ~     (all equal)

MapAccessHit/Str/256-16                    0.00           0.00           ~     (all equal)

MapAccessHit/Str/512-16                    0.00           0.00           ~     (all equal)

MapAccessHit/Str/1024-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Str/2048-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Str/4096-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Str/8192-16                   0.00           0.00           ~     (all equal)

MapAccessHit/Str/65536-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/6-16                   0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/12-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/18-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/24-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/30-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/64-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/128-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/256-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/512-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/1024-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/2048-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/4096-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/8192-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int64/65536-16               0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/6-16                   0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/12-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/18-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/24-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/30-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/64-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/128-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/256-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/512-16                 0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/1024-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/2048-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/4096-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/8192-16                0.00           0.00           ~     (all equal)

MapAccessMiss/Int32/65536-16               0.00           0.00           ~     (all equal)

MapAccessMiss/Str/6-16                     0.00           0.00           ~     (all equal)

MapAccessMiss/Str/12-16                    0.00           0.00           ~     (all equal)

MapAccessMiss/Str/18-16                    0.00           0.00           ~     (all equal)

MapAccessMiss/Str/24-16                    0.00           0.00           ~     (all equal)

MapAccessMiss/Str/30-16                    0.00           0.00           ~     (all equal)

MapAccessMiss/Str/64-16                    0.00           0.00           ~     (all equal)

MapAccessMiss/Str/128-16                   0.00           0.00           ~     (all equal)

MapAccessMiss/Str/256-16                   0.00           0.00           ~     (all equal)

MapAccessMiss/Str/512-16                   0.00           0.00           ~     (all equal)

MapAccessMiss/Str/1024-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Str/2048-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Str/4096-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Str/8192-16                  0.00           0.00           ~     (all equal)

MapAccessMiss/Str/65536-16                 0.00           0.00           ~     (all equal)

MapAssignGrow/Int64/6-16                   0.00           0.00           ~     (all equal)

MapAssignGrow/Int64/12-16                  1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignGrow/Int64/18-16                  3.00 ± 0%      2.00 ± 0%   -33.33%  (p=0.000 n=10+10)

MapAssignGrow/Int64/24-16                  4.00 ± 0%      2.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignGrow/Int64/30-16                  6.00 ± 0%      3.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignGrow/Int64/64-16                  12.0 ± 0%       4.0 ± 0%   -66.67%  (p=0.000 n=10+10)

MapAssignGrow/Int64/128-16                 19.0 ± 0%       5.0 ± 0%   -73.68%  (p=0.000 n=10+10)

MapAssignGrow/Int64/256-16                 27.0 ± 0%       6.0 ± 0%   -77.78%  (p=0.000 n=10+10)

MapAssignGrow/Int64/512-16                 42.0 ± 0%       7.0 ± 0%   -83.33%  (p=0.000 n=10+10)

MapAssignGrow/Int64/1024-16                64.0 ± 0%       8.0 ± 0%   -87.50%  (p=0.000 n=10+10)

MapAssignGrow/Int64/2048-16                 100 ± 1%         9 ± 0%   -90.96%  (p=0.000 n=10+10)

MapAssignGrow/Int64/4096-16                 162 ± 0%        10 ± 0%   -93.81%  (p=0.000 n=10+10)

MapAssignGrow/Int64/8192-16                 274 ± 0%        11 ± 0%   -95.99%  (p=0.000 n=10+10)

MapAssignGrow/Int64/65536-16              2.35k ± 0%     0.01k ± 0%   -99.40%  (p=0.000 n=10+10)

MapAssignGrow/Int32/6-16                   0.00           0.00           ~     (all equal)

MapAssignGrow/Int32/12-16                  1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignGrow/Int32/18-16                  3.00 ± 0%      2.00 ± 0%   -33.33%  (p=0.000 n=10+10)

MapAssignGrow/Int32/24-16                  4.00 ± 0%      2.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignGrow/Int32/30-16                  6.00 ± 0%      3.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignGrow/Int32/64-16                  12.0 ± 0%       4.0 ± 0%   -66.67%  (p=0.000 n=10+10)

MapAssignGrow/Int32/128-16                 19.0 ± 0%       5.0 ± 0%   -73.68%  (p=0.000 n=10+10)

MapAssignGrow/Int32/256-16                 28.0 ± 0%       6.0 ± 0%   -78.57%  (p=0.000 n=10+10)

MapAssignGrow/Int32/512-16                 41.0 ± 0%       7.0 ± 0%   -82.93%  (p=0.000 n=10+10)

MapAssignGrow/Int32/1024-16                59.0 ± 0%       8.0 ± 0%   -86.44%  (p=0.000 n=10+10)

MapAssignGrow/Int32/2048-16                86.5 ± 1%       9.0 ± 0%   -89.60%  (p=0.000 n=10+10)

MapAssignGrow/Int32/4096-16                 131 ± 1%        10 ± 0%   -92.38%  (p=0.000 n=10+10)

MapAssignGrow/Int32/8192-16                 284 ± 0%        11 ± 0%   -96.13%  (p=0.002 n=8+10)

MapAssignGrow/Int32/65536-16              2.37k ± 0%     0.01k ± 0%   -99.41%  (p=0.000 n=10+10)

MapAssignGrow/Str/6-16                     0.00           0.00           ~     (all equal)

MapAssignGrow/Str/12-16                    1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignGrow/Str/18-16                    2.00 ± 0%      2.00 ± 0%      ~     (all equal)

MapAssignGrow/Str/24-16                    2.00 ± 0%      2.00 ± 0%      ~     (all equal)

MapAssignGrow/Str/30-16                    4.00 ± 0%      3.00 ± 0%   -25.00%  (p=0.000 n=10+10)

MapAssignGrow/Str/64-16                    7.00 ± 0%      4.00 ± 0%   -42.86%  (p=0.000 n=10+10)

MapAssignGrow/Str/128-16                   9.00 ± 0%      5.00 ± 0%   -44.44%  (p=0.000 n=10+10)

MapAssignGrow/Str/256-16                   10.0 ± 0%       6.0 ± 0%   -40.00%  (p=0.000 n=10+10)

MapAssignGrow/Str/512-16                   20.0 ± 0%       7.0 ± 0%   -65.00%  (p=0.000 n=10+10)

MapAssignGrow/Str/1024-16                  39.0 ± 0%       8.0 ± 0%   -79.49%  (p=0.000 n=10+10)

MapAssignGrow/Str/2048-16                  74.0 ± 0%       9.0 ± 0%   -87.84%  (p=0.000 n=10+10)

MapAssignGrow/Str/4096-16                   143 ± 0%        10 ± 0%   -93.01%  (p=0.000 n=10+10)

MapAssignGrow/Str/8192-16                   280 ± 0%        11 ± 0%   -96.07%  (p=0.002 n=8+10)

MapAssignGrow/Str/65536-16                2.33k ± 0%     0.01k ± 0%   -99.40%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/6-16          6.00 ± 0%      6.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Pointer/12-16         13.0 ± 0%      13.0 ± 0%      ~     (all equal)

MapAssignPreAllocate/Pointer/18-16         19.0 ± 0%      19.0 ± 0%      ~     (all equal)

MapAssignPreAllocate/Pointer/24-16         25.0 ± 0%      25.0 ± 0%      ~     (all equal)

MapAssignPreAllocate/Pointer/30-16         31.0 ± 0%      31.0 ± 0%      ~     (all equal)

MapAssignPreAllocate/Pointer/64-16         66.0 ± 0%      65.0 ± 0%    -1.52%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/128-16         130 ± 0%       129 ± 0%    -0.77%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/256-16         258 ± 0%       257 ± 0%    -0.39%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/512-16         514 ± 0%       513 ± 0%    -0.19%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/1024-16      1.03k ± 0%     1.02k ± 0%    -0.10%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/2048-16      2.05k ± 0%     2.05k ± 0%    -0.05%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/4096-16      4.10k ± 0%     4.10k ± 0%    -0.02%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/8192-16      8.19k ± 0%     8.19k ± 0%    -0.01%  (p=0.000 n=10+10)

MapAssignPreAllocate/Pointer/65536-16     65.5k ± 0%     65.5k ± 0%    -0.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/6-16            0.00           0.00           ~     (all equal)

MapAssignPreAllocate/Int64/12-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int64/18-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int64/24-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/30-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int64/64-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/128-16          3.00 ± 0%      1.00 ± 0%   -66.67%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/256-16          4.00 ± 0%      1.00 ± 0%   -75.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/512-16          5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/1024-16         6.00 ± 0%      1.00 ± 0%   -83.33%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/2048-16         7.00 ± 0%      1.00 ± 0%   -85.71%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/4096-16         8.00 ± 0%      1.00 ± 0%   -87.50%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/8192-16         9.00 ± 0%      1.00 ± 0%   -88.89%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int64/65536-16        13.0 ± 0%       1.0 ± 0%   -92.31%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/6-16            0.00           0.00           ~     (all equal)

MapAssignPreAllocate/Int32/12-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int32/18-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int32/24-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/30-16           1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Int32/64-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/128-16          3.00 ± 0%      1.00 ± 0%   -66.67%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/256-16          4.00 ± 0%      1.00 ± 0%   -75.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/512-16          5.00 ± 0%      1.00 ± 0%   -80.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/1024-16         6.00 ± 0%      1.00 ± 0%   -83.33%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/2048-16         7.00 ± 0%      1.00 ± 0%   -85.71%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/4096-16         8.00 ± 0%      1.00 ± 0%   -87.50%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/8192-16         9.00 ± 0%      1.00 ± 0%   -88.89%  (p=0.000 n=10+10)

MapAssignPreAllocate/Int32/65536-16        13.0 ± 0%       1.0 ± 0%   -92.31%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/6-16              0.00           0.00           ~     (all equal)

MapAssignPreAllocate/Str/12-16             1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Str/18-16             1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Str/24-16             1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Str/30-16             1.00 ± 0%      1.00 ± 0%      ~     (all equal)

MapAssignPreAllocate/Str/64-16             2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/128-16            2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/256-16            2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/512-16            2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/1024-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/2048-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/4096-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/8192-16           2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignPreAllocate/Str/65536-16          2.00 ± 0%      1.00 ± 0%   -50.00%  (p=0.000 n=10+10)

MapAssignReuse/Pointer/6-16                6.00 ± 0%      6.00 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/12-16               12.0 ± 0%      12.0 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/18-16               18.0 ± 0%      18.0 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/24-16               24.0 ± 0%      24.0 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/30-16               30.0 ± 0%      30.0 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/64-16               64.0 ± 0%      64.0 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/128-16               128 ± 0%       128 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/256-16               256 ± 0%       256 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/512-16               512 ± 0%       512 ± 0%      ~     (all equal)

MapAssignReuse/Pointer/1024-16            1.02k ± 0%     1.02k ± 0%      ~     (all equal)

MapAssignReuse/Pointer/2048-16            2.05k ± 0%     2.05k ± 0%      ~     (all equal)

MapAssignReuse/Pointer/4096-16            4.10k ± 0%     4.10k ± 0%      ~     (all equal)

MapAssignReuse/Pointer/8192-16            8.19k ± 0%     8.19k ± 0%      ~     (all equal)

MapAssignReuse/Pointer/65536-16           65.5k ± 0%     65.5k ± 0%      ~     (all equal)

MapAssignReuse/Int64/6-16                  0.00           0.00           ~     (all equal)

MapAssignReuse/Int64/12-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int64/18-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int64/24-16                 1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/30-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int64/64-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int64/128-16                1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/256-16                2.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/512-16                3.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/1024-16               4.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/2048-16               5.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/4096-16               6.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/8192-16               7.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int64/65536-16              11.0 ± 0%       0.0       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/6-16                  0.00           0.00           ~     (all equal)

MapAssignReuse/Int32/12-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int32/18-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int32/24-16                 1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/30-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int32/64-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Int32/128-16                1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/256-16                2.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/512-16                3.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/1024-16               4.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/2048-16               5.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/4096-16               6.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/8192-16               7.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Int32/65536-16              11.0 ± 0%       0.0       -100.00%  (p=0.000 n=10+10)

MapAssignReuse/Str/6-16                    0.00           0.00           ~     (all equal)

MapAssignReuse/Str/12-16                   0.00           0.00           ~     (all equal)

MapAssignReuse/Str/18-16                   0.00           0.00           ~     (all equal)

MapAssignReuse/Str/24-16                   0.00           0.00           ~     (all equal)

MapAssignReuse/Str/30-16                   0.00           0.00           ~     (all equal)

MapAssignReuse/Str/64-16                   0.00           0.00           ~     (all equal)

MapAssignReuse/Str/128-16                  0.00           0.00           ~     (all equal)

MapAssignReuse/Str/256-16                  0.00           0.00           ~     (all equal)

MapAssignReuse/Str/512-16                  0.00           0.00           ~     (all equal)

MapAssignReuse/Str/1024-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Str/2048-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Str/4096-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Str/8192-16                 0.00           0.00           ~     (all equal)

MapAssignReuse/Str/65536-16                0.00           0.00           ~     (all equal)

Benchmark-2

The benchmarks from runtime.

INFO

name                              old time/op    new time/op      delta
MegMap-16                           9.01ns ± 1%      8.83ns ± 1%       -2.00%  (p=0.000 n=8+8)
MegOneMap-16                        4.59ns ± 1%      9.21ns ± 2%     +100.52%  (p=0.000 n=9+10)
MegEqMap-16                         20.4µs ± 2%      20.1µs ± 2%       -1.49%  (p=0.011 n=9+9)
MegEmptyMap-16                      2.18ns ± 3%      2.06ns ± 1%       -5.42%  (p=0.000 n=10+10)
SmallStrMap-16                      8.27ns ± 1%      7.17ns ± 4%      -13.31%  (p=0.000 n=8+10)
MapStringKeysEight_16-16            6.89ns ± 3%      7.79ns ± 1%      +13.09%  (p=0.000 n=9+8)
MapStringKeysEight_32-16            7.75ns ± 5%      7.97ns ± 0%       +2.83%  (p=0.000 n=10+7)
MapStringKeysEight_64-16            7.66ns ± 3%      8.76ns ± 1%      +14.43%  (p=0.000 n=10+7)
MapStringKeysEight_1M-16            7.72ns ± 3%  16483.00ns ± 1%  +213363.36%  (p=0.000 n=10+8)
IntMap-16                           5.21ns ± 1%      6.42ns ±16%      +23.30%  (p=0.000 n=8+10)
MapFirst/1-16                       2.68ns ± 1%      2.45ns ± 1%       -8.78%  (p=0.000 n=10+9)
MapFirst/2-16                       2.68ns ± 1%      2.43ns ± 1%       -9.34%  (p=0.000 n=9+9)
MapFirst/3-16                       2.66ns ± 2%      2.44ns ± 1%       -7.98%  (p=0.000 n=10+9)
MapFirst/4-16                       2.68ns ± 1%      2.44ns ± 0%       -8.67%  (p=0.000 n=8+9)
MapFirst/5-16                       2.69ns ± 1%      2.45ns ± 0%       -8.73%  (p=0.000 n=8+8)
MapFirst/6-16                       2.68ns ± 0%      2.44ns ± 1%       -8.78%  (p=0.000 n=8+9)
MapFirst/7-16                       2.69ns ± 1%      2.45ns ± 1%       -9.10%  (p=0.000 n=10+9)
MapFirst/8-16                       2.67ns ± 1%      4.79ns ± 1%      +79.47%  (p=0.000 n=10+9)
MapFirst/9-16                       4.66ns ± 1%      4.75ns ± 2%       +1.98%  (p=0.000 n=10+9)
MapFirst/10-16                      4.68ns ± 2%      4.73ns ± 1%       +1.19%  (p=0.016 n=9+10)
MapFirst/11-16                      4.69ns ± 2%      4.78ns ± 1%       +1.93%  (p=0.000 n=9+8)
MapFirst/12-16                      4.64ns ± 2%      4.75ns ± 2%       +2.47%  (p=0.005 n=10+10)
MapFirst/13-16                      4.69ns ± 1%      4.78ns ± 1%       +1.86%  (p=0.000 n=8+9)
MapFirst/14-16                      4.68ns ± 2%      4.79ns ± 1%       +2.34%  (p=0.000 n=10+8)
MapFirst/15-16                      4.67ns ± 1%      6.90ns ± 2%      +47.88%  (p=0.000 n=8+10)
MapFirst/16-16                      4.65ns ± 2%      6.95ns ± 1%      +49.60%  (p=0.000 n=10+9)
MapMid/1-16                         2.68ns ± 1%      2.62ns ± 1%       -2.15%  (p=0.000 n=10+9)
MapMid/2-16                         3.23ns ± 1%      2.95ns ± 1%       -8.59%  (p=0.000 n=10+9)
MapMid/3-16                         3.21ns ± 1%      2.94ns ± 0%       -8.33%  (p=0.000 n=10+7)
MapMid/4-16                         3.64ns ± 2%      3.46ns ± 1%       -4.84%  (p=0.000 n=10+8)
MapMid/5-16                         3.67ns ± 1%      3.47ns ± 1%       -5.46%  (p=0.000 n=10+8)
MapMid/6-16                         4.15ns ± 2%      3.93ns ± 1%       -5.25%  (p=0.000 n=10+9)
MapMid/7-16                         4.19ns ± 1%      3.91ns ± 1%       -6.55%  (p=0.000 n=10+10)
MapMid/8-16                         4.84ns ± 2%      5.76ns ±11%      +19.02%  (p=0.000 n=10+10)
MapMid/9-16                         5.66ns ±10%      5.83ns ± 9%         ~     (p=0.393 n=10+10)
MapMid/10-16                        5.81ns ± 5%      6.20ns ± 4%       +6.67%  (p=0.001 n=8+7)
MapMid/11-16                        5.80ns ± 4%      6.17ns ±11%         ~     (p=0.278 n=9+10)
MapMid/12-16                        5.87ns ±10%      6.26ns ± 2%       +6.48%  (p=0.008 n=9+7)
MapMid/13-16                        6.15ns ±13%      5.92ns ± 8%         ~     (p=0.315 n=10+8)
MapMid/14-16                        5.29ns ± 8%      6.18ns ±14%      +16.89%  (p=0.001 n=9+10)
MapMid/15-16                        5.44ns ±12%      7.04ns ± 2%      +29.37%  (p=0.000 n=10+10)
MapMid/16-16                        5.91ns ±11%      7.18ns ± 3%      +21.44%  (p=0.000 n=10+9)
MapLast/1-16                        2.69ns ± 1%      2.64ns ± 2%       -2.00%  (p=0.000 n=8+10)
MapLast/2-16                        3.22ns ± 2%      2.93ns ± 1%       -9.05%  (p=0.000 n=9+10)
MapLast/3-16                        3.66ns ± 2%      3.47ns ± 1%       -5.17%  (p=0.000 n=10+8)
MapLast/4-16                        4.20ns ± 1%      3.88ns ± 2%       -7.54%  (p=0.000 n=8+9)
MapLast/5-16                        4.85ns ± 2%      4.39ns ± 2%       -9.53%  (p=0.000 n=9+9)
MapLast/6-16                        5.33ns ± 1%      5.10ns ± 8%       -4.27%  (p=0.017 n=9+10)
MapLast/7-16                        5.79ns ± 1%      5.33ns ± 2%       -7.93%  (p=0.000 n=9+8)
MapLast/8-16                        6.28ns ± 1%      6.55ns ±17%         ~     (p=0.704 n=9+10)
MapLast/9-16                        6.90ns ±18%      6.87ns ±12%         ~     (p=1.000 n=9+9)
MapLast/10-16                       6.83ns ±15%      7.32ns ± 7%       +7.10%  (p=0.010 n=9+8)
MapLast/11-16                       7.84ns ± 3%      7.46ns ± 5%       -4.78%  (p=0.006 n=7+8)
MapLast/12-16                       7.58ns ± 9%      7.58ns ±12%         ~     (p=0.743 n=8+9)
MapLast/13-16                       9.15ns ±25%     14.06ns ± 2%      +53.70%  (p=0.000 n=10+8)
MapLast/14-16                       6.31ns ±15%      7.95ns ± 8%      +25.94%  (p=0.000 n=9+8)
MapLast/15-16                       6.20ns ±16%      7.11ns ± 2%      +14.59%  (p=0.004 n=10+10)
MapLast/16-16                       6.78ns ±19%      7.19ns ± 1%         ~     (p=0.139 n=9+8)
MapCycle-16                         11.5ns ± 2%      15.8ns ± 2%      +36.83%  (p=0.000 n=10+10)
RepeatedLookupStrMapKey32-16        9.37ns ± 2%      7.81ns ± 1%      -16.67%  (p=0.000 n=9+9)
RepeatedLookupStrMapKey1M-16        16.6µs ± 1%      16.6µs ± 2%         ~     (p=0.604 n=10+9)
MakeMap/[Byte]Byte-16                120ns ± 1%       116ns ± 1%       -3.61%  (p=0.000 n=10+10)
MakeMap/[Int]Int-16                  164ns ± 1%       160ns ± 0%       -2.36%  (p=0.000 n=10+9)
NewEmptyMap-16                      4.32ns ± 1%      4.55ns ± 3%       +5.26%  (p=0.000 n=10+10)
NewSmallMap-16                      19.4ns ± 2%      24.1ns ± 1%      +24.31%  (p=0.000 n=10+10)
MapIter-16                          73.7ns ± 2%      82.3ns ± 3%      +11.60%  (p=0.000 n=10+10)
MapIterEmpty-16                     3.65ns ± 1%      4.11ns ± 2%      +12.80%  (p=0.000 n=9+9)
SameLengthMap-16                    3.14ns ± 2%      3.38ns ± 2%       +7.50%  (p=0.000 n=9+10)
BigKeyMap-16                        10.0ns ± 4%      11.9ns ± 1%      +18.84%  (p=0.000 n=10+10)
BigValMap-16                        10.0ns ± 3%      11.9ns ± 2%      +18.74%  (p=0.000 n=10+10)
SmallKeyMap-16                      8.51ns ± 1%      9.91ns ± 1%      +16.44%  (p=0.000 n=10+9)
MapPopulate/1-16                    10.4ns ± 1%      14.4ns ± 2%      +38.28%  (p=0.000 n=9+9)
MapPopulate/10-16                    608ns ± 1%       495ns ± 1%      -18.58%  (p=0.000 n=10+10)
MapPopulate/100-16                  9.32µs ± 1%      6.28µs ± 1%      -32.59%  (p=0.000 n=9+10)
MapPopulate/1000-16                  111µs ± 0%        86µs ± 0%      -22.28%  (p=0.000 n=10+10)
MapPopulate/10000-16                 965µs ± 0%       745µs ± 1%      -22.78%  (p=0.000 n=10+10)
MapPopulate/100000-16               10.4ms ± 1%       7.4ms ± 0%      -28.46%  (p=0.000 n=10+10)
ComplexAlgMap-16                    20.6ns ± 1%      22.9ns ± 1%      +10.86%  (p=0.000 n=9+10)
GoMapClear/Reflexive/1-16           19.3ns ± 1%      17.9ns ± 1%       -7.39%  (p=0.000 n=10+10)
GoMapClear/Reflexive/10-16          21.2ns ± 1%      18.9ns ± 2%      -10.91%  (p=0.000 n=10+9)
GoMapClear/Reflexive/100-16         37.3ns ± 1%      40.2ns ± 1%       +7.90%  (p=0.000 n=9+9)
GoMapClear/Reflexive/1000-16         345ns ± 2%       433ns ± 1%      +25.73%  (p=0.000 n=10+10)
GoMapClear/Reflexive/10000-16       2.62µs ± 1%      3.94µs ± 1%      +50.33%  (p=0.000 n=10+10)
GoMapClear/NonReflexive/1-16        80.2ns ± 2%      62.8ns ± 2%      -21.61%  (p=0.000 n=9+9)
GoMapClear/NonReflexive/10-16       92.2ns ± 2%      72.5ns ± 2%      -21.42%  (p=0.000 n=10+10)
GoMapClear/NonReflexive/100-16       216ns ± 2%       101ns ± 1%      -53.49%  (p=0.000 n=9+8)
GoMapClear/NonReflexive/1000-16     2.13µs ± 1%      0.34µs ± 2%      -84.02%  (p=0.000 n=10+9)
GoMapClear/NonReflexive/10000-16    16.4µs ± 1%       2.1µs ± 1%      -86.96%  (p=0.000 n=10+8)
MapStringConversion/32/simple-16    7.79ns ± 1%     12.22ns ± 1%      +56.92%  (p=0.000 n=9+9)
MapStringConversion/32/struct-16    7.72ns ± 1%     12.32ns ± 2%      +59.70%  (p=0.000 n=9+10)
MapStringConversion/32/array-16     7.72ns ± 3%     12.00ns ± 3%      +55.34%  (p=0.000 n=10+9)
MapStringConversion/64/simple-16    7.47ns ± 1%     11.77ns ± 3%      +57.65%  (p=0.000 n=9+10)
MapStringConversion/64/struct-16    7.49ns ± 1%     11.94ns ± 2%      +59.38%  (p=0.000 n=9+10)
MapStringConversion/64/array-16     7.50ns ± 1%     11.92ns ± 2%      +58.89%  (p=0.000 n=9+10)
MapInterfaceString-16               11.2ns ± 5%      13.7ns ±61%         ~     (p=1.000 n=8+10)
MapInterfacePtr-16                  10.8ns ±29%      11.3ns ±52%         ~     (p=0.684 n=10+10)
NewEmptyMapHintLessThan8-16         6.54ns ± 1%      6.04ns ± 1%       -7.56%  (p=0.000 n=9+9)
NewEmptyMapHintGreaterThan8-16       271ns ± 2%       268ns ± 1%         ~     (p=0.062 n=10+9)
MapPop100-16                        10.8µs ± 6%       7.2µs ±14%      -33.41%  (p=0.000 n=10+10)
MapPop1000-16                        170µs ± 1%       101µs ± 1%      -40.54%  (p=0.000 n=9+9)
MapPop10000-16                      3.35ms ± 3%      1.74ms ± 4%      -48.15%  (p=0.000 n=10+9)
MapAssign/Int32/256-16              10.1ns ± 4%       8.9ns ± 1%      -12.13%  (p=0.000 n=10+9)
MapAssign/Int32/65536-16            22.0ns ± 1%      12.9ns ± 1%      -41.11%  (p=0.000 n=10+8)
MapAssign/Int64/256-16              10.7ns ± 2%       8.6ns ± 2%      -19.79%  (p=0.000 n=8+9)
MapAssign/Int64/65536-16            23.2ns ± 2%      13.1ns ± 2%      -43.39%  (p=0.000 n=10+9)
MapAssign/Str/256-16                16.6ns ± 4%      13.1ns ± 3%      -21.18%  (p=0.000 n=10+9)
MapAssign/Str/65536-16              27.5ns ± 3%      20.5ns ± 3%      -25.66%  (p=0.000 n=10+9)
MapOperatorAssign/Int32/256-16      9.89ns ± 2%      8.69ns ± 3%      -12.15%  (p=0.000 n=9+9)
MapOperatorAssign/Int32/65536-16    21.9ns ± 1%      12.8ns ± 3%      -41.52%  (p=0.000 n=10+10)
MapOperatorAssign/Int64/256-16      10.9ns ± 3%       8.6ns ± 1%      -21.20%  (p=0.000 n=9+8)
MapOperatorAssign/Int64/65536-16    22.4ns ± 0%      13.2ns ± 2%      -41.15%  (p=0.000 n=7+9)
MapOperatorAssign/Str/256-16        1.43µs ± 2%      1.40µs ± 1%       -1.93%  (p=0.000 n=10+10)
MapOperatorAssign/Str/65536-16       234ns ± 3%       237ns ± 4%         ~     (p=0.138 n=10+10)
MapAppendAssign/Int32/256-16        21.0ns ± 2%      20.1ns ± 4%       -4.43%  (p=0.000 n=8+10)
MapAppendAssign/Int32/65536-16      38.5ns ± 2%      33.9ns ± 2%      -12.00%  (p=0.000 n=10+10)
MapAppendAssign/Int64/256-16        21.4ns ± 3%      20.4ns ± 6%       -4.26%  (p=0.008 n=9+10)
MapAppendAssign/Int64/65536-16      39.8ns ± 2%      34.9ns ± 1%      -12.40%  (p=0.000 n=10+8)
MapAppendAssign/Str/256-16          52.8ns ± 7%      52.1ns ± 5%         ~     (p=0.739 n=10+10)
MapAppendAssign/Str/65536-16        66.5ns ± 2%      67.7ns ± 1%       +1.94%  (p=0.004 n=9+9)
MapDelete/Int32/100-16              27.7ns ± 2%      17.8ns ± 2%      -35.77%  (p=0.000 n=10+10)
MapDelete/Int32/1000-16             22.6ns ± 2%      12.8ns ± 1%      -43.31%  (p=0.000 n=9+9)
MapDelete/Int32/10000-16            25.0ns ± 2%      15.2ns ± 1%      -39.33%  (p=0.000 n=7+10)
MapDelete/Int64/100-16              29.8ns ± 3%      17.6ns ± 2%      -40.98%  (p=0.000 n=10+9)
MapDelete/Int64/1000-16             23.3ns ± 2%      13.1ns ± 1%      -43.77%  (p=0.000 n=10+8)
MapDelete/Int64/10000-16            25.6ns ± 2%      16.1ns ± 1%      -37.13%  (p=0.000 n=9+9)
MapDelete/Str/100-16                38.4ns ± 4%      24.8ns ± 2%      -35.29%  (p=0.000 n=10+10)
MapDelete/Str/1000-16               30.8ns ± 2%      20.7ns ± 1%      -32.72%  (p=0.000 n=10+10)
MapDelete/Str/10000-16              35.8ns ± 2%      24.4ns ± 2%      -31.95%  (p=0.000 n=10+10)
MapDelete/Pointer/100-16            30.7ns ± 2%      21.0ns ± 1%      -31.69%  (p=0.000 n=10+10)
MapDelete/Pointer/1000-16           24.5ns ± 2%      16.6ns ± 1%      -32.37%  (p=0.000 n=10+10)
MapDelete/Pointer/10000-16          27.1ns ± 3%      19.8ns ± 2%      -26.87%  (p=0.000 n=10+10)
name                              old alloc/op   new alloc/op     delta

NewEmptyMap-16                       0.00B            0.00B              ~     (all equal)

NewSmallMap-16                       0.00B            0.00B              ~     (all equal)

MapPopulate/1-16                     0.00B            0.00B              ~     (all equal)

MapPopulate/10-16                     179B ± 0%        176B ± 0%       -1.68%  (p=0.000 n=10+10)

MapPopulate/100-16                  3.35kB ± 0%      2.64kB ± 0%      -21.16%  (p=0.000 n=10+10)

MapPopulate/1000-16                 53.3kB ± 0%      48.7kB ± 0%       -8.62%  (p=0.000 n=9+10)

MapPopulate/10000-16                 428kB ± 0%       368kB ± 0%      -13.87%  (p=0.000 n=9+10)

MapPopulate/100000-16               3.62MB ± 0%      2.89MB ± 0%      -20.08%  (p=0.000 n=8+10)

MapStringConversion/32/simple-16     0.00B            0.00B              ~     (all equal)

MapStringConversion/32/struct-16     0.00B            0.00B              ~     (all equal)

MapStringConversion/32/array-16      0.00B            0.00B              ~     (all equal)

MapStringConversion/64/simple-16     0.00B            0.00B              ~     (all equal)

MapStringConversion/64/struct-16     0.00B            0.00B              ~     (all equal)

MapStringConversion/64/array-16      0.00B            0.00B              ~     (all equal)

NewEmptyMapHintLessThan8-16          0.00B            0.00B              ~     (all equal)

NewEmptyMapHintGreaterThan8-16      1.15kB ± 0%      1.15kB ± 0%         ~     (all equal)

MapAppendAssign/Int32/256-16         45.5B ± 3%       43.5B ±13%         ~     (p=0.291 n=8+10)

MapAppendAssign/Int32/65536-16       18.3B ± 4%       16.7B ± 4%       -8.74%  (p=0.000 n=10+10)

MapAppendAssign/Int64/256-16         42.8B ±12%       44.5B ±15%         ~     (p=0.466 n=10+10)

MapAppendAssign/Int64/65536-16       18.6B ± 8%       17.0B ± 0%       -8.60%  (p=0.000 n=10+9)

MapAppendAssign/Str/256-16           88.1B ± 4%       87.9B ± 4%         ~     (p=1.000 n=10+10)

MapAppendAssign/Str/65536-16         35.0B ± 0%       33.4B ± 4%       -4.57%  (p=0.000 n=6+10)
name                              old allocs/op  new allocs/op    delta

NewEmptyMap-16                        0.00             0.00              ~     (all equal)

NewSmallMap-16                        0.00             0.00              ~     (all equal)

MapPopulate/1-16                      0.00             0.00              ~     (all equal)

MapPopulate/10-16                     1.00 ± 0%        1.00 ± 0%         ~     (all equal)

MapPopulate/100-16                    17.0 ± 0%         4.0 ± 0%      -76.47%  (p=0.000 n=10+10)

MapPopulate/1000-16                   72.7 ± 1%         8.0 ± 0%      -89.00%  (p=0.000 n=10+10)

MapPopulate/10000-16                   319 ± 0%          11 ± 0%      -96.55%  (p=0.002 n=8+10)

MapPopulate/100000-16                4.00k ± 0%       0.01k ± 0%      -99.65%  (p=0.000 n=10+10)

MapStringConversion/32/simple-16      0.00             0.00              ~     (all equal)

MapStringConversion/32/struct-16      0.00             0.00              ~     (all equal)

MapStringConversion/32/array-16       0.00             0.00              ~     (all equal)

MapStringConversion/64/simple-16      0.00             0.00              ~     (all equal)

MapStringConversion/64/struct-16      0.00             0.00              ~     (all equal)

MapStringConversion/64/array-16       0.00             0.00              ~     (all equal)

NewEmptyMapHintLessThan8-16           0.00             0.00              ~     (all equal)

NewEmptyMapHintGreaterThan8-16        1.00 ± 0%        1.00 ± 0%         ~     (all equal)

MapAppendAssign/Int32/256-16          0.00             0.00              ~     (all equal)

MapAppendAssign/Int32/65536-16        0.00             0.00              ~     (all equal)

MapAppendAssign/Int64/256-16          0.00             0.00              ~     (all equal)

MapAppendAssign/Int64/65536-16        0.00             0.00              ~     (all equal)

MapAppendAssign/Str/256-16            0.00             0.00              ~     (all equal)

MapAppendAssign/Str/65536-16          0.00             0.00              ~     (all equal)

gopherbot · 2022-08-30T06:51:03Z

Change https://go.dev/cl/426614 mentions this issue: runtime: use SwissTable

seankhliao · 2022-08-30T07:37:39Z

cc @golang/runtime

prattmic · 2022-08-30T14:36:01Z

cc @randall77

Overall this sounds great. The main concern I have up front here is that growing happens all at once rather than incrementally. Could you explain more why that is and if it is possible to do so incrementally?

aaronbee · 2022-08-30T16:45:45Z

Do iterators get invalidated when the map is modified? This is common for open-addressing hash tables. An important feature of the current map is that you can modify the map while iterating and the iterator still works.

aaronbee · 2022-08-30T18:47:42Z

Do iterators get invalidated when the map is modified? This is common for open-addressing hash tables. An important feature of the current map is that you can modify the map while iterating and the iterator still works.

I checked the implementation and it does look like iterators stay valid when the map is modified.

randall77 · 2022-08-30T19:27:05Z

The semantics of Go iterators basically mean you can't move items in the map data structure once you've placed them. So, for instance, you can't move a valid item to fill in a deleted one - you need to always use a tombstone. But other than that, iterators don't add much of a restriction to the implementation.

aclements · 2022-08-31T15:56:35Z

This is really exciting. Thanks for doing all of this work.

The benchmarks from runtime.

There are many slowdowns in these benchmarks, some quite significant. Do you understand the source of these slowdowns? Is it something that can be fixed?

The previous implementation uses incremental rehash

This is an important property to maintain because it can significantly impact the tail latency of services. We've done a lot of work throughout the Go runtime over the years to avoid unpredictable performance spikes and it would be a shame to regress here.

I'm not personally familiar with the details of SwissTable. Is incremental rehashing something that can be done and just hasn't been implemented yet, or is it fundamentally difficult?

If it's fundamentally difficult to do directly in SwissTable, I've been kickaround the the idea of adopting aspects of extendible hashing for a while, which could be a general solution to incremental resizing. I should probably just file an "idea" issue about this, but I'll try to lay it out here.

The idea is that, once a hash table grows beyond some size threshold based on bounding how long it takes to resize a map, you switch to a two-level scheme. I'm guessing that threshold would be around 4MiB, but that would have to be determined experimentally. In the two-level scheme, the top level is an index array keyed by the top k bits of the hash, which then points to map shards, which are individual SwissTables. The Wikipedia article I linked has some good diagrams for visualizing this. Each shard s contains only the items whose top j_s <= k bits are all identical, and multiple index entries will point to the same shard if that shard's j_s < k. When an individual shard overflows the threshold size, you split just that shard into two new shards s1 and s2 with j_s1 = j_s2 = j_s+1, and update the index. If j_s1 > k, then you also double the index array in order to increase k by 1.

This would enable incremental growth and bound the resize cost paid by any single map operation. Iterators can continue to work while a map is resized by holding on to the pre-resize shard they are currently iterating (let the GC collect this once all iterators have moved past it). It would also reduce overall memory footprint because the total memory size of a map doesn't have to be a power of two (even if each individual shard is). It would result in less memory fragmentation caused by large maps because it limits the size of each individual allocation. And it would address problems with our current map resizing algorithm where, if a map is grown to a size that puts it into resizing mode, but then modifications stop and the application switches to only reading from the map, accesses are relatively slow and the map continues to consume additional memory (#51410).

mknyszek · 2022-08-31T19:26:53Z

I placed this in the Unplanned milestone for now since it seems like there's still a bunch to discuss before landing it (it's non-committal). I assigned it to @zhangyunhao116 since you're driving the effort at the moment.

zhangyunhao116 · 2022-09-02T09:28:47Z

Thanks for your advice! @aclements

We hope to get more feedback from the community and the Go team.

Do you understand the source of these slowdowns? Is it something that can be fixed?

Many reasons affect the performance degradation of these benchmarks(for basic version):

Most benchmarks from the Go runtime are running on a small map(contains very few elements). The original implementation has a feature called emptyRest that would break the current loop after encountering it. SwissTable does not have this feature. In this case, the previous implementation is better(the situation is usually reversed with the larger map. ). This affects the performance of BigKeyMap and MapStringConversion. In most cases, the larger the number of map elements, the better performance of the SwissTable.
The Go runtime's mapaccess benchmarks only test the hit case ( MapFirst MapMid MapLast). SwissTable tends to perform better in the case of Miss.
The growth of SwissTable is done at once, which means in some cases, the performance will be significantly degraded. For MapStringKeysEight, because it inserts a total of 8 elements if using SwissTable, now the map is composed of two buckets; this invalidates our optimization when the number of buckets is 1 in map_faststr.go. We can also observe a similar case in MapFirst, where there is a significant performance change when the number of buckets changes. Some of these problems may be solved by adding special optimizations, such as growing the capacity after the first bucket is full.
We removed some optimizations to avoid a CL containing many changes, such as
- Store bucketmask instead of B. So that we don't need to calculate the bucketmask every time, it can save about 0.3ns each time, about 10% improvement for some benchmarks that consume less time.
- Remove the overflow pointer in the bucket. It will help the overall performance and GC.

Is incremental rehashing something that can be done and just hasn't been implemented yet, or is it fundamentally difficult?

I think it is fundamentally difficult since a single empty slot in SwissTable can break the search process(https://faultlore.com/blah/hashbrown-tldr/#deletion).

If it's fundamentally difficult to do directly in SwissTable, I've been kickaround the the idea of adopting aspects of extendible hashing for a while, which could be a general solution to incremental resizing. I should probably just file an "idea" issue about this, but I'll try to lay it out here.

That sounds like a great idea! I'll think about this idea carefully later.
We plan to internally deploy this change to some latency-sensitive services to observe the impact. If there is a significant impact on the latency, we will also consider using different ways to solve it if possible.

beoran · 2022-09-05T13:08:24Z

I like to use small maps for many purposes, so it worries me a bit that SwissTable seems to perform worse for them. Maybe a special case is needed for small maps?

zhangyunhao116 · 2022-09-06T10:24:01Z

Maybe a special case is needed for small maps?

Yes, but it may have to consider carefully(optimizing the small map may cause performance impact in other situations).

SwissTable does not always cause worse performance for small maps, and we can see the cases in the benchmark(e.g., in most key miss scenarios, the performance improves instead). Could you please tell me the cases where the small maps are often used?

Some of the slowdowns in the benchmarks can be fixed. PatchSet 10 should fix the slowdown of Pop in the runtime benchmark. I will update the benchmark result later :)

beoran · 2022-09-06T10:27:29Z

Well I use small maps often in stead of case statements, or for mapping a few input file names to processors, or for lookups such as os.Substitute can do. I am looking forward to the improved results.

aclements · 2022-09-07T16:38:42Z

Thanks for the detailed breakdown of the performance losses! My take is that there are two things that need to happen on that front:

Work on improving the small map case. I'm okay with some slowdown here, but I also think these are common enough that it's worth some effort to improve.
Optionally, improve the runtime's map benchmarks. It seems like we just don't have great benchmarks. :) We should continue to cover the small map case, though. If I'm interpreting the names of the benchmarks from your suite correctly, it looks like you are covering small maps.

You mentioned that SwissTable is better for the "miss" case than the "hit" case. If I understand your layout correctly (I haven't looked closely), you're already packing the tophash and the data together, so you'd expect one cache miss for a hit. Is that right? Does the SIMD version of SwissTable level the field between the hit and miss cases at all?

aclements · 2022-09-07T16:52:34Z

Stepping back, I think there are three high-level potential concerns to address with this:

Incremental resizing. We've already been discussing this above. :)

DoS prevention. Currently, Go maps have fairly strong denial-of-service properties. The main concern is if an attacker can control the placement of items to induce collisions, leading to n^2 behavior. Having a good, per-map seed that is factored into the hash computation (not just combined at the end) goes a long way toward preventing this. Beyond this, the concern becomes leaking too much information about long-lived maps such that an attacker could reconstruct the seed. Having non-deterministic iteration order helps a lot here. A third problem is that copying elements one-by-one from one map into another, newly allocated map can easily go n^2, but having a per-map seed also mitigates that. I think all of these mechanisms are still in place in your implementation, but wanted to confirm that.

SIMD, specifically how to actually use SIMD instructions in the map implementation. The most straightforward approach is to write the SIMD bits in assembly, but that has significant maintainability problems and may even perform worse because of the cost of transitioning to and from assembly. So, that suggests adding compiler intrinsics. General SIMD intrinsics are a wide-open area right now and I don't think we want to block the map implementation on solving that problem. :) A lot of proposals have floated around (admittedly, some of which have not been published). We could start trying them out just in the runtime. Or, if I understand correctly, SwissTable doesn't need very many or any particularly fancy SIMD operations, so maybe we just hack in some intrinsics (which we could use as a starting point for more general exploration).

CAFxX · 2022-09-08T05:51:41Z

The main concern is if an attacker can control the placement of items to induce collisions, leading to n^2 behavior. Having a good, per-map seed that is factored into the hash computation (not just combined at the end) goes a long way toward preventing this. Beyond this, the concern becomes leaking too much information about long-lived maps such that an attacker could reconstruct the seed. Having non-deterministic iteration order helps a lot here. A third problem is that copying elements one-by-one from one map into another, newly allocated map can easily go n^2, but having a per-map seed also mitigates that. I think all of these mechanisms are still in place in your implementation, but wanted to confirm that.

Another option that would help alleviate most n^2 concerns is having a per-map seed that changes when the map grows/shrinks.

josharian · 2022-09-08T08:49:16Z

a per-map seed that changes when the map grows/shrinks.

This is challenging with incremental map growth. FWIW, I believe we do opportunistically reset the seed when the length hits zero.

zhangyunhao116 · 2022-09-13T10:01:14Z

Thanks for all of the feedback :)

Work on improving the small map case.

PatchSet-11 adding the optimization of bucketmask into it, the benchmark has been improved for almost all cases(updated the benchmark result).

There are still two optimizations that can be added

Using a two-level scheme for map_fast32 and map_fast64. The idea is that we can iterate the bucket instead of using matchTopHash if iterating the bucket can have better performance. Now the threshold is 2, meaning that if 0 <= buckets <= 2, we iterate the bucket(bucket == 0 is a special case, we don't need to calculate the hash). For buckets > 2, we use the matchTopHash scheme. We can change the threshold based on the experiment, and uint32 and uint64 can have different thresholds.
Remove the overflow pointer in the bucket. ~~I have encountered some problems due to memory overlap, which is still a work in progress.~~ It has been added in PatchSet 12.

Improving the runtime's map benchmarks.

Indeed. We can add some new benchmarks to it. I feel like adding the new one into https://github.com/zhangyunhao116/gomapbench first and then migrating some of it into the runtime is a good idea.

DoS prevention.

Yes! All of these mechanisms are still in the current implementation, including the non-deterministic iteration and resetting the map's seed when the length hits zero.

SIMD

We planned to write the SIMD directly in assembly, but the experiments outside the runtime show that their performance is almost the same. I wonder if we can use ABIInternal can make the assembly run faster?

I think SIMD intrinsics is a great idea! Agree that we can start trying SIMD intrinsics just in the runtime. After some basic optimizations are done, I will start to implement the SIMD version :) Most SIMD in the SwissTable is not very tricky except the prepareSameSizeGrow, and this function is rarely called(only used in sameSizeGrow).

zhangyunhao116 · 2022-09-14T09:58:29Z

Another challenge of SIMD is that its default bucket size is 16(the basic version is 8, which is the same as before), which means memory consumption may increase significantly in some cases.

aclements · 2022-09-19T21:07:54Z

Indeed. We can add some new benchmarks to it. I feel like adding the new one into https://github.com/zhangyunhao116/gomapbench first and then migrating some of it into the runtime is a good idea.

Sounds good. Possibly we should fold your package into bent, so they run as part of the performance dashboard.

Yes! All of these mechanisms are still in the current implementation, including the non-deterministic iteration and resetting the map's seed when the length hits zero.

Perfect!

We planned to write the SIMD directly in assembly, but the experiments outside the runtime show that their performance is almost the same. I wonder if we can use ABIInternal can make the assembly run faster?

Yeah, this doesn't surprise me if you're jumping to assembly just to run a few instructions. ABIInternal would certainly improve that, since it would probably allow the entire call to be registerized. I'm not sure exactly what operations you need, but if they're taking or returning vector values there's still going to be some overhead since ABIInternal doesn't know anything about passing vector registers.

I'm not sure how much effort it is to add a few one-off SIMD intrinsics. You just need SSE, right, not AVX? The operations themselves are probably not hard to add. The register allocator already knows about the XMM registers, but only as non-vector 64-bit floating-point. That mostly shouldn't matter unless it decides to spill one (thanks @cherrymui for pointing that out). If you need AVX, things may get a lot more complicated, or maybe not since the YMM registers are just aliased onto the XMM registers, so we would just call them X registers anyway.

Another challenge of SIMD is that its default bucket size is 16(the basic version is 8, which is the same as before), which means memory consumption may increase significantly in some cases.

It's hard to say how concerning this is. Sure, if an application has a huge number of small maps, perhaps with large key or value types (though they can't go over 128 bytes each), this could add up to a lot. But the relative overhead of this decreases as map size increases. I'll see if we can get some data on this.

Are you considering the trick described in this video, where you need to allocate 16 bytes of control (or a little more for unaligned groups) but the actual bucket array can be smaller? The net result of that might actually be that the tables would be smaller than current tables.

Use similar SIMD operations to the ones used in Abseil. We still using 8-slot groups (even though the XMM registers could handle 16-slot groups) to keep the implementation simpler (no changes to the memory layout of maps). Still, the implementations of matchH2 and matchEmpty are shorter than the portable version using standard arithmetic operations. They also return a packed bitset, which avoids the need to shift in bitset.first. That said, the packed bitset is a downside in cognitive complexity, as we have to think about two different possible representations. This doesn't leak out of the API, but we do need to intrinsify bitset to switch to a compatible implementation. The compiler's intrinsics don't support intrinsifying methods, so the implementations move to free functions. This makes operations between 0-3% faster on my machine. e.g., MapGetHit/impl=runtimeMap/t=Int64/len=6-12 12.34n ± 1% 11.42n ± 1% -7.46% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=12-12 15.14n ± 2% 14.88n ± 1% -1.72% (p=0.009 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=18-12 15.04n ± 6% 14.66n ± 2% -2.53% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=24-12 15.80n ± 1% 15.48n ± 3% ~ (p=0.444 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=30-12 15.55n ± 4% 14.77n ± 3% -5.02% (p=0.004 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=64-12 15.26n ± 1% 15.05n ± 1% ~ (p=0.055 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=128-12 15.34n ± 1% 15.02n ± 2% -2.09% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=256-12 15.42n ± 1% 15.15n ± 1% -1.75% (p=0.001 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=512-12 15.48n ± 1% 15.18n ± 1% -1.94% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=1024-12 17.38n ± 1% 17.05n ± 1% -1.90% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=2048-12 17.96n ± 0% 17.59n ± 1% -2.06% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=4096-12 18.36n ± 1% 18.18n ± 1% -0.98% (p=0.013 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=8192-12 18.75n ± 0% 18.31n ± 1% -2.35% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=65536-12 26.25n ± 0% 25.95n ± 1% -1.14% (p=0.000 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=262144-12 44.24n ± 1% 44.06n ± 1% ~ (p=0.181 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=1048576-12 85.02n ± 0% 85.35n ± 0% +0.39% (p=0.032 n=25) MapGetHit/impl=runtimeMap/t=Int64/len=4194304-12 98.87n ± 1% 98.85n ± 1% ~ (p=0.799 n=25) For #54766. Cq-Include-Trybots: luci.golang.try:gotip-linux-ppc64_power10,gotip-linux-amd64-goamd64v3 Change-Id: Ic1b852f02744404122cb3672900fd95f4625905e Reviewed-on: https://go-review.googlesource.com/c/go/+/626277 Reviewed-by: Keith Randall <khr@golang.org> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Auto-Submit: Michael Pratt <mpratt@google.com> Reviewed-by: Keith Randall <khr@google.com>

gopherbot · 2024-11-21T14:56:20Z

Change https://go.dev/cl/630279 mentions this issue: reflect: set swissmap GroupSize

This was missed in CL 627716. For #54766. Change-Id: Ib987efa8abe6e89367e2e1b71a33b64ac6b01b1f Reviewed-on: https://go-review.googlesource.com/c/go/+/630279 Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Keith Randall <khr@golang.org> Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

gopherbot · 2024-11-21T19:02:30Z

Change https://go.dev/cl/630676 mentions this issue: reflect: add test of maps with keys larger than key size

This finds the bug fixed in CL 630279. reflect mutates the SwissMapType of a map[unsafe.Pointer]unsafe.Pointer, which happened to already have the correct GroupSize for all of the maps used in the reflect tests. For #54766. Change-Id: If4428e1e799598e7512edceb3cefb2ad00cfa712 Reviewed-on: https://go-review.googlesource.com/c/go/+/630676 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@golang.org> Reviewed-by: Keith Randall <khr@google.com> Auto-Submit: Michael Pratt <mpratt@google.com>

- Run rekres and update linters. - Pull latest hashtriemap changes. - Support Go 1.24 [swissmaps](golang/go#54766). Signed-off-by: Dmitriy Matrenichev <dmitry.matrenichev@siderolabs.com>

gopherbot · 2024-12-12T22:40:07Z

Change https://go.dev/cl/635757 mentions this issue: internal/runtime/maps: switch directory to []table

gopherbot · 2024-12-12T22:40:08Z

Change https://go.dev/cl/635756 mentions this issue: internal/runtime/maps: layout all control words together

gopherbot · 2024-12-13T15:33:54Z

Change https://go.dev/cl/635995 mentions this issue: runtime: migrate missing map linkname allowlists

The swissmap implementation forgot to copy some of the linkname allowlists from the old implementation. Copy them from map_noswiss.go. Some were missing linkname entirely; others were linknamed but missing the hall of shame comment. For #54766. Change-Id: Icc715384123e73d868b4cb729ab639abcd6bbfd7 Reviewed-on: https://go-review.googlesource.com/c/go/+/635995 Reviewed-by: Cherry Mui <cherryyz@google.com> Auto-Submit: Michael Pratt <mpratt@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

rabbbit · 2024-12-13T21:21:37Z

Not sure if immediately superuseful but in #21035 (comment) I saw something that looked like a swissmap allocs regression. At least disabling it reduced the allocs :)

I was on

❯ gotip version
go version devel go1.24-4ce116a88 2024-12-10 14:51:25 -0500 darwin/arm64

prattmic · 2024-12-13T21:34:30Z

@rabbbit Thanks for the heads up, I will reply on that issue.

prattmic · 2024-12-13T21:55:30Z

I going to close this issue as it has huge scope (replace the entire implementation), which is done (and in the just-released Go 1.24 RC1!). Please try out the RC and open new issues with any problems you find.

These results are a bit old (missing a few optimizations), but give a good overview of changes:

goos: linux
goarch: amd64
pkg: github.com/cockroachdb/swiss
cpu: Intel(R) Xeon(R) W-2135 CPU @ 3.70GHz
                                                          │ /tmp/noswiss.lu.txt │          /tmp/swiss.lu.txt           │
                                                          │       sec/op        │    sec/op      vs base               │
MapIter/impl=runtimeMap/t=Int64/len=6-12                           70.72n ±  2%    62.18n ±  2%  -12.07% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=12-12                          119.2n ±  8%    127.1n ±  5%        ~ (p=0.065 n=6)
MapIter/impl=runtimeMap/t=Int64/len=18-12                          182.2n ±  4%    187.2n ±  7%        ~ (p=0.509 n=6)
MapIter/impl=runtimeMap/t=Int64/len=24-12                          227.5n ±  7%    216.6n ±  3%   -4.79% (p=0.009 n=6)
MapIter/impl=runtimeMap/t=Int64/len=30-12                          297.0n ±  3%    289.4n ±  8%        ~ (p=0.240 n=6)
MapIter/impl=runtimeMap/t=Int64/len=64-12                          642.0n ±  3%    603.8n ±  6%   -5.95% (p=0.004 n=6)
MapIter/impl=runtimeMap/t=Int64/len=128-12                         1.316µ ±  7%    1.223µ ±  9%   -7.07% (p=0.004 n=6)
MapIter/impl=runtimeMap/t=Int64/len=256-12                         2.779µ ±  2%    2.386µ ±  3%  -14.14% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=512-12                         5.709µ ±  3%    4.829µ ±  2%  -15.42% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=1024-12                       11.241µ ±  1%    9.852µ ±  2%  -12.35% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=2048-12                        22.32µ ±  1%    19.73µ ±  1%  -11.62% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=4096-12                        44.14µ ±  1%    39.38µ ±  3%  -10.79% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=8192-12                        87.98µ ±  1%    78.80µ ±  1%  -10.43% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=65536-12                       705.7µ ±  1%    633.8µ ±  2%  -10.20% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=262144-12                      2.831m ±  2%    2.650m ±  1%   -6.38% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=1048576-12                     11.61m ±  2%    11.04m ±  2%   -4.92% (p=0.002 n=6)
MapIter/impl=runtimeMap/t=Int64/len=4194304-12                     47.40m ±  2%    44.41m ±  2%   -6.30% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=6-12                    36.69n ±  1%    42.48n ±  3%  +15.78% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=12-12                   46.57n ±  1%    48.50n ±  3%   +4.14% (p=0.004 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=18-12                   59.35n ±  4%    56.58n ±  4%   -4.67% (p=0.004 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=24-12                   59.47n ±  3%    56.01n ±  1%   -5.83% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=30-12                   92.34n ±  1%    68.31n ±  1%  -26.03% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=64-12                  145.85n ±  3%    92.85n ±  2%  -36.34% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=128-12                  248.2n ±  2%    138.7n ±  1%  -44.11% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=256-12                  450.2n ±  1%    216.7n ±  1%  -51.87% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=512-12                  858.3n ±  2%    373.2n ±  1%  -56.52% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=1024-12                1679.5n ±  2%    729.1n ±  3%  -56.59% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=2048-12                 3.329µ ±  0%    1.497µ ±  1%  -55.04% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=4096-12                 6.610µ ±  2%    3.022µ ±  2%  -54.29% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=8192-12                13.205µ ±  0%    6.078µ ±  1%  -53.97% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=65536-12               113.16µ ±  5%    79.07µ ±  6%  -30.13% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=262144-12               682.1µ ±  3%    587.4µ ±  1%  -13.88% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=1048576-12              3.715m ±  1%    4.404m ±  1%  +18.56% (p=0.002 n=6)
MapIterLowLoad/impl=runtimeMap/t=Int64/len=4194304-12              15.20m ±  1%    18.22m ±  1%  +19.87% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=6-12                       694.1n ±  3%    606.2n ±  2%  -12.67% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=12-12                      1.539µ ±  3%    1.322µ ±  2%  -14.10% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=18-12                      2.707µ ±  3%    2.249µ ±  3%  -16.94% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=24-12                      3.077µ ±  2%    2.447µ ±  2%  -20.48% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=30-12                      5.099µ ±  2%    3.965µ ±  3%  -22.23% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=64-12                     10.196µ ±  2%    8.092µ ±  8%  -20.63% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=128-12                     19.86µ ±  3%    15.49µ ±  3%  -21.99% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=256-12                     38.70µ ±  3%    30.41µ ±  3%  -21.42% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=512-12                     77.30µ ±  1%    67.30µ ±  3%  -12.93% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=1024-12                    153.2µ ±  4%    132.1µ ±  4%  -13.76% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=2048-12                    306.9µ ±  4%    254.6µ ±  5%  -17.06% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=4096-12                    610.6µ ±  2%    500.3µ ±  1%  -18.06% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=8192-12                    1.259m ±  2%    1.008m ±  4%  -19.97% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=65536-12                  12.015m ±  2%    9.574m ±  2%  -20.31% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=262144-12                  61.55m ±  1%    50.48m ±  1%  -17.99% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=1048576-12                 340.1m ±  1%    291.6m ±  3%  -14.28% (p=0.002 n=6)
MapIterGrow/impl=runtimeMap/t=Int64/len=4194304-12                  1.424 ±  5%     1.275 ±  0%  -10.47% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=6-12                         12.13n ±  1%    12.39n ±  0%   +2.14% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=12-12                        13.90n ±  2%    15.02n ±  2%   +8.02% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=18-12                        13.67n ±  9%    15.25n ±  7%  +11.52% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=24-12                        13.81n ±  6%    15.40n ±  4%  +11.47% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=30-12                        13.57n ±  5%    15.07n ±  6%  +11.05% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=64-12                        14.08n ±  4%    15.28n ±  3%   +8.45% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=128-12                       15.36n ±  3%    15.34n ±  1%        ~ (p=0.699 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=256-12                       20.00n ±  6%    15.19n ±  5%  -24.01% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=512-12                       21.81n ±  3%    15.58n ±  2%  -28.58% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=1024-12                      24.02n ±  2%    17.38n ±  2%  -27.62% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=2048-12                      25.55n ±  2%    18.07n ±  1%  -29.30% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=4096-12                      26.70n ±  2%    18.21n ±  1%  -31.80% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=8192-12                      27.61n ±  1%    18.80n ±  1%  -31.89% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=65536-12                     33.68n ±  2%    26.35n ±  2%  -21.75% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=262144-12                    44.23n ±  1%    44.23n ±  2%        ~ (p=0.660 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=1048576-12                   75.89n ±  1%    87.50n ±  1%  +15.30% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int64/len=4194304-12                   82.94n ±  1%   102.20n ±  0%  +23.22% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=6-12                         12.34n ±  0%    11.98n ±  1%   -2.88% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=12-12                        13.71n ±  1%    15.41n ± 10%  +12.40% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=18-12                        13.69n ±  4%    15.35n ±  5%  +12.13% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=24-12                        13.85n ±  2%    16.19n ±  5%  +16.90% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=30-12                        13.65n ±  3%    15.32n ±  7%  +12.19% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=64-12                        13.84n ±  5%    15.56n ±  2%  +12.39% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=128-12                       13.89n ±  1%    15.69n ±  2%  +13.00% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=256-12                       14.58n ±  3%    15.67n ±  1%   +7.55% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=512-12                       17.13n ±  7%    15.72n ±  2%   -8.26% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=1024-12                      21.83n ±  3%    17.13n ±  3%  -21.53% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=2048-12                      24.52n ±  2%    17.45n ±  2%  -28.80% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=4096-12                      26.14n ±  1%    18.03n ±  2%  -31.04% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=8192-12                      26.90n ±  2%    18.47n ±  2%  -31.34% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=65536-12                     31.03n ±  1%    22.70n ±  1%  -26.84% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=262144-12                    36.25n ±  2%    31.57n ±  3%  -12.91% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=1048576-12                   69.42n ±  2%    75.62n ±  1%   +8.95% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=Int32/len=4194304-12                   79.60n ±  0%    93.00n ±  0%  +16.83% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=6-12                        20.75n ±  2%    17.43n ±  2%  -16.02% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=12-12                       16.97n ±  7%    20.41n ± 10%  +20.30% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=18-12                       16.30n ±  2%    19.23n ±  8%  +17.94% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=24-12                       16.55n ±  3%    18.66n ±  4%  +12.72% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=30-12                       16.15n ±  2%    18.96n ±  3%  +17.43% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=64-12                       16.36n ±  6%    18.69n ±  1%  +14.24% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=128-12                      17.18n ±  2%    19.75n ±  2%  +14.90% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=256-12                      19.82n ±  8%    20.27n ±  4%   +2.32% (p=0.015 n=6)
MapGetHit/impl=runtimeMap/t=String/len=512-12                      27.05n ±  2%    21.31n ±  1%  -21.22% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=1024-12                     32.20n ±  1%    23.76n ±  1%  -26.22% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=2048-12                     36.34n ±  2%    24.31n ±  1%  -33.09% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=4096-12                     38.74n ±  2%    25.12n ±  2%  -35.14% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=8192-12                     38.39n ±  1%    25.67n ±  1%  -33.13% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=65536-12                    49.44n ±  3%    38.72n ±  2%  -21.67% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=262144-12                   100.0n ±  1%    105.2n ±  2%   +5.20% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=1048576-12                  133.2n ±  2%    157.0n ±  1%  +17.91% (p=0.002 n=6)
MapGetHit/impl=runtimeMap/t=String/len=4194304-12                  146.0n ±  1%    172.2n ±  1%  +17.95% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=6-12                        15.38n ±  1%    14.65n ±  1%   -4.72% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=12-12                       17.28n ± 29%    15.35n ±  9%        ~ (p=0.065 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=18-12                       15.85n ± 27%    15.17n ±  8%        ~ (p=0.093 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=24-12                       20.36n ± 24%    15.25n ±  6%  -25.14% (p=0.009 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=30-12                       15.53n ±  1%    14.59n ±  5%   -6.08% (p=0.004 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=64-12                       15.63n ±  8%    15.08n ±  8%        ~ (p=0.240 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=128-12                      15.62n ±  1%    15.28n ±  4%        ~ (p=0.084 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=256-12                      15.79n ±  3%    15.14n ±  2%   -4.09% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=512-12                      16.20n ±  3%    15.55n ±  5%   -3.98% (p=0.041 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=1024-12                     16.42n ±  2%    16.48n ±  3%        ~ (p=0.699 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=2048-12                     16.93n ±  1%    16.93n ±  1%        ~ (p=0.937 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=4096-12                     17.12n ±  3%    17.02n ±  2%        ~ (p=0.310 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=8192-12                     17.55n ±  1%    17.59n ±  4%        ~ (p=0.909 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=65536-12                    25.95n ±  2%    21.77n ±  1%  -16.11% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=262144-12                   54.11n ±  3%    30.48n ±  1%  -43.67% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=1048576-12                  90.92n ±  2%    60.33n ±  1%  -33.64% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int64/len=4194304-12                 106.40n ±  1%    72.99n ±  2%  -31.40% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=6-12                        15.43n ±  0%    14.64n ±  0%   -5.12% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=12-12                       15.56n ± 61%    14.80n ±  6%   -4.85% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=18-12                       15.38n ±  3%    14.38n ±  4%   -6.47% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=24-12                       15.53n ± 38%    15.07n ± 11%        ~ (p=0.132 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=30-12                       15.47n ± 17%    14.30n ±  7%   -7.53% (p=0.004 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=64-12                       15.63n ±  7%    15.27n ±  8%        ~ (p=0.132 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=128-12                      16.05n ±  5%    15.26n ±  6%        ~ (p=0.065 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=256-12                      15.61n ±  3%    15.33n ± 10%        ~ (p=0.589 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=512-12                      15.74n ±  4%    15.80n ±  4%        ~ (p=0.818 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=1024-12                     15.91n ±  1%    16.19n ±  5%        ~ (p=0.180 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=2048-12                     16.34n ±  2%    16.55n ±  2%        ~ (p=0.225 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=4096-12                     16.79n ±  2%    17.04n ±  2%        ~ (p=0.141 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=8192-12                     17.18n ±  3%    17.25n ±  1%        ~ (p=0.729 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=65536-12                    22.41n ±  3%    20.07n ±  2%  -10.44% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=262144-12                   29.34n ±  1%    25.99n ±  1%  -11.42% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=1048576-12                  79.22n ±  2%    57.91n ±  2%  -26.90% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=Int32/len=4194304-12                 100.15n ±  1%    74.71n ±  1%  -25.40% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=6-12                       16.94n ±  1%    17.03n ± 19%        ~ (p=0.623 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=12-12                      20.18n ±  6%    17.66n ± 14%  -12.46% (p=0.026 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=18-12                      19.24n ±  8%    16.91n ±  7%  -12.08% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=24-12                      20.80n ±  9%    18.19n ± 12%  -12.57% (p=0.026 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=30-12                      19.01n ±  4%    16.32n ± 13%  -14.13% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=64-12                      18.96n ±  3%    18.19n ± 11%        ~ (p=0.132 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=128-12                     19.91n ±  5%    17.10n ±  4%  -14.12% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=256-12                     19.26n ±  1%    17.57n ±  3%   -8.75% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=512-12                     19.70n ±  3%    17.83n ±  4%   -9.49% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=1024-12                    21.38n ±  3%    19.12n ±  2%  -10.57% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=2048-12                    30.52n ±  1%    19.94n ±  3%  -34.67% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=4096-12                    26.25n ±  2%    20.18n ±  2%  -23.13% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=8192-12                    23.79n ±  3%    20.98n ±  2%  -11.79% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=65536-12                   36.29n ±  2%    27.18n ±  4%  -25.12% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=262144-12                 106.75n ±  1%    47.97n ±  1%  -55.07% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=1048576-12                122.60n ±  0%    78.64n ±  1%  -35.86% (p=0.002 n=6)
MapGetMiss/impl=runtimeMap/t=String/len=4194304-12                134.85n ±  1%    84.82n ±  1%  -37.10% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=6-12                        214.9n ±  1%    203.0n ±  1%   -5.51% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=12-12                       667.5n ±  3%    725.1n ±  1%   +8.64% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=18-12                       1.306µ ±  1%    1.447µ ±  2%  +10.76% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=24-12                       1.613µ ±  3%    1.665µ ±  1%   +3.25% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=30-12                       2.701µ ± 14%    2.825µ ±  3%        ~ (p=0.065 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=64-12                       5.886µ ±  3%    5.699µ ±  3%   -3.18% (p=0.015 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=128-12                      11.71µ ±  3%    11.56µ ±  2%        ~ (p=0.394 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=256-12                      22.89µ ±  3%    22.41µ ±  1%        ~ (p=0.143 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=512-12                      45.93µ ±  3%    44.83µ ±  4%        ~ (p=0.093 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=1024-12                     92.43µ ±  0%    93.79µ ±  2%   +1.46% (p=0.009 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=2048-12                     183.5µ ±  2%    197.8µ ±  3%   +7.75% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=4096-12                     369.9µ ±  2%    399.0µ ±  2%   +7.88% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=8192-12                     739.1µ ±  2%    816.0µ ±  4%  +10.41% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=65536-12                    6.457m ±  4%    7.792m ±  3%  +20.67% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=262144-12                   33.93m ±  2%    33.56m ±  2%        ~ (p=0.310 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=1048576-12                  197.0m ±  6%    172.6m ±  2%  -12.37% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int64/len=4194304-12                  929.3m ±  1%    894.2m ±  5%        ~ (p=0.065 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=6-12                        229.4n ±  0%    213.5n ±  2%   -6.95% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=12-12                       676.9n ±  2%    701.9n ±  2%   +3.69% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=18-12                       1.264µ ±  3%    1.353µ ±  3%   +7.08% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=24-12                       1.609µ ±  1%    1.593µ ±  3%        ~ (p=0.290 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=30-12                       2.527µ ±  2%    2.606µ ±  2%   +3.15% (p=0.015 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=64-12                       5.487µ ±  4%    5.326µ ±  2%   -2.93% (p=0.028 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=128-12                      11.03µ ±  2%    10.62µ ±  2%   -3.71% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=256-12                      21.71µ ±  1%    21.05µ ±  2%   -3.04% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=512-12                      43.19µ ±  3%    41.83µ ±  1%   -3.16% (p=0.009 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=1024-12                     86.48µ ±  2%    87.94µ ±  1%   +1.70% (p=0.015 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=2048-12                     170.3µ ±  2%    182.4µ ±  2%   +7.07% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=4096-12                     339.7µ ±  1%    374.8µ ±  2%  +10.35% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=8192-12                     681.6µ ±  2%    767.3µ ±  2%  +12.58% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=65536-12                    5.988m ±  1%    6.609m ±  3%  +10.37% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=262144-12                   27.86m ±  2%    29.82m ±  1%   +7.05% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=1048576-12                  157.8m ±  2%    148.9m ±  4%   -5.65% (p=0.004 n=6)
MapPutGrow/impl=runtimeMap/t=Int32/len=4194304-12                  831.9m ±  2%    802.9m ±  1%   -3.49% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=6-12                       228.5n ±  1%    225.4n ±  2%   -1.38% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=12-12                      804.4n ±  1%    847.5n ±  1%   +5.36% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=18-12                      1.707µ ±  2%    1.765µ ±  4%   +3.43% (p=0.009 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=24-12                      2.026µ ±  1%    2.023µ ±  3%        ~ (p=0.729 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=30-12                      3.532µ ±  1%    3.553µ ±  2%        ~ (p=0.589 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=64-12                      7.607µ ±  2%    7.379µ ±  2%   -2.99% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=128-12                     15.47µ ±  3%    14.94µ ±  4%   -3.44% (p=0.004 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=256-12                     31.30µ ±  1%    29.75µ ±  4%   -4.96% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=512-12                     64.72µ ±  4%    61.28µ ±  7%        ~ (p=0.065 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=1024-12                    127.4µ ±  2%    129.5µ ±  4%        ~ (p=0.180 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=2048-12                    254.1µ ±  2%    273.4µ ±  3%   +7.60% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=4096-12                    518.8µ ±  4%    551.4µ ±  1%   +6.28% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=8192-12                    1.204m ±  4%    1.212m ±  4%        ~ (p=0.310 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=65536-12                   10.73m ±  2%    11.72m ±  4%   +9.20% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=262144-12                  57.12m ±  2%    60.92m ±  2%   +6.66% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=1048576-12                 315.7m ±  3%    365.1m ±  1%  +15.66% (p=0.002 n=6)
MapPutGrow/impl=runtimeMap/t=String/len=4194304-12                  1.699 ±  2%     1.876 ±  1%  +10.37% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=6-12                 86.19n ±  2%    71.38n ±  2%  -17.18% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=12-12                338.7n ±  3%    327.0n ±  3%   -3.45% (p=0.009 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=18-12                551.9n ±  2%    461.5n ±  3%  -16.38% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=24-12                767.8n ±  3%    549.8n ±  2%  -28.39% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=30-12                957.9n ±  2%    759.1n ±  6%  -20.75% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=64-12                2.179µ ±  1%    1.428µ ±  5%  -34.47% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=128-12               4.139µ ±  1%    2.716µ ±  6%  -34.39% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=256-12               8.017µ ±  2%    5.228µ ±  2%  -34.78% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=512-12               15.84µ ±  1%    10.28µ ±  6%  -35.12% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=1024-12              32.60µ ±  4%    22.35µ ±  6%  -31.45% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=2048-12              65.90µ ±  2%    44.30µ ±  1%  -32.78% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=4096-12             134.96µ ±  2%    91.81µ ±  4%  -31.97% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=8192-12              277.6µ ±  2%    198.6µ ±  1%  -28.45% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=65536-12             2.644m ±  4%    2.004m ±  3%  -24.20% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=262144-12            14.98m ±  2%    13.04m ±  2%  -12.97% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=1048576-12           85.11m ±  1%   104.70m ±  1%  +23.02% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int64/len=4194304-12           389.7m ±  1%    518.2m ±  1%  +32.97% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=6-12                 83.28n ±  3%    70.45n ±  3%  -15.40% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=12-12                296.9n ±  2%    290.2n ±  6%        ~ (p=0.240 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=18-12                476.0n ±  2%    387.8n ±  2%  -18.53% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=24-12                696.0n ±  6%    463.9n ±  3%  -33.34% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=30-12                814.1n ±  3%    584.3n ±  5%  -28.23% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=64-12                1.784µ ±  2%    1.110µ ±  3%  -37.78% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=128-12               3.528µ ±  2%    2.111µ ±  3%  -40.14% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=256-12               6.893µ ±  2%    4.187µ ±  3%  -39.26% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=512-12              13.357µ ±  1%    8.124µ ±  4%  -39.18% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=1024-12              26.51µ ±  1%    17.26µ ±  4%  -34.89% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=2048-12              55.40µ ±  2%    36.30µ ±  3%  -34.48% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=4096-12             111.33µ ±  2%    73.30µ ±  2%  -34.16% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=8192-12              228.1µ ±  5%    151.4µ ±  4%  -33.62% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=65536-12             2.224m ±  3%    1.457m ±  6%  -34.52% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=262144-12           11.673m ±  1%    9.105m ±  1%  -22.00% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=1048576-12           75.28m ±  3%    82.89m ±  2%  +10.11% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=Int32/len=4194304-12           361.5m ±  1%    481.2m ±  1%  +33.10% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=6-12                92.97n ±  6%    84.52n ±  3%   -9.09% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=12-12               428.1n ±  3%    431.2n ±  3%        ~ (p=0.197 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=18-12               728.5n ±  2%    667.9n ±  3%   -8.32% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=24-12               929.3n ±  2%    759.6n ±  4%  -18.26% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=30-12               1.252µ ±  2%    1.088µ ±  7%  -13.14% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=64-12               2.670µ ±  3%    2.167µ ±  3%  -18.81% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=128-12              5.244µ ±  3%    4.204µ ±  5%  -19.83% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=256-12             10.268µ ±  2%    8.237µ ±  3%  -19.78% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=512-12              21.81µ ±  5%    17.43µ ±  4%  -20.05% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=1024-12             43.70µ ±  2%    37.63µ ±  2%  -13.89% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=2048-12             86.65µ ±  4%    77.96µ ±  1%  -10.03% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=4096-12             170.6µ ±  2%    175.5µ ±  5%        ~ (p=0.132 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=8192-12             380.1µ ±  2%    417.2µ ±  9%   +9.77% (p=0.015 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=65536-12            4.017m ±  2%    4.370m ±  2%   +8.81% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=262144-12           21.71m ±  1%    24.02m ±  1%  +10.64% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=1048576-12          107.5m ±  3%    156.8m ±  1%  +45.89% (p=0.002 n=6)
MapPutPreAllocate/impl=runtimeMap/t=String/len=4194304-12          493.1m ±  4%    718.1m ±  7%  +45.62% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=6-12                       89.60n ±  2%    74.71n ±  3%  -16.61% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=12-12                      252.6n ±  1%    162.5n ±  2%  -35.68% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=18-12                      411.8n ±  0%    236.1n ±  1%  -42.66% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=24-12                      618.8n ±  1%    313.0n ±  3%  -49.41% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=30-12                      689.0n ±  1%    394.9n ±  2%  -42.68% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=64-12                     1548.0n ±  1%    817.4n ±  2%  -47.20% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=128-12                     3.099µ ±  1%    1.603µ ± 15%  -48.29% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=256-12                     6.173µ ±  2%    3.285µ ±  8%  -46.78% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=512-12                    12.247µ ±  2%    6.486µ ±  9%  -47.04% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=1024-12                    24.50µ ±  1%    15.38µ ±  5%  -37.22% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=2048-12                    50.60µ ±  2%    31.56µ ±  2%  -37.62% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=4096-12                   103.25µ ±  1%    63.62µ ±  2%  -38.38% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=8192-12                    212.2µ ±  2%    132.1µ ±  1%  -37.73% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=65536-12                   2.138m ±  1%    1.538m ±  3%  -28.08% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=262144-12                  13.27m ±  1%    12.29m ±  6%   -7.39% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=1048576-12                 85.23m ±  2%   105.04m ±  1%  +23.24% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int64/len=4194304-12                 381.8m ±  1%    531.8m ±  1%  +39.27% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=6-12                       87.91n ±  1%    73.96n ±  3%  -15.87% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=12-12                      241.2n ±  2%    161.5n ±  1%  -33.03% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=18-12                      386.9n ±  1%    239.3n ±  8%  -38.14% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=24-12                      577.9n ±  1%    310.8n ±  9%  -46.21% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=30-12                      651.5n ±  2%    378.6n ±  7%  -41.90% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=64-12                     1421.0n ±  3%    804.0n ±  5%  -43.42% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=128-12                     2.841µ ±  4%    1.585µ ±  3%  -44.23% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=256-12                     5.665µ ±  1%    3.111µ ±  2%  -45.08% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=512-12                    11.157µ ±  1%    6.202µ ±  5%  -44.41% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=1024-12                    22.08µ ±  1%    14.28µ ±  6%  -35.32% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=2048-12                    45.23µ ±  2%    29.47µ ±  4%  -34.84% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=4096-12                    93.92µ ±  2%    59.21µ ±  2%  -36.95% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=8192-12                    192.4µ ±  1%    120.6µ ±  1%  -37.30% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=65536-12                   1.821m ±  3%    1.205m ±  2%  -33.79% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=262144-12                  9.197m ±  2%    6.460m ±  2%  -29.76% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=1048576-12                 74.95m ±  1%    80.14m ±  1%   +6.93% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=Int32/len=4194304-12                 364.0m ±  2%    473.0m ±  2%  +29.95% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=6-12                     104.60n ±  3%    89.22n ±  3%  -14.70% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=12-12                     278.5n ±  1%    209.0n ±  2%  -24.96% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=18-12                     449.3n ±  2%    310.9n ±  3%  -30.80% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=24-12                     654.4n ±  1%    409.8n ±  3%  -37.38% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=30-12                     746.6n ±  1%    534.8n ±  6%  -28.37% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=64-12                     1.602µ ±  4%    1.083µ ± 14%  -32.41% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=128-12                    3.201µ ±  1%    2.194µ ±  4%  -31.45% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=256-12                    6.431µ ±  2%    4.276µ ±  3%  -33.50% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=512-12                   13.192µ ±  1%    8.812µ ±  3%  -33.20% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=1024-12                   27.44µ ±  2%    19.59µ ±  4%  -28.62% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=2048-12                   55.23µ ±  1%    40.10µ ±  2%  -27.40% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=4096-12                  112.11µ ±  1%    81.29µ ±  2%  -27.49% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=8192-12                   232.4µ ±  1%    165.7µ ±  2%  -28.68% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=65536-12                  2.517m ±  1%    1.995m ±  2%  -20.75% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=262144-12                 20.22m ±  1%    20.49m ±  3%        ~ (p=0.394 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=1048576-12                101.7m ±  2%    148.5m ±  2%  +45.95% (p=0.002 n=6)
MapPutReuse/impl=runtimeMap/t=String/len=4194304-12                440.4m ±  2%    672.5m ±  1%  +52.72% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=6-12                      33.64n ±  3%    31.80n ±  1%   -5.45% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=12-12                     34.45n ±  6%    37.78n ± 10%   +9.65% (p=0.015 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=18-12                     33.81n ±  2%    35.49n ± 21%   +4.97% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=24-12                     35.58n ±  4%    38.76n ± 16%   +8.94% (p=0.009 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=30-12                     32.94n ±  5%    36.59n ±  7%  +11.07% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=64-12                     34.25n ±  3%    37.76n ±  5%  +10.23% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=128-12                    35.71n ±  4%    39.31n ±  6%  +10.07% (p=0.004 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=256-12                    38.99n ±  2%    38.92n ±  4%        ~ (p=0.937 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=512-12                    46.46n ±  4%    38.70n ±  6%  -16.69% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=1024-12                   53.06n ±  3%    42.86n ±  7%  -19.21% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=2048-12                   57.31n ±  2%    43.41n ±  3%  -24.26% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=4096-12                   57.91n ±  2%    44.19n ±  1%  -23.71% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=8192-12                   57.91n ±  2%    45.24n ±  2%  -21.89% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=65536-12                  68.67n ±  1%    60.08n ±  2%  -12.52% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=262144-12                 101.4n ±  1%    101.7n ±  2%        ~ (p=0.420 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=1048576-12                153.8n ±  0%    185.7n ±  2%  +20.67% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int64/len=4194304-12                170.5n ±  0%    222.0n ±  1%  +30.20% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=6-12                      33.35n ±  1%    32.17n ± 11%        ~ (p=0.065 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=12-12                     35.68n ±  6%    36.21n ± 19%        ~ (p=0.260 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=18-12                     33.67n ±  4%    36.96n ± 20%   +9.79% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=24-12                     35.32n ±  8%    41.27n ± 14%  +16.88% (p=0.015 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=30-12                     32.58n ±  6%    35.83n ±  2%   +9.94% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=64-12                     34.06n ±  4%    37.87n ±  6%  +11.16% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=128-12                    35.44n ±  5%    38.56n ±  4%   +8.82% (p=0.004 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=256-12                    40.30n ±  8%    37.64n ±  3%   -6.60% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=512-12                    47.58n ±  3%    38.43n ±  4%  -19.23% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=1024-12                   52.65n ±  2%    41.01n ±  2%  -22.11% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=2048-12                   54.69n ±  2%    41.79n ±  2%  -23.57% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=4096-12                   54.96n ±  1%    42.90n ±  2%  -21.93% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=8192-12                   54.92n ±  1%    43.41n ±  2%  -20.96% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=65536-12                  60.10n ±  2%    49.65n ±  4%  -17.38% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=262144-12                 70.95n ±  2%    65.00n ±  1%   -8.39% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=1048576-12                127.2n ±  1%    134.5n ±  3%   +5.74% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=Int32/len=4194304-12                153.4n ±  1%    178.3n ±  2%  +16.26% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=6-12                     41.20n ±  2%    43.83n ± 19%   +6.37% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=12-12                    42.38n ± 13%    48.95n ±  7%  +15.53% (p=0.015 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=18-12                    40.40n ±  8%    47.32n ± 11%  +17.13% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=24-12                    43.39n ±  6%    52.47n ± 11%  +20.91% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=30-12                    40.95n ±  5%    47.22n ±  3%  +15.31% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=64-12                    42.11n ±  8%    48.48n ±  7%  +15.12% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=128-12                   47.79n ±  2%    48.51n ±  7%        ~ (p=0.485 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=256-12                   60.94n ±  3%    48.96n ±  3%  -19.65% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=512-12                   68.62n ±  4%    50.65n ±  5%  -26.19% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=1024-12                  75.42n ±  3%    53.60n ± 20%  -28.94% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=2048-12                  77.80n ±  2%    55.09n ± 23%  -29.18% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=4096-12                  79.21n ±  1%    55.66n ±  2%  -29.72% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=8192-12                  78.46n ±  1%    56.10n ±  2%  -28.50% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=65536-12                 92.72n ±  1%    76.27n ±  4%  -17.74% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=262144-12                153.4n ±  1%    156.1n ±  6%   +1.79% (p=0.009 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=1048576-12               190.2n ±  1%    230.8n ±  1%  +21.35% (p=0.002 n=6)
MapPutDelete/impl=runtimeMap/t=String/len=4194304-12               204.6n ±  1%    261.4n ±  1%  +27.76% (p=0.002 n=6)
geomean                                                            1.898µ          1.654µ        -12.90%

To summarize:

Access and assignment of large (>1024 entries) maps improved ~30%. Access of small maps do have small regressions in some cases.
Assignment into pre-sized maps improved ~35%.
Iteration faster across the board by ~10%, ~60% for maps with low load (large size, few entries).
Application benchmarks in sweet speed up by geomean of ~1.5%.

Some follow-up issues already filed:

I want to give a big shout-out of thanks to everyone that helped out with this. @petermattis for https://github.com/cockroachdb/swiss, which the runtime implementation is heavily based on [1]. @zhangyunhao116 and @thepudds for your implementations that helped prove feasibility and explore the design space. Plus everyone else that has contributed to the discussion here!

[1] I should file issues on your repo for the correctness issues I found in that design! 😅

RaduBerinde · 2024-12-13T22:01:54Z

[1] I should file issues on your repo for the correctness issues I found in that design!

Please do, that would be appreciated!

gopherbot · 2024-12-16T02:41:34Z

Change https://go.dev/cl/634396 mentions this issue: internal/runtime/maps: speed up small map lookups ~1.7x for unpredictable keys

gopherbot · 2025-01-14T00:27:41Z

Change https://go.dev/cl/642376 mentions this issue: internal/runtime/maps: re-enable some tests

Re-enable tests for stack-allocated maps and fast map accessors. Those are implemented now. Update #54766 Change-Id: I8c019702bd9fb077b2fe3f7c78e8e9e10d2263a6 Reviewed-on: https://go-review.googlesource.com/c/go/+/642376 LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com> Reviewed-by: Keith Randall <khr@google.com> Reviewed-by: Michael Pratt <mpratt@google.com> Auto-Submit: Keith Randall <khr@golang.org>

…able keys On master, lookups on small Swiss Table maps (<= 8 elements) for non-specialized key types are seemingly a performance regression compared to the Go 1.23 map implementation (reported in #70849). Currently, a linear scan is used for gets in these cases. This CL changes (*Map).getWithKeySmall to instead use the SIMD or SWAR match on the control bytes to then jump to candidate matching slots, with sample results below for a 16-byte key. This especially helps the hit case when the key is unpredictable, which previously had to scan an unpredictable number of control bytes to find a candidate slot when the key is unpredictable. Separately, other CLs in this stack modify the main Swiss Table benchmarks to randomize lookup key order (vs. previously most of the benchmarks had a repeating lookup key ordering, which likely is predictable until the map is too big). We have sample results for the randomized key order benchmarks followed by results from the older benchmarks. The first table below is with randomized key order. For hits, the older results get slower as there are more elements. With this CL, we see hits for unpredictable key ordering (sizes 2-8) get a ~1.7x speedup from ~25ns to ~14ns, with a now consistent lookup time for the different sizes. (The 1 element size map has a predictable key ordering because there is only one key, and that reports a modest ~0.5ns or ~3% performance penalty). Misses for unpredictable key order get a ~1.3x speedup, from ~13ns to ~10ns, with similar results for the 1 element size. │ no-fix-new-bmarks │ fix-with-new-bmarks │ │ sec/op │ sec/op vs base │ MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4 13.26n ± 0% 13.64n ± 0% +2.90% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=2-4 19.47n ± 0% 13.62n ± 0% -30.05% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=3-4 22.23n ± 0% 13.64n ± 0% -38.68% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=4-4 23.98n ± 0% 13.64n ± 0% -43.11% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=5-4 25.02n ± 0% 13.67n ± 0% -45.35% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=6-4 25.77n ± 1% 13.68n ± 2% -46.89% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=7-4 26.38n ± 0% 13.64n ± 0% -48.28% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=8-4 26.31n ± 0% 13.71n ± 21% -47.90% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4 13.055n ± 0% 9.815n ± 0% -24.82% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=2-4 13.070n ± 0% 9.813n ± 0% -24.92% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=3-4 13.060n ± 0% 9.819n ± 0% -24.82% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=4-4 13.075n ± 0% 9.816n ± 0% -24.92% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=5-4 13.060n ± 0% 9.826n ± 0% -24.76% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=6-4 13.095n ± 19% 9.834n ± 31% -24.90% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=7-4 13.075n ± 19% 9.822n ± 27% -24.88% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=8-4 13.11n ± 16% 12.14n ± 19% -7.43% (p=0.000 n=20) The next table uses the original benchmarks from just before this CL stack (i.e., without shuffling lookup keys). With this CL, we see improvement that is directionally similar to the above results but not as large, presumably because the branches in the linear scan are fairly predictable with predictable keys. (The numbers here also include the time from a mod in the benchmark code, which seemed to take around ~1/3 of CPU time based on spot checking a couple of examples, vs. the modified benchmarks shown above have removed that mod). │ master-8c3e391573 │ just-fix-with-old-bmarks │ │ sec/op │ sec/op vs base │ MapSmallAccessHit/Key=smallType/Elem=int32/len=1-4 20.85n ± 0% 21.69n ± 0% +4.03% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=2-4 21.22n ± 0% 21.70n ± 0% +2.24% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=3-4 21.73n ± 0% 21.71n ± 0% ~ (p=0.158 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=4-4 22.06n ± 0% 21.71n ± 0% -1.56% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=5-4 22.41n ± 0% 21.73n ± 0% -3.01% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=6-4 22.71n ± 0% 21.72n ± 0% -4.38% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=7-4 22.98n ± 0% 21.71n ± 0% -5.53% (p=0.000 n=20) MapSmallAccessHit/Key=smallType/Elem=int32/len=8-4 23.20n ± 0% 21.72n ± 0% -6.36% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=1-4 19.95n ± 0% 17.30n ± 0% -13.28% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=2-4 19.96n ± 0% 17.31n ± 0% -13.28% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=3-4 19.95n ± 0% 17.29n ± 0% -13.33% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=4-4 19.95n ± 0% 17.30n ± 0% -13.29% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=5-4 19.96n ± 25% 17.32n ± 0% -13.22% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=6-4 19.99n ± 24% 17.29n ± 0% -13.51% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=7-4 19.97n ± 20% 17.34n ± 16% -13.14% (p=0.000 n=20) MapSmallAccessMiss/Key=smallType/Elem=int32/len=8-4 20.02n ± 11% 17.33n ± 14% -13.44% (p=0.000 n=20) geomean 21.02n 19.39n -7.78% See #70849 for additional benchmark results, including results for arm64 (which also means without SIMD support). Updates #54766 Updates #70700 Fixes #70849 Change-Id: Ic2361bb6fc15b4436d1d1d5be7e4712e547f611b Reviewed-on: https://go-review.googlesource.com/c/go/+/634396 Reviewed-by: Michael Pratt <mpratt@google.com> Reviewed-by: Dmitri Shuralyov <dmitshur@google.com> LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>

gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Aug 30, 2022

seankhliao added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Aug 30, 2022

egonelbre mentioned this issue Aug 30, 2022

sync: improve Map performance with lock free list #54720

Closed

marco-m-pix4d mentioned this issue Aug 31, 2022

add a generic set data structure Pix4D/cogito#99

Merged

mknyszek added this to Go Compiler / Runtime Aug 31, 2022

mknyszek added this to the Unplanned milestone Aug 31, 2022

mknyszek assigned zhangyunhao116 Aug 31, 2022

mknyszek moved this to In Progress in Go Compiler / Runtime Aug 31, 2022

julieqiu added this to Go Security Sep 8, 2022

julieqiu removed this from Go Security Sep 8, 2022

zigo101 mentioned this issue Nov 29, 2024

proposal: language: allow getting capacity of map? #52157

Closed

gabyhelp mentioned this issue Dec 5, 2024

runtime: some possible SwissTable map benchmark improvements #70700

Open

DmitriyMV mentioned this issue Dec 9, 2024

chore: update hashtriemap implementation from the latest upstream siderolabs/gen#22

Merged

gabyhelp mentioned this issue Dec 13, 2024

runtime: map cold cache improvements #70835

Open

prattmic closed this as completed Dec 13, 2024

github-project-automation bot moved this from In Progress to Done in Go Compiler / Runtime Dec 13, 2024

thepudds mentioned this issue Dec 14, 2024

runtime: performance regression for small Swiss Table map access for non-specialized keys #70849

Closed

This was referenced Dec 17, 2024

Go language spec violations during iteration cockroachdb/swiss#39

Open

spec: clarify that map iteration always yields the latest version of an entry #70916

Open

3052 mentioned this issue Feb 11, 2025

runtime: map[int64]struct{} requires 16 bytes per slot #71368

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

runtime: use SwissTable #54766

runtime: use SwissTable #54766

zhangyunhao116 commented Aug 30, 2022 •

edited

Loading

zhangyunhao116 commented Aug 30, 2022 •

edited

Loading

gopherbot commented Aug 30, 2022

seankhliao commented Aug 30, 2022

prattmic commented Aug 30, 2022

aaronbee commented Aug 30, 2022

aaronbee commented Aug 30, 2022

randall77 commented Aug 30, 2022

aclements commented Aug 31, 2022

mknyszek commented Aug 31, 2022

zhangyunhao116 commented Sep 2, 2022

beoran commented Sep 5, 2022

zhangyunhao116 commented Sep 6, 2022 •

edited

Loading

beoran commented Sep 6, 2022

aclements commented Sep 7, 2022

aclements commented Sep 7, 2022

CAFxX commented Sep 8, 2022

josharian commented Sep 8, 2022

zhangyunhao116 commented Sep 13, 2022 •

edited

Loading

zhangyunhao116 commented Sep 14, 2022

aclements commented Sep 19, 2022

gopherbot commented Nov 21, 2024

gopherbot commented Nov 21, 2024

gopherbot commented Dec 12, 2024

gopherbot commented Dec 12, 2024

gopherbot commented Dec 13, 2024

rabbbit commented Dec 13, 2024

prattmic commented Dec 13, 2024

prattmic commented Dec 13, 2024 •

edited

Loading

RaduBerinde commented Dec 13, 2024

gopherbot commented Dec 16, 2024

gopherbot commented Jan 14, 2025

runtime: use SwissTable #54766

runtime: use SwissTable #54766

Comments

zhangyunhao116 commented Aug 30, 2022 • edited Loading

Abstract

Motivations

Implementations

Tasks

Advantages compared to the original implementation

Disadvantages compared to the original implementation

Implementation details

Differences with SwissTable

Differences with the original implementation

References

zhangyunhao116 commented Aug 30, 2022 • edited Loading

Performance comparison

Platform

Benchmark-1

Benchmark-2

gopherbot commented Aug 30, 2022

seankhliao commented Aug 30, 2022

prattmic commented Aug 30, 2022

aaronbee commented Aug 30, 2022

aaronbee commented Aug 30, 2022

randall77 commented Aug 30, 2022

aclements commented Aug 31, 2022

mknyszek commented Aug 31, 2022

zhangyunhao116 commented Sep 2, 2022

beoran commented Sep 5, 2022

zhangyunhao116 commented Sep 6, 2022 • edited Loading

beoran commented Sep 6, 2022

aclements commented Sep 7, 2022

aclements commented Sep 7, 2022

CAFxX commented Sep 8, 2022

josharian commented Sep 8, 2022

zhangyunhao116 commented Sep 13, 2022 • edited Loading

zhangyunhao116 commented Sep 14, 2022

aclements commented Sep 19, 2022

gopherbot commented Nov 21, 2024

gopherbot commented Nov 21, 2024

gopherbot commented Dec 12, 2024

gopherbot commented Dec 12, 2024

gopherbot commented Dec 13, 2024

rabbbit commented Dec 13, 2024

prattmic commented Dec 13, 2024

prattmic commented Dec 13, 2024 • edited Loading

RaduBerinde commented Dec 13, 2024

gopherbot commented Dec 16, 2024

gopherbot commented Jan 14, 2025

zhangyunhao116 commented Aug 30, 2022 •

edited

Loading

zhangyunhao116 commented Aug 30, 2022 •

edited

Loading

zhangyunhao116 commented Sep 6, 2022 •

edited

Loading

zhangyunhao116 commented Sep 13, 2022 •

edited

Loading

prattmic commented Dec 13, 2024 •

edited

Loading