MPS issue job003783

TitleChainCondemnAuto condemns too many generations
Assigned userGareth Rees
DescriptionChainCondemnAuto [1] condemns all generations up the highest generation whose new size is greater than its capacity. But it’s not a good idea to collect all lower generations when collecting a generation. That’s because when you collect the world, you use at least double the memory in use because you have to reallocate all the live objects (and in practice more than double because the client program is continuing to allocate).
AnalysisIt’s better to keep the work small—collecting just one generation at a time if possible. So would it be a good idea to collect just the lowest generation that’s over-capacity? The trouble with that is you might never get around to collecting the higher generations at all, because there’s always some lower generation that needs collecting. We need some kind of rational basis for making this decision.

Another problem with the new algorithm is the possibility that a collection that promotes a lot of survivors may see the next generation immediately exceed its capacity, and so immediately need collecting. (And so on up the chain.) This is only likely happen if the chain is poorly constructed, with higher generations having smaller capacities than lower generations, but nonetheless the MPS should not behave badly in this situation.

Proposal: store, for each generation, the last time it was collected. Define a scoring function that combines (time since last collected) and (amount over capacity) to produce a score indicating the urgency of collecting this generation. In TracePoll, compute the urgency of all generations, and collect the most urgent.

But see [2]: "I think it would make sense to quickly try the simple idea of just condemning the most urgent generation (and nothing else) — although I am worried about fairness under this algorithm (a quickly-filling nursery could always hog the urgency metric, preventing other generations from being collected), in practice the fairness issue is present in the current algorithm, just at the level of whole chains rather than generations in the chain."
How foundinspection
Evidence[1] <>
[2] <>
Created byGareth Rees
Created on2014-05-01 18:22:49
Last modified byGareth Rees
Last modified on2014-06-20 15:30:27
History2014-05-01 GDR Created.