4 ms·
As an example of how simple, as I think people tend to see gc as complicated and scary, a simple tri-color mark and sweep gc in pseudo code: push_registers
by vidarh 9y ago
As an example of how simple, as I think people tend to see gc as complicated and scary, a simple tri-color mark and sweep gc in pseudo code:
push_registers_to_stack() // Simplifies dealing with roots - you can now ignore registers
// These are the roots:
// (grey objects are directly referenced from a root, but have not yet been scanned for pointers)
for_each_stack_value { mark_grey }
for_each_bss_variable { mark_grey }
// We then keep iterating over grey objects, scanning the values of those objects for further
// pointers (which we mark grey), and mark "finished" objects black:
while (ob = grey_list.shift) {
for each pointer in ob {
if white: mark_grey(pointer);
mark_black(ob)
}
}
// Now any objects you haven't touched are still white (and unreachable), and thus garbage:
for_each_object {
if white: free
else: mark_white
}
The above is inefficient, but it takes very little space to implement. If you know precise object layout and takes it into account when scanning, it's also precise, if not it's conservative (it may leave garbage if values in memory looks like pointers). Downside is that it is "stop the world", so if your heap is big, it'll cause noticeable pauses.
Simple GC's are easy.... Fast/good/efficient GC's on the other hand...
- vvanders 9y agoThe other downside is fragmentation(which is also why even embedded native tends to be static/up-front allocation based).
- vidarh 9y agoThat's true, and certainly if you can avoid dynamic allocations, do. But you can actually get "halfway" to a partially compacting gc very easily too if memory use is a bigger concern than performance and you want to avoid fragmentation: Set a (small) fixed size for all objects. It can be anything from a single pointer to any data that will be present in all objects. E.g. you might have class pointers and flags and a fixed number of bytes for auxiliary data. If any class needs more instance data, you make a pointer in that primary layout point to space in a secondary heap. Now compacting the secondary heap is easy: Just copy into new buffers and deallocate the old and update a single pointer per object. You can do that by a single pass through all allocated objects, or you can do something more complex. Compacting the primary heap is still messy (you'd need to identify all sites pointing to each object), but if you chose a small size for the primary objects there's less reason to do so, as while it is still possible to create pathological allocation patterns, unless the application reaches a high water mark and then frees a huge number of objects that it then never need again, any empty space left behind can always be perfectly filled by new primary object allocations, and hopefully each such object is fairly small. If you want to, though, you can also compact auxiliary data (the "secondary heap") into holes in the primary heap when there's a good enough fit. E.g. on top of the steps I outlined: For each object, if there's an auxiliary data pointer, check if there's a suitable hole (keep lists by "hole size" for example) in the primary heap. If so, move there. If not, copy to end of new secondary heap. Update source pointer.
- sehugg 9y agoYep, even Applesoft BASIC had a simple compacting GC for strings.
- vidarh 9y agoYes, that's certainly "low hanging fruit" in compacting in that if you have a list of "objects" that e.g. contain just a pointer and a length of auxiliary data, so that you have an indirection, compacting gets really easy since you only need to update a single location, and for things like strings that auxiliary data is likely to make up most of the memory use.
- pjmlp 9y agoEven simpler than your description, just plain reference counting, which is why it is usually the first GC algorithm many reach to. Eventually coupled with a basic tracing GC like you describe for collecting cycles. It won't win any performance awards, but does the job.