undefined | Better HN

0 pointssilentbicycle13y ago0 comments

Not necessarily -- lazy sweeping only needs to do work proportional to live data (like copying GC), rather than proportional to dead data.

I have a pretty straightforward implementation of a lazy mark-sweep collector here (in C): https://github.com/silentbicycle/oscar

Basically, instead of marking live data, then sweeping all unmarked data, you just mark live data, then the next time a slot is requested, you step the allocator over the heap until it finds the next unmarked cell and re-use that. If most cells are dead, this happens very quickly. If you have to sweep over too many live cells (left deliberately vague), you grow the heap.

0 comments

3 comments · 1 top-level

waterhouse13y ago· 2 in thread

Interesting... I still feel that this is for the most part merely deferring the free-ing work to when you next allocate an object. It may succeed in getting the "free" cost down to a single instruction--checking a mark bit--but it is still a cost per dead object that a copying GC wouldn't have to pay. (The difference may be, as some say, "academic".) It does have the slight advantage of reducing the maximum pause time due to sweeping down to being proportional to live objects rather than garbage.

Also, what if you want to allocate a large object? You might have to skip over some unmarked cells. Either you'd waste the memory, or you would probably want to put them on a free-list of some sort, in which case you are doing more than just bumping a pointer and checking for a mark. ... I see, it says "equally-sized chunks of memory".

Still, that's a cool idea. As mark-and-sweep goes, anyway. :-} I'm rather more fond of copying garbage collectors--I like the determinism, the fact that (normally) the memory address of each object after a full copying GC will depend only on the structure of the graph of objects, and not on the memory addresses of the objects prior to the GC. (In other words, it destroys the information "what the memory address of each object was before this GC". This implies a somewhat higher inherent cost, to eliminate this entropy. See [1] for musings about the relation of this to thermodynamics.) In particular, whether you have fragmentation issues won't depend on the past history of your program. (You could say that the space lost to fragmentation is fixed at a factor of 2.)

[1] http://www.pipeline.com/~hbaker1/ThermoGC.html

silentbicycleOP13y ago

Checking the mark bit can be quite cheap, though, particularly if you store the mark bits in their own array - the next several bits will be in-cache. Still, the overall performance is likely to vary quite a bit for either scheme depending on the project's other quirks. Mark-sweep has the advantage that it doesn't need to move objects, but copying is easier with variable-size allocations, etc.

Another disadvantage with lazy sweeping is I don't see a clear way to make it generational. (Right?)

crumblan13y ago

Mark each arena with the last time something was collected from it and just skip sweeping old pages until X cycles have passed? Just thinking out loud... that check wouldn't save time for half-pages of old objects.

j / k navigate · click thread line to collapse