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

[Thomas Stuefe]

On Thu, 20 Jun 2024 13:06:38 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:
> 
>   Rename free to deallocate

src/hotspot/share/nmt/nmtNativeCallStackStorage.hpp line 74:

> 72:   using Allocator = HomogenousObjectArray<Link, mtNMT>;
> 73:   using LinkPtr = typename Allocator::I;
> 74:   LinkPtr nil() { return Allocator::nil; }

could we have some clearer names?

- Link -> TableEntry or Entry (since its entries of the hashtable)
- LinkPtr -> TableEntryIndex

Also, could you put all data members of NCCS here, please? It makes it easier to see the implementation. The big boys here are _table, hash table entry storage, and stack storage.

I don't think you need a nil(), at least not if you keep referring to Allocator::nil elsewhere. 

Btw, why do you prefer using over  typedef?

src/hotspot/share/nmt/nmtNativeCallStackStorage.hpp line 76:

> 74:   LinkPtr nil() { return Allocator::nil; }
> 75: 
> 76:   Allocator _allocator;

"Allocator" is misleading. An allocator is typically a thing that provides alloc() and free() for you, but does not maintain the storage for you, thats up to you. 

Proposal: Allocator -> TableEntryStorage or EntryStorage. _allocator = _entry_storage.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1647953473
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1647951546