RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees (original) (raw)
Peter Levart peter.levart at gmail.com
Sun May 26 11:02:15 UTC 2013
- Previous message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Next message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On 05/23/2013 09:02 PM, Brent Christian wrote:
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.
Hi Brent,
It's unfortunate, because composition increases memory footprint. Here's my attempt at merging HashMap.Entry with TreeNode into same object:
...this is a patch against your webrev.
Diamond inheritance is solved by making LinkedHashMap.Entry an interface and exposing get/set[Before,After] methods instead of before/after fields. The hierarchy is as follows:
class HashMap.Entry implements Map.Entry class TreeNode extends HashMap.Entry interface LinkedHashMap.Entry extends Map.Entry class LinkedHashMap.EntryImpl implements LinkedHashMap.Entry class LinkedHashMap.LinkedTreeNode extends TreeNode implements LinkedHashMap.Entry
I also added two factory methods to HashMap which are overriden in LinkedHashMap for constructing TreeNode/LinkedHashMap.LinkedTreeNode objects.
The TreeNode still contains the final 'entry' field, which is initialized to 'this' because there are a lot of references to it. These would have to be replaced in code, but would make the patch much larger and more difficult to grasp, so I left this exercise for later.
So what do you think? I know that with this patch, the access to before/after links in LinkedHashMap.Entry is not direct field access any more and goes through invokeinterface and can therefore be slower, because there are two implementing classes (LHM.EntryImpl and LHM.LinkedTreeNode). But on the other hand, the space savings can be noticeable if lots of buckets are transformed into TreeBins...
Regards, Peter
- Previous message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Next message: RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]