Hi, similar to JDK-8244960[1] that I reported last week, I noticed that HashMap & LinkedHashMap could benefit from a similar improvement.
I used the following benchmark again to validate the results: @BenchmarkMode(Mode.AverageTime) @OutputTimeUnit(TimeUnit.NANOSECONDS) public class MyBenchmark { @State(Scope.Benchmark) public static class ThreadState { private Map<TestKey, String> map = new HashMap<>(); private TestKey key = new TestKey(Collections.singleton("test")); /* public ThreadState() { this.map.put(key, "test"); } */ } @Benchmark public String test(ThreadState threadState) { return threadState.map.get(threadState.key); } } Where TestKey is the following: public class TestKey { private final Set<String> params; public TestKey(Set<String> params) { this.params = params; } @Override public int hashCode() { return this.params.hashCode(); } } Applying the (hopefully) attached patch I see the following results: Patched Benchmark Mode Cnt Score Error Units MyBenchmark.test avgt 10 2,717 ± 0,247 ns/op MyBenchmark.test:·gc.alloc.rate avgt 10 ≈ 10⁻⁴ MB/sec MyBenchmark.test:·gc.alloc.rate.norm avgt 10 ≈ 10⁻⁶ B/op MyBenchmark.test:·gc.count avgt 10 ≈ 0 counts Old Benchmark Mode Cnt Score Error Units MyBenchmark.test avgt 10 3,713 ± 0,091 ns/op MyBenchmark.test:·gc.alloc.rate avgt 10 ≈ 10⁻⁴ MB/sec MyBenchmark.test:·gc.alloc.rate.norm avgt 10 ≈ 10⁻⁶ B/op MyBenchmark.test:·gc.count avgt 10 ≈ 0 counts The case when the map is already filled didn't seem to show any regression. Unfortunately, there is the caveat of potentially executing the hash() method twice in computeIfPresent if the remapping function returns null and the node is removed. I don't know if this case is really common (or more common than an empty map), but I should mention it for completeness reasons. One common case for the above scenario is the following: I noticed that in a typical Spring-Boot app Manifest.getTrustedAttributes or Manifest.getEntries() is actually empty. Since this is used during class loading it is executed relatively frequent. I could imagine other use-cases where this might be benefitial for startup scenarios. In case you think this is worthwhile, I would highly appreciate a sponsoring of the attached patch. Cheers, Christoph [1] https://bugs.openjdk.java.net/browse/JDK-8244960
diff -r f143729ca00e src/java.base/share/classes/java/util/HashMap.java --- a/src/java.base/share/classes/java/util/HashMap.java Wed May 13 16:18:16 2020 +0200 +++ b/src/java.base/share/classes/java/util/HashMap.java Tue May 19 14:10:33 2020 +0200 @@ -555,20 +555,19 @@ */ public V get(Object key) { Node<K,V> e; - return (e = getNode(hash(key), key)) == null ? null : e.value; + return (e = getNode(key)) == null ? null : e.value; } /** * Implements Map.get and related methods. * - * @param hash hash for key * @param key the key * @return the node, or null if none */ - final Node<K,V> getNode(int hash, Object key) { - Node<K,V>[] tab; Node<K,V> first, e; int n; K k; + final Node<K,V> getNode(Object key) { + Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k; if ((tab = table) != null && (n = tab.length) > 0 && - (first = tab[(n - 1) & hash]) != null) { + (first = tab[(n - 1) & (hash = hash(key))]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; @@ -594,7 +593,7 @@ * key. */ public boolean containsKey(Object key) { - return getNode(hash(key), key) != null; + return getNode(key) != null; } /** @@ -1105,7 +1104,7 @@ return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); - Node<K,V> candidate = getNode(hash(key), key); + Node<K,V> candidate = getNode(key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { @@ -1141,7 +1140,7 @@ @Override public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; - return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; + return (e = getNode(key)) == null ? defaultValue : e.value; } @Override @@ -1157,7 +1156,7 @@ @Override public boolean replace(K key, V oldValue, V newValue) { Node<K,V> e; V v; - if ((e = getNode(hash(key), key)) != null && + if ((e = getNode(key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) { e.value = newValue; afterNodeAccess(e); @@ -1169,7 +1168,7 @@ @Override public V replace(K key, V value) { Node<K,V> e; - if ((e = getNode(hash(key), key)) != null) { + if ((e = getNode(key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); @@ -1260,8 +1259,7 @@ if (remappingFunction == null) throw new NullPointerException(); Node<K,V> e; V oldValue; - int hash = hash(key); - if ((e = getNode(hash, key)) != null && + if ((e = getNode(key)) != null && (oldValue = e.value) != null) { int mc = modCount; V v = remappingFunction.apply(key, oldValue); @@ -1271,8 +1269,10 @@ afterNodeAccess(e); return v; } - else + else { + int hash = hash(key); removeNode(hash, key, null, false, true); + } } return null; } diff -r f143729ca00e src/java.base/share/classes/java/util/LinkedHashMap.java --- a/src/java.base/share/classes/java/util/LinkedHashMap.java Wed May 13 16:18:16 2020 +0200 +++ b/src/java.base/share/classes/java/util/LinkedHashMap.java Tue May 19 14:10:33 2020 +0200 @@ -438,7 +438,7 @@ */ public V get(Object key) { Node<K,V> e; - if ((e = getNode(hash(key), key)) == null) + if ((e = getNode(key)) == null) return null; if (accessOrder) afterNodeAccess(e); @@ -450,7 +450,7 @@ */ public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; - if ((e = getNode(hash(key), key)) == null) + if ((e = getNode(key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); @@ -685,7 +685,7 @@ return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); - Node<K,V> candidate = getNode(hash(key), key); + Node<K,V> candidate = getNode(key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) {