This is an "exploratory" CR.
As part of 6977804 (G1: remove the zero-filling thread) and 6949241 (G1: restructure region lists in G1) all the free regions in G1 will be managed as a singly-linked list. This makes the two most common operations:
- allocate free region
- concatenate two free lists
very fast and constant time. However, it also has two disadvantages:
- It's hard / expensive to keep the free list sorted in address order. So, if we want to try to allocate free regions at the bottom of the heap in favor of free regions at the top of the heap (e.g., in case we want to shrink the heap without a Full GC), it's not really easy to do that.
- When we want to allocate a set of contiguous regions to satisfy a humongous allocation request removing those regions from the free list typically involves a linear scan of the list and the removal of each of the regions we would like to allocate one at a time until all are removed.
It might be worthwhile exploring different ways of managing the free regions to address the two issues above (either or both). Possible alternatives include:
- Using a doubly-linked list will allow us to be able to remove individual regions in constant time, so it will avoid the linear scan that we do when allocating humongous regions.
- Using a bitmap to keep track of which regions are free or not might be a good alternative to using a free list. By default it would allow us to allocate regions in address order if we need to and would make finding and freeing a contiguous set of free regions trivial. Freeing a single region will be a bit more expensive (in the worst case we'll have to do a full bitmap sweep), ditto for the concatenation operation (or the two bitmaps together). But maybe those two operations can be speeded up in practice if we maintain some extra metadata (i.e., first / last free region that we've freed) to minimize which parts of the bitmap we'll have to look at.