On Thu, 9 Apr 2026 14:45:48 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 │ 227.3 ± 0.6 │ 78.4 ± 0.3 │ 66% >> HashMap │ 25 │ 1037.0 ± 22.9│ 286.0 ± 4.0 │ 72% >> 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 > ... > > jengebr has updated the pull request incrementally with one additional commit > since the last revision: > > Reformatting per comments, adding expensive hashCode() to benchmark
HashMap and benchmark are updated to match comments, and PR description is updated with revised data. The benchmark now uses BigInteger instead of String and it significantly increased the measured value of the change. UnmodifiableMap(TreeMap) is not optimized. I am OK proceeding with or without that. ------------- PR Comment: https://git.openjdk.org/jdk/pull/28243#issuecomment-4215222016
