Hi Stuart,
The implNote compares the performance impact without mentioning
that HashMap uses 'equals()' vs '==' which might have as big an impact
on performance as sequential vs chained references.
Detailed performance comparisons are very difficult given the factors
that impact performance, cache sizes, data structure sizes, etc.
I'm not sure the wordsmithing adds much to the doc.
"JRE" -> "Java"
$.02, Roger
On 2/10/20 7:09 PM, Stuart Marks wrote:
On 2/10/20 7:52 AM, Martin Buchholz wrote:
On Fri, Feb 7, 2020 at 2:47 PM David Holmes <david.hol...@oracle.com>
wrote:
Hi Martin,
On 8/02/2020 3:10 am, Martin Buchholz wrote:
I explored System.identityHashCode (see below).
System.identityHashCode is a VM call that is potentially very
expensive.
In the worst-case it triggers monitor inflation.
I can believe that. The VM can't simply return the address of an object
because ... the object might move and an address is a poor hash code
because low bits will tend to be zero.
But IdentityHashMap already calls System.identityHashCode - that price
must be paid.
My proposal is still "Let's trust System.identityHashCode to produce
acceptable hash codes"
OK... I appreciate that there are a bunch of subtle issues here, from
whether it's necessary to do mixing of the identity hash code to
whether an open-addressed table really is faster than separate
chaining in this case. Before we go on too long, though, I'd like to
ask what to do about my proposed comments changes.
Should I proceed with pushing my comments changes (which I've appended
below for convenience)? Or is somebody going to dive in right away and
make changes that will invalidate my proposed comments changes, and
thus I should hold off pushing them?
Thanks,
s'marks
# HG changeset patch
# User smarks
# Date 1580167577 28800
# Mon Jan 27 15:26:17 2020 -0800
# Node ID 0e08ce23484ca42597105225ffa3dd0827cb4b60
# Parent 981f6982717a7df4a2a43dd0ae6b2c2389e683f9
8046362: IdentityHashMap.hash comments should be clarified
Reviewed-by: XXX
diff -r 981f6982717a -r 0e08ce23484c
src/java.base/share/classes/java/util/IdentityHashMap.java
--- a/src/java.base/share/classes/java/util/IdentityHashMap.java Mon
Jan 27 14:03:58 2020 -0800
+++ b/src/java.base/share/classes/java/util/IdentityHashMap.java Mon
Jan 27 15:26:17 2020 -0800
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000, 2019, Oracle and/or its affiliates. All rights
reserved.
+ * Copyright (c) 2000, 2020, Oracle and/or its affiliates. All rights
reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -115,17 +115,19 @@
* exception for its correctness: <i>fail-fast iterators should be
used only
* to detect bugs.</i>
*
- * <p>Implementation note: This is a simple <i>linear-probe</i> hash
table,
- * as described for example in texts by Sedgewick and Knuth. The array
- * alternates holding keys and values. (This has better locality for
large
- * tables than does using separate arrays.) For many JRE
implementations
- * and operation mixes, this class will yield better performance than
- * {@link HashMap} (which uses <i>chaining</i> rather than
linear-probing).
- *
* <p>This class is a member of the
* <a
href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
* Java Collections Framework</a>.
*
+ * @implNote
+ * <p>This is a simple <i>linear-probe</i> hash table,
+ * as described for example in texts by Sedgewick and Knuth. The array
+ * contains alternating keys and values, with keys at even indexes
and values
+ * at odd indexes. (This arrangement has better locality for large
+ * tables than does using separate arrays.) For many JRE
implementations
+ * and operation mixes, this class will yield better performance than
+ * {@link HashMap}, which uses <i>chaining</i> rather than
linear-probing.
+ *
* @see System#identityHashCode(Object)
* @see Object#hashCode()
* @see Collection
@@ -293,7 +295,7 @@
*/
private static int hash(Object x, int length) {
int h = System.identityHashCode(x);
- // Multiply by -127, and left-shift to use least bit as part
of hash
+ // Multiply by -254 to use the hash LSB and to ensure index
is even
return ((h << 1) - (h << 8)) & (length - 1);
}
