6
$\begingroup$

TL;DR: Could a programming language that uses manual memory management use a tracing GC to rescue the usual suspects of memory leaks?

I was reading about the Boehm GC and came across this page that talks about using the Boehm GC to "detect leaks":

The garbage collector may be used as a leak detector. In this case, the primary function of the collector is to report objects that were allocated (typically with GC_MALLOC), not de-allocated (normally with GC_FREE), but are no longer accessible. Since the object is no longer accessible, there in normally no way to de-allocate the object at a later time; thus it can safely be assumed that the object has been "leaked".

I have never used the Boehm GC, so it is possible I am missing something when I read the above statement and don't know how successful the Boehm GC is in "real world" usage is and what its limitations are. But it seems it can tell if an object is "leaking". The page uses the words "normally" and "typically" but the devil is in the details, details I am not familiar with.

Take the above and couple this idea that Python primarily uses reference counting supplemented by a tracing GC to manage memory. The point I am focusing on is this: tracing GCs can work with other memory management techniques (not sure how if this is rendered mute by python's infamous reputation when it comes to memory).

I was thinking the above two ideas side by side and wondering: Can tracing GCs work alongside manual memory management in the same way the tracing GC in python works alongside refc?

Could something like the Boehm GC be extended or has there been work to extend GCs to work alongside manual memory management. So, perhaps benefiting from the speed of manual memory management with the cushion of tracing GCs to fall back on albeit at a cost - while the programmer can deal with leaks as they are detected.

The idea sounds too layman to be novel, so I suspect my question might be better asked as: what are the limitations of a hybrid tracing GC + manual memory management approach?

$\endgroup$
1
  • $\begingroup$ The issue I can foresee is that when memory is manually freed, the programmer will also need to ensure that any latent references to that memory are zeroed out, not just unused. Otherwise the GC will see references which might now point to a different allocation (at the same address) and think that they keep that allocation alive. $\endgroup$
    – kaya3
    Commented Apr 8 at 14:02

2 Answers 2

7
$\begingroup$

Is there room for GCs in manual memory management?

Yes.

First of all, reference-counting, even without a tracing GC to collect cycles, is typically considered a form of GC itself. It is imperfect, in that it may not collect cycle unless augmented, but it is memory safe.

Secondly, there is also a host of schemes for a variety of circumstances. While arenas/bump allocators may not be thought of as GCs, I'd argue they're somewhat close to them at least. And of course there's the whole suite of "solutions" to assist with concurrent operations:

  • Read-Copy-Update (RCU) is a GC mechanism used in the Linux kernel.
  • Hazard Pointers are used in lock-free data-structures.
  • Epoch-Based Reclamation (EBR) and Quiescent-State-Based Reclamation (QSBR) are also used in lock-free data-structures, in various flavors.

There's a very diverse ecosystem of various solutions to memory reclamation for a variety of situations -- often involving concurrency.

Is there room for a Tracing GC in manual memory management?

Yes.

Very much like in Python, reference-counting can be helpfully supplemented by a cycle collector. Collecting cycles involves tracing, and thus a (limited in scope) Tracing GC is involved in such a case.

There are implementation difficulties. In most manual memory management languages, there's no language facility to actually trace, and a tracing implementation regularly needs to trace across manually managed memory -- as a simple example, think of a Traced<Foo> object, where Foo contains a Vec<Traced<Bar>>. And of course there's the whole root identification issue. In such a case, the user cooperation is typically required, which leaves some room for error. Nonetheless, the result is a (limited in scope) Tracing GC.

Beyond cycle collecting, however, I have seen attempts at defining "limited-in-scope" GCs for usecases where GCs are useful: graphs, and lock-free collections.

Those GCs typically have a very small scope -- sometimes managing a single graph, or a single collection -- meaning that multiple GCs, sometimes of different implementations, may coexist in the same process. If they remain strictly separate, it's actually relatively simple. If they are interleaved, the challenges of tracing and rooting occur again.

What about a full GC?

This exists, too. As mentioned by @Chris Dodd, the Boehm GC can work both as a complete memory management solutions -- the user allocates, the GC handles the rest -- or as a hybrid solution -- the user allocates and sometimes deallocates, the GC handles the rest.

The main advantage of the conservative Boehm GC here is that it automatically handles tracing and rooting without user intervention, by using a conservative tracing approach including stack tracing. A conservative scan has some shortcomings -- not recognizing pointers stored in non-aligned memory, or stored as integers -- which impose limitations on the application code, but those are not very restrictive.

In hybrid mode, there's still clearly manual memory management going on.

$\endgroup$
4
$\begingroup$

Boehm GC works quite well in that mode -- you can use GC_MALLOC to allocate memory and use GC_FREE to free (some of) the memory (manual management), while letting the garbage collector free the rest. By using GC_FREE to free memory when possible/easy you reduce the overhead of the garbage collector -- it does not need to collect as often.

So that's mainly just an advantage -- better performance than "pure" garbage collection while dealing with memory that is not manually freed as well as just using the garbage collector.

The only disadvantage I see is that the garbage collector needs to be designed to support this, as well as the normal problems with a conservative collector (false retention) caused by garbage collection being an add-on not natively supported by the language.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .