RFR: 8269004 Implement ResizableResourceHashtable [v3]

[Coleen Phillimore]

On Tue, 29 Jun 2021 03:45:41 GMT, Ioi Lam <iklam at openjdk.org> wrote:

>> In HotSpot we have (at least) two hashtable designs in the C++ code:
>> 
>> - share/utilities/hashtable.hpp
>> - share/utilities/resourceHash.hpp
>> 
>> Of the two, the `ResourceHashtable` API is much cleaner and most new code has been written with it. However, one issue is that the `SIZE` of `ResourceHashtable` is a compile-time constant. This makes the hash-to-index computation very fast on x64 (gcc can avoid using the slow divq instruction for modulo). However, the downside is we cannot use `ResourceHashtable` when we need a hashtable whose size is determined at run time (and, optionally, resizeable).
>> 
>> This PR refactors `ResourceHashtable` into a base template class `ResourceHashtableBase`, whose `size()` function can be configured by a subclass to be either constant or runtime-configurable. 
>> 
>> Note: since we want to preserve the performance of `hash % SIZE`, we can't make `size()` a virtual function.
>> 
>> Preliminary benchmark shows that this refactoring has no impact on the performance of the constant `ResourceHashtable`. See https://github.com/iklam/tools/tree/main/bench/resourceHash:
>> 
>> *before*
>> ResourceHashtable: 2.70 sec
>> 
>> *after*
>> ResourceHashtable: 2.72 sec
>> ResizableResourceHashtable: 5.29 sec
>> 
>> To make sure `ResizableResourceHashtable` works, I rewrote some CDS code to use `ResizableResourceHashtable` instead of `KVHashtable`
>
> Ioi Lam has updated the pull request incrementally with one additional commit since the last revision:
> 
>   @kimbarrett feedback to move the storage code to a base class

The cross product of Resizeable/Fixed x CHeap/ResourceAllocated is something that makes this hard to get my head around.  Would you have a resizeable ResourceAllocated hashtable?
Something doesn't seem right.
We have ResourceHashtables with fixed sizes in the code, and there are a couple of cases that use the CHeap allocation, and they need resizing.  Maybe only have two choices to make things easier?  Lots of indirection makes this really challenging to see if it's correct.
It could be that you want the hashtable to be resource allocated but the elements are CHeap allocated.  Which table is that?  We had this discussion with GrowableArray and I believe we settled on that if the GrowableArray is CHeap allocated, all the elements are also.

src/hotspot/share/utilities/resizeableResourceHash.hpp line 127:

> 125:     }
> 126: 
> 127:     FREE_C_HEAP_ARRAY(Node*, old_table);

If you resource allocated old_table, this doesn't seem right.
It seems like the ResizeableHashtable should be a CHeapHashtable and it's always resizeable.
And the code either has a fixed size ResourceHashtable or a variable/resizeable CHeapHashtable.

src/hotspot/share/utilities/resourceHash.hpp line 246:

> 244:     K, V, HASH, EQUALS, ALLOC_TYPE, MEM_TYPE> {
> 245: public:
> 246:   ResourceHashtable() : ResourceHashtableBase<FixedResourceHashtableStorage<SIZE, K, V>, K, V, HASH, EQUALS, ALLOC_TYPE, MEM_TYPE>() {}

nit: can you break up this line after the V> ?

-------------

PR: https://git.openjdk.java.net/jdk/pull/4536