On 08/21/2013 02:25 PM, Paul Sandoz wrote:
Hi,
Here are Doug's Linked/HashMap changes, discussed in a previous thread, as a
webrev:
http://cr.openjdk.java.net/~psandoz/tl/JDK-8023463-Linked-HashMap-bin-and-tree/webrev/
I also added some tests related to characteristics associated with fixing
another bug.
Looking at the diffs will be tricky given there are so many changes.
The code can be simplified a little bit by using the diamond syntax,
HashMap (lines: 919, 963, 1026, 1497, 1569) and
LinkedHashMap (lines: 255, 264, 270, 278)
There are a bunch of @Override that are missing making the code harder
than it should to read.
HashMapSpliterator.est should be renamed to estimateSize.
All occurences of "(n - 1) & hash" should be replaced by "hash & (n -
1)" because it's easier to explain.
TreeNode.getTreeNode() should be a static method and take a Node<K,V> as
first argument,
so most of the casts to TreeNode<K,V> that bother you will disappear :)
static TreeNode<K,V> getTreeNode(Node<K,V> node, int h, Object k) {
TreeNode<K,V> first = (TreeNode<K,V)node;
return ((first.parent != null) ? first.root() : firt).find(h, k, null);
}
In putVal, line 654, the null check (e != null) makes the method hard to
read,
at least I think a comment saying that it means that an existing node
need to be altered is needed.
And I still don't like the way the method clone() is implemented (the
older implementation has the same issue),
result should not be initialized to null and the catch clause should
thow an InternalError or an AssertionError,
Taking a look to the generated assemblies for HashMap.get(), there are
three differences,
1) the old implementation and the new implementation both have a
shortcut to return null,
but the condition is slightly different, the old implementation
test if size == 0 while
the new one test if arraylength <= 0.
So the new implementation use less load but at the price of a less
general condition.
2) the new implementation do a lot of less bits twiddling on the
hashCode value
3) the old implementation use an array of Object and not an array of
Node, so
there is a supplementary fast checkcast.
apart that the whole code is identical, so the introduction of the tree
implementation has
no runtime cost if the tree is not needed.
For HashMap.put, the new implementation has no runtime cost too and does
fewer loads
because the code of the old implementation was written in the stupid way
(the field 'table' has to be loaded several times by example).
so the code is clearly an improvement compared to the previous versions
in term of 'assembly beauty' :)
I fixed unchecked warnings in LinkedHashMap, but have not done so for HashMap,
where there are many more casts from Node to TreeNode. One way to solve that is
with a static method:
@SuppressWarnings("unchecked")
static <K, V> TreeNode<K, V> asTreeNode(Node<K, V> n) {
return (TreeNode<K, V>) n;
}
but i dunno what the performance implications are. Perhaps it's best to simply
stuff @SuppressWarnings on methods of TreeNode rather than trying to modify
code just for the sake of reducing the scope.
You should not need the @SuppressWarnings here?
A JPRT job has been kicked off.
I recommend when this code goes in we look closely at code coverage results to
see if we are missing areas testing tree functionality and update/add new tests
accordingly.
Paul.
cheers,
Rémi
