RFR: 8324573: HashMap::putAll add notes for conservative resizing [v8]

[Joshua Cao]

> Add notes for `HashMap::putAll()` conservative resizing.
> 
> Note: everything below this line is from the original change. After discussion, we decided to keep the conservative resizing, but we should add an `@implNote` for the decision.
> 
> ---
> 
> This change mirrors what we did for ConcurrentHashMap in https://github.com/openjdk/jdk/pull/17116. When we add all entries from one map to anther, we should resize that map to the size of the sum of both maps.
> 
> I used the command below to run the benchmarks. I set a high heap to reduce garbage collection noise.
> 
> java -Xms25G -jar benchmarks.jar -p size=100000 -p addSize=100000 -gc true org.openjdk.bench.java.util.HashMapBench
> 
> 
> Before change
> 
> 
> Benchmark            (addSize)        (mapType)  (size)  Mode  Cnt   Score   Error  Units
> HashMapBench.putAll     100000         HASH_MAP  100000  avgt    4  22.927 ± 3.170  ms/op
> HashMapBench.putAll     100000  LINKED_HASH_MAP  100000  avgt    4  25.198 ± 2.189  ms/op
> 
> 
> After change
> 
> 
> Benchmark            (addSize)        (mapType)  (size)  Mode  Cnt   Score   Error  Units
> HashMapBench.putAll     100000         HASH_MAP  100000  avgt    4  16.780 ± 0.526  ms/op
> HashMapBench.putAll     100000  LINKED_HASH_MAP  100000  avgt    4  19.721 ± 0.349  ms/op
> 
> 
> We see about average time improvements of 26% in HashMap and 20% in LinkedHashMap.
> 
> ---
> 
> In the worse case, we may have two maps with identical keys. In this case, we would aggressively resize when we do not need to. I'm also adding an additional `putAllSameKeys` benchmark.
> 
> Before change:
> 
> 
> Benchmark                                       (addSize)        (mapType)  (size)  Mode  Cnt        Score   Error   Units
> HashMapBench.putAllSameKeys                        100000         HASH_MAP  100000  avgt             6.956           ms/op
> HashMapBench.putAllSameKeys:gc.alloc.rate          100000         HASH_MAP  100000  avgt          1091.383          MB/sec
> HashMapBench.putAllSameKeys:gc.alloc.rate.norm     100000         HASH_MAP  100000  avgt       7968871.917            B/op
> HashMapBench.putAllSameKeys:gc.count               100000         HASH_MAP  100000  avgt               ≈ 0          counts
> HashMapBench.putAllSameKeys                        100000  LINKED_HASH_MAP  100000  avgt             8.417           ms/op
> HashMapBench.putAllSameKeys:gc.alloc.rate          100000  LINKED_HASH_MAP  100000  avgt           992.543          MB/sec
> HashMapBench.putAllSameKeys:gc.alloc.rate.norm     100000  LINKED_HASH_MAP  100000  avgt       87...

Joshua Cao has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains 11 additional commits since the last revision:

 - Move implNote to putAll()
 - Merge branch 'master' into hashmap
 - Use @link for javadoc
 - Update implNotes to explain conservative resizing decisions and suggest
   options to avoid expensive resizing
 - Merge branch 'master' into hashmap
 - Add note about conservative resizing
 - Merge branch 'master' into hashmap
 - extract msize variable
 - Use max of both sizes and other maps size in case of overflow
 - Add benchmark with all duplicate keys
 - ... and 1 more: https://git.openjdk.org/jdk/compare/0e273613...2644e4d7

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

Changes:
  - all: https://git.openjdk.org/jdk/pull/17544/files
  - new: https://git.openjdk.org/jdk/pull/17544/files/8db9e125..2644e4d7

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=17544&range=07
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=17544&range=06-07

  Stats: 31023 lines in 760 files changed: 13382 ins; 12516 del; 5125 mod
  Patch: https://git.openjdk.org/jdk/pull/17544.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17544/head:pull/17544

PR: https://git.openjdk.org/jdk/pull/17544