16

Some (at least Mono's and .NET's) garbage collectors have a short term memory area which they scan often, and a secondary memory area which they scan less often. Mono calls this a nursery.

To find out which objects can be disposed of, they scan all objects starting from roots, the stack and the registers and dispose all objects that aren't being referenced anymore.

My question is how they prevent all in use memory from being scanned on every collect? In principle, the only way to find out what objects aren't in use anymore is to scan all objects and all their references. However, this would prevent the OS from swapping out memory even though it isn't in use by the application and feels like a huge amount of work that needs to be done, also for "Nursery Collection". It doesn't feel like they're winning much by using a nursery.

Am I missing something or is the garbage collector actually scanning every object and every reference every time it does a collection?

Improve this question
1
  • 1
    a nice overview is in an article The Art of Garbage Collection Tuning written by Angelika Langer. Formally, it is about the way how it's done in Java, but concepts presented are pretty much language agnostic – gnat Aug 24 '12 at 16:26
14

The fundamental observations which allow generational garbage-collection to avoid having to scan all older-generation objects are:

  1. After a collection, all objects that still exist will be of some minimum generation (e.g. in .net, after a Gen0 collection, all objects are Gen1 or Gen2; after a Gen1 or Gen2 collection, all objects are Gen2).
  2. An object, or portion thereof, which has not been written since a collection that promoted everything to generation N or higher cannot contain any references to objects of lower generations.
  3. If an object has reached a certain generation, it need not be identified as reachable to ensure its retention when collecting lower generations.

In many GC frameworks, it's possible for the garbage collector to flag objects or portions thereof in such a way that the first attempt to write to them will trigger special code to record the fact that they have been modified. An object or portion thereof which has been modified, regardless of its generation, must be scanned in the next collection, since it may contain references to newer objects. On the other hand, it's very common for there to be a lot of older objects that do not get modified between collections. The fact that lower-generation scans can ignore such objects can allow such scans to complete much more quickly than they otherwise would.

Note, btw, that even if one cannot detect when objects are modified and would have to scan everything on each GC pass, generational garbage collection could still improve the "sweep" stage performance of a compacting collector. In some embedded environments (especially those where there is little or no difference in speed between sequential and random memory accesses), moving blocks of memory around is relatively expensive compared to tagging references. Consequently, even if the "mark" phase can't be sped up using a generational collector, speeding up the "sweep" phase may be worthwhile.

Improve this answer
4
  • moving memory blocks around is expensive in any system, so improving the sweep is a gain even on your quad Ghz CPU system. – gbjbaanb Aug 25 '12 at 10:57
  • @gbjbaanb: In many cases, the cost of scanning everything to find live objects would be significant and objectionable even if moving the objects was totally free. Consequently, one should when practical avoid scanning old objects. On the other hand, refraining from compacting older objects is a simple optimization which can be accomplished even on simple frameworks. BTW, if one were designing a GC framework for a small embedded system, declarative support for immutable objects could be helpful. Tracking whether a mutable object has changed is hard, but one might do well to... – supercat Aug 25 '12 at 16:33
  • ...simply assume that mutable objects need to be scanned every GC pass but immutable objects do not. Even if the only way to construct an immutable object was to construct a "prototype" in mutable space and then copy it, the single extra copy operation could avoid the need to scan the object in future GC operations. – supercat Aug 25 '12 at 16:33
  • Incidentally, the garbage-collection performance on 1980's Microsoft-derived implementations of BASIC for 6502 microprocessors (and perhaps others as well) could be greatly enhanced in some cases, if a program which generated lots of strings that would never change, copied the "next string allocation" pointer to the "top of string space" pointer. Such a change would prevent the garbage collector from examining any of the old strings to see if they were still needed. The Commodore 64 was hardly hi-tech, but such "generational" GC would help even there. – supercat Aug 25 '12 at 17:25
7

The GCs you are referring to are generational garbage collectors. They are engineered to get the most out of an observation known as "infant mortality" or "the generational hypothesis", which means that most objects become unreachable very quickly. They indeed scan starting from the roots, but ignore all old objects. Therefore, they do not need to scan most of the objects in memory, they only scan young objects (at the expense of not detecting unreachable old objects, at least not at that point).

"But that's wrong", I hear you scream, "old objects can and do refer to young objects". You're right, and there are several solutions to that, which all revolve around gaining knowledge, quickly and efficiently, which old objects must be checked and which are safe to ignore. They pretty much boil down to recording objects, or small (larger than objects, but much smaller than the whole heap) ranges of memory which contain pointers to younger generations. Others have described those far better than me, so I'll just give you a couple of keywords: Card marking, remembered sets, write barriers. There are other techniques too (including hybrids), but these encompass the common approaches I'm aware of.

Improve this answer
3

