Thank you for having a look, Doug.
Comments inline...
On 5/23/13 5:20 AM, Doug Lea wrote:
* Given that balanced trees are not used in WeakHashMap
or Hashtable, I wonder why the TreeNode etc classes are
not just nested inside HashMap (usable from subclass LinkedHashMap).
And if so, it would be simpler, faster, and less code-intensive
to declare TreeNode as a subclass of the internal Entry class.
Plus some further gymnastics to overcome the unfortunate
decision to make LinkedHashMap a subclass of HashMap.
Had you considered this?
I definitely did. I wanted a cleaner class hierarchy for
Entry/TreeNode, but LinkedHashMap makes it difficult, since its Entries
need extra before/after references.
I couldn't work out a TreeNode class that could be used by both HashMap
and LinkedHashMap, since LHM would need a TreeNode derived from
LinkedHashMap.Entry, not HashMap.Entry.
So instead I used composition, where TreeNode has-a [Linked]HashMap.Entry.
* The comparableClassFor code turns out to be a bottleneck
(and is bypassed in the particular case of String)
in tests of the analogous code in ConcurrentHashMap, mainly
because the only available reflection methods allocate little
objects while checking for the form "class C implements Comparable<C>"
At some point, someone might want to implement a JDK-internal
streamlined form.
OK
* Notice that if trees were ever to be used in WeakHashMap,
the nodes would surely need to be declared as WeakReference
subclasses, as are the current Entry nodes.
Full-disclosure: I did have a working version of WeakHashMap with
balanced trees. Here again, composition helped: TreeNode has-a
WeakReference instead of being-a WeakReference. But guaranteeing that
TreeBin was protected from encountering null/cleared keys took some
contortions. In the end, the extra complexity wasn't worth it, so it's
not included.
The whole thought
of doing this though is suspect (so I'm happy to see it
not being done)
Glad to hear that taking it out was the right move. :)
Thanks,
-Brent
On 05/22/13 16:50, Brent Christian wrote:
I have updated the changes as follows:
* TreeBin.createEntryForNode() + the anonymous TreeBin subclass in
[Linked]HashMap have been replaced by a TreeBin.map reference back to the
containing map, enabling TreeBin to just call newEntry() directly.
* TreeNode.entry was made final
* Added a top-level comment in HashMap giving a brief overview of how
balanced
trees are used
* Updated the TreeBinSplitBackToEntries test for TREE_THRESHOLD=16
* Test code was updated to not need to be on the bootclasspath.
LaunchOnBootClass.java was removed from the changes (and would not
have been
needed anyway, due to the recent jtreg update)
The new webrev is here:
http://cr.openjdk.java.net/~bchristi/8005698/webrev.01/
Thanks,
-Brent
On 5/13/13 9:48 AM, Brent Christian wrote:
Hi,
Please review my changes for 8005698 : Handle Frequent HashMap
Collisions with Balanced Trees.
For HashMap and LinkedHashMap, we would like to duplicate the technique
(and some of the code) that the latest ConcurrentHashMap[1] uses for
handling hash collisions: use of balanced trees to store map entries in
hash bins containing many collisions.
Webrev is here:
http://cr.openjdk.java.net/~bchristi/8005698/webrev.00/
Some high-level details copied from the JEP[2]:
Earlier work in this area in JDK 8, namely the alternative
string-hashing implementation[3], improved collision performance for
string-valued keys only, and it did so at the cost of adding a new
(private) field to every String instance.
The changes proposed here will improve collision performance for any key
type that implements Comparable. The alternative string-hashing
mechanism, including the private hash32 field added to the String class,
can then be removed.
The principal idea is that once the number of items in a hash bucket
grows beyond a certain threshold, that bucket will switch from using a
linked list of entries to a balanced tree.
We will not implement this for the Hashtable class - some legacy code
that uses it is known to depend upon iteration order. Instead, Hashtable
will be reverted to its state prior to the introduction of the
alternative string-hashing implementation, and will maintain its
historical iteration order.
We also will not implement this technique in WeakHashMap. An attempt was
made, but the complexity of having to account for weak keys resulted in
an unacceptable drop in microbenchmark performance. WeakHashMap will
also be reverted to its prior state.
Thanks!
-Brent
1.
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java?view=log
2. http://openjdk.java.net/jeps/180
3. http://hg.openjdk.java.net/jdk8/jdk8/jdk/rev/43bd5ee0205e
