> # HashMap.putAll() optimizations > > ## Summary > > This PR adds fast paths to `HashMap.putMapEntries()` for `HashMap` and > `Collections.UnmodifiableMap(HashMap)` sources. These deliver 66-86% > improvement for the targeted cases with zero regression for other map types. > > ## Problem > > `HashMap.putMapEntries()` iterates via `entrySet()` using a chain of virtual > calls: `entrySet()`, `iterator()`, `hasNext()`, `next()`, `getKey()`, > `getValue()` and `hashCode()`. These call sites are inherently megamorphic > because `putMapEntries()` accepts any Map implementation. The JIT cannot > devirtualize them. `UnmodifiableMap` compounds the problem by adding a > megamorphic wrapper layer on top. > > See JDK-8368292 for full analysis. > > ## Solution > > `putMapEntries()` checks whether the source is exactly `HashMap.class` or an > `UnmodifiableMap` wrapping one. If so, it dispatches to `putHashMapEntries()` > which walks the source `Node[]` table directly. This eliminates the > megamorphic iteration call sites and reuses the pre-computed hash stored in > each Node — avoiding redundant `hashCode()` calls on every key. > > An exact class identity check (not `instanceof`) is used for `HashMap` to > prevent subclasses from entering the fast path. This avoids correctness > issues with overridden behavior and keeps the fast path monomorphic. > > `UnmodifiableMap.m` visibility is changed from `private` to package-private. > The class remains non-public and is only accessible within `java.util`. > > ## Performance > > Benchmarks use `BigInteger(128)` keys whose `hashCode()` is not cached. Call > sites are poisoned with five Map types to simulate real-world megamorphic > conditions. Platform: aarch64 (AWS Graviton). > > ### Optimized paths (poisoned call sites) > > > Source │Size│Baseline (ns/op)│Optimized (ns/op)│Improvement > ─────────────────────────┼────┼────────────────┼─────────────────┼─────────── > HashMap │ 5 │ 202.1 ± 0.6 │ 78.0 ± 0.3 │ 61% > HashMap │ 25 │ 906.4 ± 1.0│ 286.1 ± 2.5 │ 68% > HashMap │150 │ 6654.2 ± 40.9│ 1539.1 ± 27.6 │ 77% > UnmodifiableMap(HashMap) │ 5 │ 352.7 ± 0.6 │ 77.5 ± 1.0 │ 78% > UnmodifiableMap(HashMap) │ 25 │ 1772.3 ± 5.6 │ 289.6 ± 2.5 │ 84% > UnmodifiableMap(HashMap) │150 │ 10593.2 ± 37.5│ 1533.1 ± 20.4 │ 86% > > > ### Non-optimized paths (poisoned, size=150) > > > Source │Baseline (ns/op)│Optimized (ns/op)│Delta > ─────────────────────────┼────────────────┼─────────────────┼───── > TreeMap ...
jengebr has updated the pull request incrementally with one additional commit since the last revision: Addressing review feedback on benchmark & test ------------- Changes: - all: https://git.openjdk.org/jdk/pull/28243/files - new: https://git.openjdk.org/jdk/pull/28243/files/e7ba79e6..792f28b6 Webrevs: - full: https://webrevs.openjdk.org/?repo=jdk&pr=28243&range=08 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=28243&range=07-08 Stats: 81 lines in 2 files changed: 12 ins; 51 del; 18 mod Patch: https://git.openjdk.org/jdk/pull/28243.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/28243/head:pull/28243 PR: https://git.openjdk.org/jdk/pull/28243
