A simple semi-space collector – wingolog (2022) (opens in new tab)

An immediate question I have is whether one could extend compacting GCs to also "sort" or "cluster" the live objects for better cache access in some way (in a practical sense I mean, where the extra runtime overhead is worth it). Also what kind clustering would actually work in that case.

I'm guessing naively tracking how often each object is accessed in a certain window of time and sorting by that wouldn't work, since the most accessed objects could be used at completely different times - some sort of "accessed together" algorithm probably makes more sense. But then we're in the territory of a combinatorial explosion of options if we're not careful.

Maybe something really stupid would work:

    1. use a single global integer
       that increases by one with
       each heap memory access,
    2. assign the counter's value to
       GC metadata of the accessed
       object in question as a sort
       of "time stamp"
    3. during compacting, "sort"
       all living objects by whatever
       they have as their value
       (this is probably really hard)
    4. after compacting, reset counter
       and time stamps

I presume that this question must have been researched to death, does anyone have any suggestions?