RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Brent Christian]

Updated webrev is here:
http://cr.openjdk.java.net/~bchristi/8005698/webrev.03/

It contains the following changes from Mike's review:

* HashMap.comparableClassFor(): corrected reference to TreeBin docs

* fixed @run tag in InPlaceOpsCollisions.java

* Hashtable & HashMap: hashSeed made final, initialized in constructor, 
UNSAFE restored and used in readObject().

Thanks,
-Brent

On 5/29/13 11:39 AM, Brent Christian wrote:
> On 5/28/13 9:13 PM, Mike Duigou wrote:
>> Hashtable/WeakHashMap::
>>
>> - I assume that the JVM falls over dead if the security manager
>> doesn't allow access to the property, correct? I hadn't considered
>> what should happen in the event of a security exception when I
>> originally copied the GetPropertyAction idiom from elsewhere in the
>> JDK.
>
> AFAIK a security exception won't happen here as it's called in a
> doPrivileged().
>
>> Perhaps add a security manager test to CheckRandomHashSeed?
>> Or two if we want to make sure that
>
> ...that what? :)
>
> I ran a test to confirm that maps can be created when useRandomSeed=true
> and a security manager is running (-Djava.security.manager).  Attempting
> to read the property from the test code throws an
> AccessControlException, as one would expect.
>
> CheckRandomHashSeed probably isn't the right place to test this, as the
> test itself requires permissions to read the property and confirm (via
> reflection) the value of the hash seed.  But I can add a new test case,
> if you think it's important.
>
>> - initHashSeed could now return the value with assignment happening
>> in the constructor if we wanted to make hashSeed final. This would
>> mean the unsafe stuff would have to return in Hashtable/HashMap to
>> allow for deserialization.
>
> It would be nice to keep hashSeed final.  It would no longer be lazy,
> but we'll still get the main bottleneck relief of 8006593 by using
> ThreadLocalRandom in sun.misc.Hashing.
>
> I'll work on this.
>
>> HashMap::
>>
>> - TreeBin.comparableClassFor() includes "see above for explanation."
>> but it's not clear where that explanation is.
>
> Things got moved around - its referring to the TreeBin docs, which are
> now "below".  Fixed.
>
>> Hashing::
>>
>> - Do we know if ThreadLocalRandom requires that the VM be booted? It
>> may be possible to remove even more stuff here.
>
> Indeed.  I don't know the answer.
>
>
>> InPlaceOpsCollisions::
>>
>> - The @run directives run the wrong class (an error I have made
>> myself...).
>
> Dang!  Thanks - fixed.
>
>
> -Brent
>
>> On May 28 2013, at 13:03 , Brent Christian wrote: >
>>> On 5/28/13 3:09 AM, Doug Lea wrote:
>>>>
>>>> To better enable and simplify future improvements, could you
>>>> do this -- nest the tree classes within HashMap?
>>>
>>> Done.
>>>
>>>> Also, a note on spliterators: I had added these in the
>>>> least disruptive way (knowing that major changes were coming)
>>>> by checking exact class match for HashMap.class. This is because
>>>> there aren't LinkedHashMap view classes to attach overrides to.
>>>> While not wrong, and OK for now, at some point this should be redone.
>>>
>>> OK.  I will file a bug so this doesn't get forgotten.
>>>
>>>
>>> I also applied the change to how HashMap.putAll() resizes the table
>>> (to account for splitTreeBin() only handling doubling of tables).
>>>
>>> The updated webrev is here:
>>>
>>> http://cr.openjdk.java.net/~bchristi/8005698/webrev.02/
>>>
>>> Thanks,
>>> -Brent
>>