7

When reading the Python docs for writing C extensions, one can find the following text in the part about CPython's garbage collection strategy (emphasis mine):

... The disadvantage [of automatic garbage collection] is that for C, there is no truly portable automatic garbage collector, while reference counting can be implemented portably (as long as the functions malloc() and free() are available — which the C Standard guarantees). Maybe some day a sufficiently portable automatic garbage collector will be available for C. Until then, we’ll have to live with reference counts.

What exactly is the author's intention in the emphasized statement? Surely one can easily implement a portable tracing GC, at least for the specific VM at hand, using only malloc, free and basic data structures.

I suppose (and please correct me if I'm wrong) that the author refers to more advanced GC strategies, such as a "moving GC" (I'm actually not sure what that is), etc.

If so - please explain the reasons why, assuming the author is correct, it is difficult to create a portable advanced garbage collector.

  • Creating a precise general gc for C involves instrumenting all the C code to generate additional bookkeeping for how the memory is used, solving the halting problem and similar trivial pursuits. Creating a reasonably portable non-moving one for a VM written in C on the other hand is well-understood, yes, though aliasing rules must be accounted for. If you want to move allocated data, you need compiler-cooperation for getting the bookkeeping to rewrite the stack and registers though, which is beyond C. – Deduplicator Mar 29 '20 at 13:07
  • 3
    The author of that passage doesn't actually say that it is difficult. He simply says that it is not available. C was never intended to be a garbage-collected language, and its users understand that and use it accordingly. – Robert Harvey Mar 29 '20 at 13:56
  • Refcounting needs operations to increment/decrement the refcount, and it is the programmer's responsibility to call them (can be automated in C++ though). This is entirely portable. But tracing through memory to figure out which objects are still referenced requires reflection capabilities that C simply doesn't have – memory is effectively untyped. There is the idea of conservative GC (anything that looks like a pointer is treated as a pointer to the object) but that's still fairly fragile, e.g. when considering object slicing. – amon Mar 29 '20 at 14:17
  • How do you define "sufficiently portable", "truly portable", and "automatic garbage collector"? I feel without a precise definition of those terms, this is all just a matter of opinion. For example, why is the reference counting collector which exists in CPython considered "truly portable", but the tracing collector which also exists in CPython isn't? And what's wrong with the Boehm-Demers-Weiser collector? – Jörg W Mittag Mar 29 '20 at 14:24
11

Garbage collection requires the possibility to find objects in memory that are no longer used. One way of doing it is to have a marking algorithm that goes through all the active references. Another way is to use a reliable reference counting.

It is indeed easy to implement some reference counting features in C as your article shows. But nothing in standard C ensures that reference counting is performed reliably:

  • every pointer assignment could require reference counting
  • when a pointer is no longer used or needed, a reference decrement could be needed.

The C semantic is also lacking some rules that would make garbage collection possible. For example:

  • Pointer arithmetics make it very difficult to use an efficient marking algorithm. Even if the compiler would help, you would have to track the use of memory ranges instead of just marking single objects.
  • The use of casting could transform any place of allocated memory into a pointer at runtime, making it impossible to guarantee proper marking.
  • To add to the efficiency problem: the generated code for every pointer would have to handle the case of a pointer to stack memory without GC and a pointer to heap with GC. That would be a huge overhead that no compiler builder is ready to take.
  • The semantics would still need to define what cleaning activities to do when before the memory is released (also applies for the simpler case of reference counting).

Since the prerequisite cannot be fulfilled with the standard C language features, nobody attempted to create a standard GC functionality in the library.

All implementations of GC with C therefore rely on good will. For example, I remember on early MacIntosh (in the early 90's) there was a C compiler that relied on the OS memory management that used also block moving like a moving garbage collector. But whenenver you used pointer arithmetics to iterate on some allocated memory, it required you to first inform the system so that the memory does not get moved in-between (HLock/HUnlock). And it was of course totally non standard (and error prone).

Some people tried to extend the C language to add the kind of missing discipline that would be required for reference counting. One guy succeeded and brought us C++. In C++ you have reference counting smart pointers, with automatic destruction when an object is no longer used. In the standard library. But it is a very simple form of garbage collection: nothing identifies groups of objects referring to each other that are not used anywhere else. We are still far from a mark&sweep garbage collector.

FYI: a moving GC is a GC that moves non-contiguous used memory blocks, in order to increase the size of contiguous free blocks (defragmentation). This adds a level of complexity since in C pointers would have to be updated as well. In GC languages moving is not an issue because objets are accessed indriectly through an object reference that can be updated by GC.

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.