RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees

[Brent Christian]

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
>