Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Generations
Some of the early research into garbage collection showed that the majority of objects were very short-lived. This was in Lisp, so the findings aren't completely applicable to all languages, but they often are.
With a typical malloc()/free() implementation, the cost of allocating and deallocating an object is roughly the same, irrespective of how long it persists. This fact is part of the reason why languages like C allow allocation of small objects on the stack. It allows allocation of short-lived objects by just modifying a pointer. The downside is that the creator of the object, rather than the user, determines its lifetime.
The simplest copying garbage-collector algorithm takes advantage of this situation. Allocations work via a simple bump-the-pointer allocation from a single block of memory—every new object is allocated straight after the previous ones. When this block of memory is exhausted, the collector copies all of the objects that are still live from it into another block of memory.
A slight extension of this principle notices that this behavior typically ends up repeatedly copying the same objects at the start of the memory block, and splits the memory into generations. Objects are allocated initially in the way that I've just described, but if they're still alive after a few passes through the copy cycle then they're moved into a generation that's not copied as often.
Modern Java VMs use multiple generations. Even conservative, non-copying collectors can make use of generations to avoid some scanning. For example, the Boehm GC will mark pages that are not frequently modified as read-only, using mprotect(). Then it can catch the segmentation fault signal when the page is modified. If it isn't modified between scans, any objects that were reachable from that page are still treated as live.
Again, this is particularly useful in cooperation with a paging system. If a collector knows that an object is not modified (without having to swap it back in to check), that can reduce thrashing.