On Tue, 11 Nov 2025 19:27:28 GMT, jengebr <[email protected]> wrote: > # 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 ...
This pull request has now been integrated. Changeset: 13c92d0d Author: John Engebretson <[email protected]> Committer: Stuart Marks <[email protected]> URL: https://git.openjdk.org/jdk/commit/13c92d0d4d137c7d83a946d1fcd2dfc5686e7b51 Stats: 225 lines in 4 files changed: 224 ins; 0 del; 1 mod 8371656: HashMap.putAll() optimizations Reviewed-by: smarks ------------- PR: https://git.openjdk.org/jdk/pull/28243
