Integrated: 8300184: Optimize ResourceHashtableBase::iterate_all using _number_of_entries

[Xin Liu]

On Mon, 16 Jan 2023 19:50:37 GMT, Xin Liu <xliu at openjdk.org> wrote:

> Current implementation needs to visit all buckets. In extreme case, an empty hashtable with 1k buckets. iterate_all() loads 1k buckets for nothing. `_number_of_entries` is the number of nodes in the hashtable. This patch leverages that to quit iteration earlier. The real effect is up to the distribution of nodes among buckets.
> 
> I also included a debug log in the original patch. It was used for the observation in the following section, but I deleted it because it introduces circular dependency. 
> 
> log_debug(hashtables)("ResourceHashtableBase table_size = %d, break at " INTX_FORMAT, sz, (bucket - table()));
> 
> **Evaluation** 
> In release build, the patch is very marginal. class loading do use ResourceHashtable but they are saturated. 
> 
> I use it to run `Renaissance/finagle-http`. hahstable iterate_all quits a little bit earlier and save some loads. eg. in line 2, there are 109 buckets in the hashable. the iteration quit at 68th bucket, we save 42 loads. 
> 
> 
> $java -Xlog:hashtables=debug  -jar renaissance-gpl-0.14.1.jar finagle-http
> ...
> [12.824s][debug][hashtables] table_size = 109, break at 109
> [12.824s][debug][hashtables] table_size = 109, break at 68
> [12.824s][debug][hashtables] table_size = 109, break at 107
> [12.825s][debug][hashtables] table_size = 109, break at 108
> [12.825s][debug][hashtables] table_size = 109, break at 99
> [12.825s][debug][hashtables] table_size = 109, break at 108
> [12.825s][debug][hashtables] table_size = 109, break at 98
> [12.825s][debug][hashtables] table_size = 109, break at 109
> [12.825s][debug][hashtables] table_size = 109, break at 102
> ...
> 
> 
> Another application is in AsyncLog Thread. We have a hashtable with 17 buckets. Each Log Output creates one node in the hashtable. In common cases, there are only 2~3 nodes in the hashtable. Each time AsyncLog Thread flushes the buffer, it has to scan the hashtable twice. Saving loads means saving the memory bandwidth for the application. 
> 
> In fastdebug build, extra verification is deployed. It's common to observe that JVM scan an empty hashtable. It's in destroy_VM. 
>  
> 
> ./build/linux-x86_64-server-fastdebug/images/jdk/bin/java -Xlog:hashtables=debug --version
> openjdk 21-internal 2023-09-19
> OpenJDK Runtime Environment (fastdebug build 21-internal-adhoc.xxinliu.jdk)
> OpenJDK 64-Bit Server VM (fastdebug build 21-internal-adhoc.xxinliu.jdk, mixed mode, sharing)
> [0.130s][debug][hashtables] table_size = 139, break at 0
> [0.136s][debug][hashtables] table_size = 107, break at 0
> [0.136s][debug][hashtables] table_size = 1009, break at 0
> [0.136s][debug][hashtables] table_size = 109, break at 107
> [0.136s][debug][hashtables] table_size = 109, break at 109
> [0.137s][debug][hashtables] table_size = 109, break at 101

This pull request has now been integrated.

Changeset: 0b9ff06f
Author:    Xin Liu <xliu at openjdk.org>
URL:       https://git.openjdk.org/jdk/commit/0b9ff06f3a72d26d64cdc43f9991005bba2aedba
Stats:     5 lines in 1 file changed: 3 ins; 0 del; 2 mod

8300184: Optimize ResourceHashtableBase::iterate_all using _number_of_entries

Reviewed-by: dholmes, rehn

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

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