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

Thu Jun 6 14:15:46 UTC 2024

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.

Started looking at this. I like this.

The smaller beauty spot of your implementation is that by relying on GrowableHeapArray, we are bound to the size of its index type, which is int. So we will never be able to hold more than 2G-1 entries. I think thats okay for now though, and if not, its easy to change in GrowableArray.

A bigger beauty spot is that it needs explicit initialization for every member (IIUC). That feels just wasteful, especially in combination with the generous hard-coded power-of-2 growth of GrowableArray.

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

> 21:       return idx == other.idx;
> 22:     }
> 23:   };

Why so much code? Why not just typedef to uint32?

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

> 25:   // A free list allocator element is either a link to the next free space
> 26:   // Or an actual element.
> 27:   union BackingElement {

No need for this to be public

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.

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

> 39:   };
> 40:   GrowableArrayCHeap<BackingElement, flag> backing_storage;
> 41:   I free_start;

Please use underscore for membernames (like, everywhere :)

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

> 43:   IndexedFreeListAllocator()
> 44:   : backing_storage(8),
> 45:   free_start(I{0}) {}

weird indentation.

Also, please expose the init size to outside, possibly with a sensible default like your 8

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

> 56:       // Follow the link to the next free element
> 57:       free_start = be.link;
> 58:     }

This feels a bit uncommon and contrary to the normal linked list implementation. If possible, I would opt for a more traditional approach that is easier to understand and does not rely on at_grow (e.g. in case we want adapt this to some other form of backing storage).

e.g.

if (_freelist == -1) {
  allocate new slot   
} else {
  reuse slot at freelist
}

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

> 65:     be_freed.link = free_start;
> 66:     free_start = i;
> 67:   }

I don't think a free(index) is very useful. We need a free(E* e), that calculates I from &e. (Your one real world usage example, NativeCallStackStorage, conveniently never frees :=)

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?

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

> 73:   E& translate(I i) {
> 74:     return backing_storage.at(i.idx).e;
> 75:   }

- I'd just call this function "at" as we usually do.
- I also would provide a const variant that exposes const E&.
- Please assert for i to be correct (not nil, not oob)

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

> 75:   }
> 76: };
> 77: 

What are these allocators for?

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

PR Review: https://git.openjdk.org/jdk/pull/18979#pullrequestreview-2101843216
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629471631
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629574300
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629474658
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629567480
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629572647
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629622542
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629627129
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629576662
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629578280
PR Review Comment: https://git.openjdk.org/jdk/pull/18979#discussion_r1629637028