> 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
