RFR: 8301136: Improve unlink() and unlink_all() of ResourceHashtableBase [v5]

[Xin Liu]

On Sun, 29 Jan 2023 06:41:10 GMT, Ioi Lam <iklam at openjdk.org> wrote:

>> Xin Liu has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Add lambda API unlink(Function f) per reviewers' request.
>
> I updated [JDK-8301296](https://bugs.openjdk.org/browse/JDK-8301296) to clarify the problems with the current ResourceHashtable design and my proposal for fixing them.
> 
> I think the above proposed fixes shouldn't block the progress of this PR, which is just an optimization that maintains the current behavior. So let's continue the discussions here.
> 
> There are two parts of this PR:
> 
> [1] For the optimization (counting the number of entries and exit the loop early), do you have any performance data that shows this is beneficial?
> 
> For this optimization to be beneficial, we must have two conditions -- (a) the table is too large so it's likely to have many unused entries, and (b) the hash function is bad so most of the unused entries are at the end of the table.
> 
> For (a), maybe it's better to change the table to ResizeableResourceHashtable?
> For (b), maybe you can also print out the occupancy of the table in your traces like this one (in your earlier PR https://github.com/openjdk/jdk/pull/12016)
> 
> 
> [12.824s][debug][hashtables] table_size = 109, break at 68
> 
> 
> If we have many entries (e.g., 40) but they all pack to the front end of the table, that means we have a bad hash function.
> 
> [2] As I suggested earlier, we should consolidate the code to use a single unlink loop, so you can apply this counting optimization in a single place. 
> 
> I am not quite sure why you would need the following in your "wrapper" functions:
> 
> 
> if (clean) {
>   *ptr = node->_next;
> } else {
>   ptr = &(node->_next);
> }
> 
> 
> and
> 
> 
> if (node->_next == nullptr) {
>   // nullify the bucket when reach the end of linked list.
>   *ptr = nullptr;
> }
> 
> 
> I wrote a version of the consolidated loop that's much simpler. It also aligns with the old code so the diff is more readable:
> 
> https://github.com/openjdk/jdk/compare/master...iklam:jdk:8301136-resource-hash-unlink-all-suggestion
> 
> Note that I have both `unlink_all()` and `unlink_all(Function function)`, that's because the current API allows the user function to do two things (a) check if the entry should be freed, (b) perform special clean up on the entry. So if you want to free all entries but need to perform special clean up, you'd call  `unlink_all(Function function)`.

hi, @iklam, 

I found that the dominating way to remove elements in resoureHashTable is its destructor. 
I ran some Renaissance benchmarks and observed the similar thing. 

In particular, it's very common to call destructor for an empty resourceHashtable. I think we should apply to the shortcut optimization in JDK-8300184 in the destructor. 



➜  jdk git:(JDK-8301136) ./build/linux-x86_64-server-release/images/jdk/bin/java -Xlog:hashtables=debug --version
[0.052s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.052s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.052s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.052s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.063s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.063s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.063s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.063s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.063s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.063s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.063s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.063s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.063s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.063s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.072s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.072s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
openjdk 21-internal 2023-09-19
OpenJDK Runtime Environment (build 21-internal-adhoc.xxinliu.jdk)
OpenJDK 64-Bit Server VM (build 21-internal-adhoc.xxinliu.jdk, mixed mode, sharing)
[0.073s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.073s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.073s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.073s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.073s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.073s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.073s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.073s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0
[0.073s][debug][hashtables] ResourceHashtableBase destructor: entries = 0
[0.073s][debug][hashtables] ResourceHashtableBase table_size = 1031, break at 0, removed = 0

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

PR: https://git.openjdk.org/jdk/pull/12213