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

[Johan Sjölen]

On Fri, 26 Apr 2024 14:29:53 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.

Thanks Thomas! Sorry for the messy code, I felt that it was in good enough shape to show people and see what they think. I'll clean it up and ping you when it's ready. I answered some of your comments also.

/ Johan

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

PR Review: https://git.openjdk.org/jdk/pull/18979#pullrequestreview-2102280016