RFR: 8333658: NMT: Use an allocator with 4-byte pointers to save memory in NativeCallStackStorage [v18]

[Thomas Stuefe]

On Thu, 13 Jun 2024 21:02:33 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> Hi,
>> 
>> This PR introduces a new allocator, `IndexedFreelistAllocator`. It uses a `GrowableArray` in order to have 4-byte "pointers" to its elements and also works as a freelist as unused slots form a linked list. This allocator cannot shrink its used memory. I'm always open for better names.
>> 
>> We then use this allocator in order to store the `NativeCallStackStorage` hash table. This saves `4 * 4099 = ~16KiB` of memory as each table element is now only 4 bytes. For each stored stack it also saves 4 bytes. The fact that the allocator cannot shrink is fine, we do not ever remove stacks from the storage.
>> 
>> The main point of this is to introduce a pointer-generic experimential API, so I also implemented CHeap and Arena allocators. It's currently placed in NMT, but we might want to move it into utilities. It uses a bit of template-magic, but my IDE (Emacs+clangd) was actually able to figure things out when the types didn't line up correctly etc, so it's not an enemy to IDE help.
>> 
>> It sounded expensive to have the GrowableArray continously realloc its underlying data array, so I did a basic test where we allocate 1 000 000 stacks and push them into NativeCallStackStorage backed by different allocators. This is available in the PR.
>> 
>> The results are as follows on linux-x64-slowdebug:
>> 
>> 
>> Generate stacks... Done
>> Time taken with GrowableArray: 8341.240945
>> Time taken with CHeap: 12189.031318
>> Time taken with Arena: 8800.703092
>> Time taken with GrowableArray again: 8295.508829
>> 
>> 
>> And on linux-x64:
>> 
>> 
>> Time taken with GrowableArray: 8378.018135
>> Time taken with CHeap: 12437.347868
>> Time taken with Arena: 8758.064717
>> Time taken with GrowableArray again: 8391.076291
>> 
>> 
>> Obviously, this is a very basic benchmark, but it seems like we're faster than CHeap and Arena for this case.
>
> Johan Sjölen has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Remove dead CHeap allocator test

More comments. Thanks for taking my suggestions.

We need a little gtest for this.

src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 62:

> 60:   I allocate(Args... args) {
> 61:     BackingElement* be;
> 62:     int i;

I i? Then, later, just return i?

src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 79:

> 77: 
> 78:   void free(I i) {
> 79:     assert(i != nil || (i > 0 && i < _backing_storage.length()), "out of bounds free");

I think there are some errors here. This is probably broken. Which we would see if the gtests were running, but hotspot common tier1 tests seem broken.

Do we allow passing in nil? Then, i must be either nil or valid, not != nil or valid. If not, use an AND, not an OR.
i=0 is valid
Could you also please factor out OOB test for i?

src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 80:

> 78:   void free(I i) {
> 79:     assert(i != nil || (i > 0 && i < _backing_storage.length()), "out of bounds free");
> 80:     if (i != nil) return;

i == nil?

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

PR Review: https://git.openjdk.org/jdk/pull/18979#pullrequestreview-2120237393
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1640814246
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1640820200
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1640820299