How does garbage collection work in languages which are natively compiled?

Question

After browsing several answers an Stack Overflow, it is clear that some natively compiled languages have garbage collection. But it is unclear to me how exactly this would work.

I understand how garbage collection could work with an interpreted language. The garbage collector would simply run alongside the interpreter and delete unused and unreachable objects from the program's memory. They are both running together.

How would this work with compiled languages though? My understanding is that once the compiler has compiled the source code to the target code - specifically native machine code - it is done. Its job is finished. So how could the compiled program be garbage collected as well?

Does the compiler work with the CPU in some way while the program is executed to delete "garbage" objects? Or does the compiler include some minimal garbage collector in the compiled program's executable.

I believe my latter statement would have more validity than the former due to this excerpt from this answer on Stack Overflow:

One such programming language is Eiffel. Most Eiffel compilers generate C code for portability reasons. This C code is used to produce machine code by a standard C compiler. Eiffel implementations provide GC (and sometimes even accurate GC) for this compiled code, and there is no need for VM. In particular, VisualEiffel compiler generated native x86 machine code directly with full GC support.

The last statement seems to imply that the compiler includes some program in the final executable which acts as a garbage collector while the program is running.

The page on the D language's website about garbage collection - which is natively compiled and has an optional garbage collector - also seems to hint that some background program runs alongside the original executable program to implement garbage collection.

D is a systems programming language with support for garbage collection. Usually it is not necessary to free memory explicitly. Just allocate as needed, and the garbage collector will periodically return all unused memory to the pool of available memory.

If the method mentioned above is used, how exactly would it work? Does the compiler store a copy of some garbage collection program and pastes it into each executable it generates?

Or am I flawed in my thinking? If so, what methods are used for implementing garbage collection for compiled languages and how exactly would they work?

Answer 1

Garbage collection in a compiled language works the same way as in an interpreted language. Languages like Go use tracing garbage collectors even though their code is usually compiled to machine code ahead-of-time.

(Tracing) garbage collection usually starts by walking the call stacks of all threads that are currently running. Objects on those stacks are always live. After that, the garbage collector traverses all objects that are pointed to by live objects, until the entire live object graph is discovered.

It is clear that doing this requires extra information that languages like C do not provide. In particular, it requires a map of the stack frame of each function that contains the offsets of all pointers (and probably their datatypes) as well as maps of all object layouts that contain the same information.

It is however easy to see that languages that have strong type guarantees (e.g. if pointer casts to different datatypes are disallowed) can indeed compute those maps at compile time. They simply store a association between instruction addresses and stack frame maps and an association between datatypes and object layout maps inside the binary. This information then allows them to do the object graph traversal.

The garbage collector itself is nothing more than a library that is linked to the program, similar to the C standard library. For example, this library could provide a function similar to malloc() that runs the collection algorithm if memory pressure is high.

Answer 2

Does the compiler store a copy of some garbage collection program and paste it into each executable it generates?

It sounds unelegant and weird, but yes. The compiler has an entire utility library, containing a whole lot more than just garbage collection code, and calls to this library will be inserted into each executable it creates. This is called the runtime library, and you'd be surprised how many different tasks it typically serves.

Answer 3

Or does the compiler include some minimal garbage collector in the compiled program's code.

That’s an odd way of saying “the compiler links the program with a library that performs garbage collection”. But yes, that’s what’s happening.

This is nothing special: compilers usually link tons of libraries into the programs they compile; otherwise compiled programs couldn’t do very much without re-implementing many things from scratch: even writing text to the screen/a file/… requires a library.

But maybe GC is different from these other libraries, which provide explicit APIs that the user calls?

No: in most languages, the runtime libraries do a lot of behind-the-scenes work without public-facing API, beyond GC. Consider these three examples:

1. Exception propagation and stack unwinding/destructor calling.
2. Dynamic memory allocation (which is usually not just calling a function, as in C, even when there’s no garbage collection).
3. Tracking of dynamic type information (for casts etc).

So a garbage collection library isn’t at all special, and a priori has nothing to do with whether a program was compiled ahead of time.

Answer 4

How would this work with compiled languages though?

Your wording is wrong. A programming language is a specification written in some technical report (for a good example, see R5RS). Actually you are referring to some specific language implementation (which is a software).

^{(some programming languages have bad specifications, or even missing ones, or just as conforming to some sample implementation; still, a programming language defines a behaviour - e.g. it has a syntax and semantics -, it is not a software product, but could be implemented by some software product; many programming languages have several implementations; in particular, "compiled" is an adjective applying to implementations - even if some programming languages are more easier implemented by interpreters than by compilers.)}

My understanding is that once the compiler has compiled the source code to the target code - specifically native machine code - it is done. Its job is finished.

Notice that interpreters and compilers have a loose meaning, and some language implementations could be considered as being both. In other words, there is a continuum in between. Read the latest Dragon Book and think about bytecode, JIT compilation, dynamically emitting C code that is compiled into some "plugin" then dlopen(3)-ed by the same process (and on current machines, this is fast enough to be compatible with an interactive REPL, see this)

