RFR: 8269004 Implement ResizableResourceHashtable [v4]

[Kim Barrett]

On Tue, 29 Jun 2021 21:04:37 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:
> 
>   @coleenp comments

Mostly good, but a few minor nits.

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

> 78: 
> 79:   Node const** lookup_node(unsigned hash, K const& key) const {
> 80:     return const_cast<Node const**>(

[pre-existing] I think this `const_cast` to add const is unnecessary.

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

> 86: 
> 87:  public:
> 88:   ResourceHashtableBase() : _number_of_entries(0) {}

I'd prefer this explicitly initialize STORAGE, e.g. add `STORAGE()` to value-initialize rather than default-initialize it.  (I think it doesn't currently make a difference, but I think being explicit is clearer.)

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

> 88:   ResourceHashtableBase() : _number_of_entries(0) {}
> 89: 
> 90:   ResourceHashtableBase(unsigned size) : STORAGE(size), _number_of_entries(0) {}

These constructors seem like they should be non-public.

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

> 90:   ResourceHashtableBase(unsigned size) : STORAGE(size), _number_of_entries(0) {}
> 91: 
> 92:   ~ResourceHashtableBase() {

Base class constructor should be non-public to avoid slicing.  Also need to decide what to do about copying, either disallow or deep copy.  Default shallow copy seems likely to be wrong.

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

> 220: protected:
> 221:   FixedResourceHashtableStorage() {
> 222:     memset(_table, 0, TABLE_SIZE * sizeof(Node*));

Instead of memset, consider `FixedResourceHashtableStorage() : _table{} {}`.

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

> 222:     memset(_table, 0, TABLE_SIZE * sizeof(Node*));
> 223:   }
> 224: 

Destructor should be non-public to prevent slicing.  Also need to consider what to do about copying.

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

Changes requested by kbarrett (Reviewer).

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