Join GitHub today
GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.Sign up
runtime: Reducing theoretical heap fragmentation #21695
It is possible that after one or more GC cycles a span may contain only a single allocated object. After the program makes a phase change that size object may become unpopular and there is no need to allocate in that span again. This would be detectable after several GCs cycles as a span that has not been allocated in. It would be really nice if we could move that object and use that span for a different size class. That approach is often touted as an advantage of a moving collector. It is important to point out that this is merely a theoretical problem and currently there is no indication of it in the wild in an important application. Someday if it becomes a problem this issue offers a possible solution.
The perhaps novel idea is that we morph the span into a span with a larger size class according to the needs of the new phase. The single allocated object remains where it is but the garbage collector treats it as a larger sized object based on the span's new class size. There will be (new_size - old_size) fragmentation for that single object but that seems a small price to pay. The rest of the span would be used to allocate objects of the new popular size. Not only would this work for a single object but for any sparsely populated span where sparsely is determined by some TBD heuristic.
What if the original object straddled two of the new size class' objects? This could be easily avoided by selecting some other size class. But assuming we didn't want this restriction. If there is space both before and after the object in the new size class simply put a pointer in those free slots to the other part of the object and adjust the GC pointer map. The result would be that the GC would never free the object until both halves were no longer live.
An alternate approach would be to introduce a new special that links the slots together. Sweeping already has to scan all of the specials, so it would be easy and inexpensive for it to also handle these specials.
This would also make it possible to transition a span from a larger size class to a smaller size class.