---

I strongly recommend reading the GC handbook. An entire book is needed to answer. Before that, read the Garbage Collection wikipage (which I assume you have read before reading below).

The runtime system of the compiled language implementation contains the garbage collector, and the compiler is generating code which is fit to that particular runtime system. In particular, allocation primitives (are compiled to machine code that) will (or may) call the runtime system.

So how could the compiled program be garbage collected as well?

Just by emitting machine code which uses (and is "friendly" and "compatible with") the runtime system.

Notice that you can find several garbage collection libraries, in particular Boehm GC, Ravenbrook's MPS, or even my (unmaintained) Qish. And coding a simple GC is not very difficult (however, debugging it is harder, and coding a competitive GC is difficult).

In some cases, the compiler would use a conservative GC (like Boehm GC). Then, there is no much to code. The conservative GC would (when the compiler calls its allocation routine, or the entire GC routine) sometimes scan the entire call stack, and assume that any memory zone (indirectly) reachable from the call stack is live. This is called a conservative GC because typing information is lost: if an integer on the call stack happens to look like some address, it would be followed, etc.

In other (more difficult) cases, the runtime provides a generational copying garbage collection (a typical example is the Ocaml compiler, which compiles Ocaml code to machine code using such a GC). Then the issue is to find precisely on the call stacks all the pointers, and some of them are moved by the GC. Then the compiler generates meta-data describing call stack frames, which the runtime uses. So the calling conventions and ABI are becoming specific to that implementation (i.e. compiler) & runtime system.

In some cases, machine code generated by the compiler (actually even closures pointing to it) is itself garbage collected. This is notably the case for SBCL (a good Common Lisp implementation) which generates machine code for every REPL interaction. This also requires some meta-data describing the code and the call frames used inside it.

Does the compiler store a copy of some garbage collection program and pastes it into each executable it generates?

Sort-of. However, the runtime system could be a shared library, etc. Sometimes (on Linux and several other POSIX systems) it could even be a script interpreter, e.g. passed to execve(2) with a shebang. Or an ELF interpreter, see elf(5) and PT_INTERP, etc.

BTW, most compilers for language with garbage collection (and their runtime system) are today free software. So download the source code and study it.

Answer 5

There are already some good answers, but I'd like to clear some misunderstandings behind this question.

There's no such thing as "natively compiled language" per se. For example, the same Java code was interpreted (and then partly just-in-time compiled at runtime) on my old phone (Java Dalvik) and is (ahead-of-time) compiled on my new phone (ART).

The difference between running code natively and interpreted is much less strict than it seems to be. Both need some runtime libraries and some operating system to work (*). The interpreted code needs an interpreter, but the interpreter is just a part of the runtime. But even this is not strict, as you could replace the interpreter by a (just-in-time) compiler. For maximum performance, you may want both (desktop Java runtime contains an interpreter and two compilers).

No matter how do run the code, it should behave the same. Allocating and freeing memory is a task for the runtime (just like opening files, starting threads, etc.). In your language you just write new X() or alike. The language specification says what should happen and the runtime does it.

Some free memory gets allocated, the constructor gets invoked, etc. When there's not enough memory, then the garbage collector gets called. As you're already in the runtime, which is a native piece of code, the existence of an interpreter does not matter at all.

There's really no direct connection between code interpreting and garbage collection. It's just that low-level languages like C are designed for speed and fine-grained control of everything, which doesn't fit well with the idea of non-native code or a garbage collector. So there's just a correlation.

This was very true in the old times, where e.g. the Java interpreter was very slow and the garbage collector rather inefficient. Nowadays, things are much different and speaking about an interpreted language has lost any sense.

---

(*) At least when speaking about general purpose code, leaving aside boot loaders and similar.

Answer 6

The details vary between implementations, but its generally some combination of the following:

• A runtime library which includes a GC. This will handle memory allocation and have some other entry points, including a "GC_now" function.
• The compiler will create tables for the GC so that it knows which fields in which data types are references. This will also be done for the stack frames for each function so that the GC can trace from the stack.
• If the GC is incremental (GC activity is interleaved with the program) or concurrent (runs in a separate thread) then the compiler will also include special object code to update the GC data structures when references are updated. The two have similar issues for data consistency.

In incremental and concurrent GC the compiled code and the GC need to cooperate to maintain some invariants. For instance in a copying collector the GC works by copying live data from space A to space B, leaving behind the garbage. For the next cycle it flips A and B and repeats. So one rule can be to ensure that any time the user program tries to refer to an object in space A this is detected and the object gets copied immediately into space B, where the program can continue to access it. A forwarding address gets left in space A to indicate to the GC that this has happened so that any other references to the object get updated as they are traced. This is known as a "read barrier".

GC algorithms have been studied ever since the 60s, and there is extensive literature on the subject. Google if you want more information.