On Wed, 15 Apr 2026 12:53:36 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:
>
> PR feedback - types in putHashMapEntries
OK, the changes in the library source files look good. I've looked through the
test and the benchmark files and I have several cleanup-level comments, nothing
major. I've also submitted a job into our internal CI system and I'll let you
know if any issues arise.
test/jdk/java/util/Collection/MOAT.java line 431:
> 429:
> 430: target.putAll(new HashMap<>(testData));
> 431: equal(target.size(), testData.size());
It's not necessary to check equality of sizes, since this is implicit in the
Map.equals() contract -- the sizes must be the same. So this line can be
removed.
Similar for other equal-size checks in the cases below.
test/jdk/java/util/Collection/MOAT.java line 753:
> 751: HashMap<Integer,Integer> target = new HashMap<>();
> 752: target.putAll(m);
> 753: check(target.equals(m));
I don't think this case is necessary. The point of the `testImmutableMap`
method is to test that the map `m` under test cannot be modified by calling the
various map mutator methods. (Yeah, maybe this method is misnamed.)
The lines added here test HashMap `target` to see if it handles `putAll` when
the argument is an immutable/unmodifiable map. That's already tested by the new
test method `testHashMapPutAll`, which tests `putAll` with all four
combinations of HashMap/non-HashMap and non-wrapped/unmodifiably-wrapped
arguments.
test/jdk/java/util/Collection/MOAT.java line 1495:
> 1493: m.clear();
> 1494: m.putAll(source);
> 1495: check(m.equals(source));
Hm. It turns out that `putAll` is barely tested in MOAT (only a couple special
cases) and so the test assertions made here should be very general. Maybe
something like this:
int oldSize = m.size();
Map<Integer,Integer> source = Map.of(10, 1000, 11, 1001, 12,
1002);
m.putAll(source);
check(m.entrySet().containsAll(source.entrySet()));
check(m.size() == oldSize + source.size());
This seems to be the only place in this file where `putAll` is called on a
non-empty map, so maybe preserve that and adjust the assertions to match.
It's kind of a shortcut to use the entryset for this, and in principle perhaps
one ought to use `containsKey` and `get` for testing individual keys and
values. But if `putAll` is broken, the map's entryset is probably also broken
and this will catch it.
The source map can be of any type, not HashMap, so might as well use `Map.of()`
to create the source.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line 43:
> 41: * The setup poisons polymorphic call sites by using five different map
> types
> 42: * in both the constructor and manual iteration patterns to ensure
> megamorphic behavior.
> 43: */
Might be useful to reference the HashMap bug report JDK-8371656 and the more
general issue with megamorphic callsites JDK-8368292 so that the discusions are
all linked.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line
113:
> 111: @SuppressWarnings("unchecked")
> 112: Map<BigInteger, Integer>[] sources = new Map[] { inputHashMap,
> inputTreeMap, inputLinkedHashMap,
> 113: inputConcurrentHashMap, inputWeakHashMap };
Might be a bit nicer to use List.of() here instead of an array.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line
120:
> 118: HashMap<BigInteger, Integer> temp = new HashMap<>(source);
> 119: if (temp.size() != mapSize)
> 120: throw new RuntimeException();
Interesting. It looks like test code here... but why? After pondering this a
bit I imagine that simply storing the new HashMap into a local and then
overwriting it on the next loop might result in the JIT compiler eliminating a
bunch of dead code, so adding the if-statement and the size check might defeat
this. But I'm kind of guessing here. A comment would be useful; or, perhaps
there's away to prevent the compiler from doing this? Use a blackhole? Kind of
strange to do this in setup code, but maybe it's appropriate.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line
126:
> 124: for (int i = 0; i < POISON_ITERATIONS; i++) {
> 125: Map<BigInteger, Integer> source = sources[i %
> sources.length];
> 126: HashMap<BigInteger, Integer> temp = new
> HashMap<>(source.size());
The argument is the HashMap's _capacity_ (table size) not the number of entries
it can store, so when the map is populated it will end up doing a resize and
rehash. Maybe not significant here, since this isn't the benchmark, but it
might generate some garbage that needs to be collected later. Suggest using
`HashMap.newHashMap(int)`.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line
158:
> 156: }
> 157: if (temp.size() != mapSize) throw new RuntimeException();
> 158: }
These loops are the same as the ones above, except that they're poisoning call
sites in different argument classes, right? Maybe they can be combined with the
above. Might need to adjust POISON_ITERATIONS accordingly. Not a big deal, but
it makes the poisoning process seem twice as complex as it actually is.
test/micro/org/openjdk/bench/java/util/HashMapConstructorBenchmark.java line
176:
> 174: @Benchmark
> 175: public HashMap<BigInteger, Integer> manualEntrySetLoop() {
> 176: HashMap<BigInteger, Integer> result = new HashMap<>();
Here, the HashMap isn't pre-sized, so this will cause resizing the map during
the middle of the loop, which does allocation and copying. Again, I'd suggest
using `HashMap.newHashMap()` here.
-------------
PR Review: https://git.openjdk.org/jdk/pull/28243#pullrequestreview-4145174567
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115163210
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115203578
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115345498
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115357502
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115392360
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115411160
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115423300
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115435437
PR Review Comment: https://git.openjdk.org/jdk/pull/28243#discussion_r3115447499
