Skip to content

runtime: Reducing theoretical heap fragmentation #21695

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
RLH opened this issue Aug 30, 2017 · 1 comment
Open

runtime: Reducing theoretical heap fragmentation #21695

RLH opened this issue Aug 30, 2017 · 1 comment

Comments

@RLH
Copy link
Contributor

RLH commented Aug 30, 2017

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.

@aclements
Copy link
Member

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.

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

3 participants