On 20 June 2010 16:01, Caldarale, Charles R <chuck.caldar...@unisys.com>wrote:
> All modern GC algorithms are variations of mark-sweep-compact. The > basic operation consists of following the object reference graph from > a set of known roots (eg, thread stack frames), marking each > discovered object with a found flag, and copying the found objects to > an unoccupied area. Unreachable (dead) objects are never encountered, > so their number or size does not come into play. The space occupied > by dead objects is automatically reclaimed as live objects are copied > over them. > > Note that in some variants, the cost of a compact *does* vary with the number of dead objects. In Squeak (Smalltalk), for example, each object header contains the object size, and hence by implication the address of the next object header. Squeak's GC compacts (after the mark phase) by starting at the bottom of object memory and iterating through each object, copying down the live ones and updating pointers on the way. In Java, this would only ever be necessary in OldSpace - with a generational GC where you're collecting anything other than the oldest generation, you just copy the live objects out as you encounter them and update any pointers to other objects in the same generation, after which you know the space is empty. Typically, the speed of such a compact is limited by the speed of access to memory. Most modern memory architectures will treat such sequential read access specially and start to read-ahead, so the memory overhead isn't as bad as it might be. My GC knowledge is a little out of date, so if any of the current GC experts wish to correct me I'll be interested! - Peter
