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

[Joshua Cao]

On Thu, 4 Apr 2024 22:17:33 GMT, Joshua Cao <duke at openjdk.org> wrote:

>> 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
>> HashM...
>
> Joshua Cao has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Use @link for javadoc

I tried looking at the docs with `make docs-image`, but I can't test that the syntax/links are actually correct because `@implNote` does not actually show up in the web pages. As I understand from [the original proposal](https://mail.openjdk.org/pipermail/lambda-libs-spec-experts/2013-January/001211.html), `@implNote` is there to help to developer understand implementation, and is not intended to be exposed in the web docs.

This seems like information that would be useful to the consumer. So maybe we can consider moving this into the main comment block?

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

PR Comment: https://git.openjdk.org/jdk/pull/17544#issuecomment-2038341734