To find out what nursery objects are still live, the collector only needs to scan the the root set and any old objects that have been mutated since the last collection, since an old object that has not been recently mutated cannot possibly point to a young object. There are different algorithms for maintaining this information at varying levels of precision (from an exact set of mutated fields to a set of pages where mutation may have occurred), but they all generally involve some sort of write barrier: code that runs on every reference-typed field mutation that updates the GC's bookkeeping.

Improve this answer
1

The oldest and simplest generation of garbage collectors actually did scan all of memory, and had to stop all other processing while they did it. Later algorithms improved on this in various ways - making the copy/scan incremental, or run in parallel. Most modern garbage collectors segregate objects into generations, and carefully manage cross-generational pointers so newer generations can be collected without disturbing older ones.

The key point is that garbage collectors work in close collaboration with the compiler and with the rest of the runtime to maintain the illusion that it is watching all of memory.

Improve this answer
2
  • I'm not sure what garbage collection approaches were used in minicomputers and mainframes prior to the late 1970's, but the Microsoft BASIC garbage collector, at least on 6502 machines, would set its "next string" pointer to top of memory, and then search all string references to find the highest address that was below the "next string pointer". That string would be copied just below the "next string pointer", and that pointer would be parked just below it. The algorithm would then repeat. It was possible for code to jinx the pointers to provide... – supercat Aug 25 '12 at 17:40
  • ...something like generational collection. I've sometimes wondered how hard it would be to patch the BASIC to implement "generational" collection by simply keeping the addresses of the top of each generation, and adding a few pointer-swap operations before and after each GC cycle. GC performance would still be pretty bad, but might in many cases be shaved from tens of seconds to tenths of seconds. – supercat Aug 25 '12 at 17:43
-2

Basically... GC uses "buckets" to separate what is in use and what isn't. Once it makes it check, it wipes out things that are not in use and moves everything else to 2nd generation (which is checked less often than 1st generation) and then moves things that are still in use in 2nd den to 3rd gen.

So, things in 3rd generation are usually objects that are stuck open for some reason, and GC doesn't check there very often.

Improve this answer
4
  • 1
    But how does it know which objects are in use? – Pieter van Ginkel Aug 24 '12 at 15:10
  • It keeps track of which objects can be reachable from reachable code. Once an object is no longer reachable from any code that can execute (say, code for a method that has returned) then the GC knows it's safe to collect – JohnL Aug 24 '12 at 16:04
  • Both of you guys are describing how GCs are correct, not how they are efficient. Judging from the question, OP knows that fully well. – user7043 Aug 24 '12 at 16:05
  • @delnan yes I was answering the question of how it knows which objects are in use, which is what was in Pieter's comment. – JohnL Aug 24 '12 at 16:38
-5

The algorithm usually used by this GC is the Naïve mark-and-sweep

you should also be aware of the fact that this is a not managed by the C# itself, but by the so called CLR .

Improve this answer
7
  • That's the feeling I got from reading about Mono's garbage collector. However, what I don't understand is why if they are scanning the complete working set on ever collect, they have a generational collector with which GEN-0 collection his very fast. How can this ever be fast with a working set of say 2GB? – Pieter van Ginkel Aug 24 '12 at 15:18
  • well, the real GC for mono is Sgen, you should read this mono-project.com/Generational_GC or some online articles schani.wordpress.com/tag/mono infoq.com/news/2011/01/SGen , the point is that this new technologies like CLR and CLI have a really modular design, the language becomes just a way to express something for the CLR and not a way to produce binary code. Your question is about implementation details and not about algorithms, because an algorithm still doesn't have an implementation, you should just read technical papers and articles from Mono, no one else. – user827992 Aug 24 '12 at 15:37
  • I'm confused. The strategy a garbage collector uses is not an algorithm? – Pieter van Ginkel Aug 24 '12 at 15:49
  • 2
    -1 Stop confusing OP. That the GC is part of the CLR and not language-specific is not relevant at all. A GC is mostly characterized by the way it lays out the heap and determines reachability, and the latter is all about the algorithm(s) used for that. While there can be many implementations of an algorithm, and you shouldn't get caught up in implementation details, the algorithm alone determines how many objects are scanned. A generational GC is simply an algorithm + heap layout which attempts to utilize the "generational hypothesis" (that most objects die young). These are not naive. – user7043 Aug 24 '12 at 16:00
  • 4
    Algorithm != implementation indeed, but an implementation can only deviate this far before it becomes an implementation of a different algorithm. An algorithm description, in the GC world, is very specific and includes things like not scanning the entire heap on nursery collection and how inter generational pointers are found and stored. It is true that an algorithm does not tell you how long a specific step of the algorithm will take, but that is not relevant at all to this question. – user7043 Aug 24 '12 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.