RFR 8023463 Update HashMap and LinkedHashMap to use bins/buckets or trees (red/black)

[Paul Sandoz]

On Aug 24, 2013, at 6:31 PM, Mike Duigou <mike.duigou at oracle.com> wrote:

> I will need to spend more time reviewing the HashMap/LinkedHashMap implementations but here are some initial comments.
> 

OK, thanks.


> Mike
> 
> HashMap::
> 
> - The "Sorry if you don't like..." comment can be omitted.
> 

Or we could tweak:

     * The concurrent-programming-like SSA-based coding style helps avoid aliasing errors
     * amid all of the twisty pointer operations.


> 
> SpliteratorCharacteristics::
> 
> - style comment : I always define my assertXXX in the (value, expected, message) form as well as the (value, expected). Being able to pass the test case name for message is often useful context. It is a little more boilerplate.
> 

That's a good point. I am terribely lazy about that aspect.


> - void assertNullComparator(Collection<?> c) {
> 210         assertNullComparator(c.spliterator());
> 211     }
> 
> intentionally throws NPE if c is null? Why not instead assertNull or assertNonNull?
> 

No, the collection c is never null, the comparator of the spliterator of the collection is asserted to be null.


> 
> MapBinToFromTreeTest::
> 
> - thank you for using "hg move" to preserve history. :-)
> 

That was a happy accident on my part :-)


> - I try to encourage @DataProvider methods to return Iterator<Object[]> rather than Object[][]. I haven't made an incremental data provider which generates cases in next() yet.... but I could someday.
> 
> - getCollector(), put(), remove() could all be static
> 

I don't have a strong preferences regarding the above. I may tweak the data provider since the logging does not identify the hash map implementation.


> - put(SIZE, m, (i, s) -> { }); could be put(SIZE, m, (i, s) -> { assertEquals(i + 1,s); }); or some other check in put that the construction was expected.
> 

Note that the reuse here is just a convenience to fill up the map. Also there is no real dependence that i + 1 = s. The only constraint is that there are up to but not including s elements, but we don't need to know about the order (and in fact we could add different orders later on as i suspect it might affect the tree shape).


> On Aug 21 2013, at 05:25 , 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.
>> 
>> 
>> 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.
> 
> Always a tough spot. I've favoured adding annotations to variables wherever possible but when it becomes necessary to suppress for entire methods it does feel like shot
> 
> The alternative approach of using a method would almost certainly be inlined and as a result would have little (if any) impact on performance.
> 
> I still lean towards suppressing on variables and then see what's left.
> 

It's kind of awkward, i already tried it and it seemed marginally oppressive in some cases. I should take another swing at it.

Paul.