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

[Johan Sjölen]

On Thu, 6 Jun 2024 12:46:20 GMT, Thomas Stuefe <stuefe 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.
>
> src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 38:
> 
>> 36:     BackingElement(E& e) {
>> 37:       this->e = e;
>> 38:     }
> 
> What would be cool is for this data structure to work with any E without requiring E to implement default- and copy-constructors. E.g. an E with a mandatory const member and a single constructor that inits that member.
> 
> Maybe we could do that by not storing E but making sure there is enough space for E, like this:
> 
> 
> union BackingElement {
>     I link;
>     char x[sizeof(E)];
> };
> 
> 
> Then use x and placement new, which you do already.
> 
> sizeof(E) would also account for intra-array padding needed to guarantee E alignment. All we need to make sure then is to align the start pointer of the first BackingElement, but since that one is malloced from C-heap, its already aligned.
> 
> And I think we don't really need any constructors here.
> 
> Also, please remove unnecessary this->. Please use initializer lists.

That's a good idea. It probably should be:

```c++
union alignas(E) BackingElement  {
  I link;
  char e[sizeof(E)];
};

> src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 71:
> 
>> 69:   E& operator[](I i) {
>> 70:     return backing_storage.at(i.idx).e;
>> 71:   }
> 
> Do we need this?

It's nice when your other operation is called `translate`, maybe not as nice when it's called `at`.

> src/hotspot/share/nmt/indexedFreeListAllocator.hpp line 77:
> 
>> 75:   }
>> 76: };
>> 77: 
> 
> What are these allocators for?

So you can easily swap out your allocator if you have a bug and want to ensure the bug isn't in your allocator. Also just completeness, and necessary for the performance tests. We can remove them, but I think they're nice to have.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629735033
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629743150
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629745072