87

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?

Christian Dean
  • 2,790
  • 1
  • 22
  • 38
  • 2
    I'd appreciate it if the close voter of this question could state exactly what is wrong so I could fix it? – Christian Dean Jun 14 '17 at 14:11
  • [this answer](https://softwareengineering.stackexchange.com/a/350868/31260) suggests that some may feel the question is too broad: "An entire book is needed to answer." – gnat Jun 14 '17 at 15:04
  • 7
    If you accept the fact that the GC is basically part of a library required by a particular programming language implementation, then the gist of your question has nothing to do with GC per se and everything to do with [static versus dynamic linking](https://stackoverflow.com/questions/311882/what-do-statically-linked-and-dynamically-linked-mean). – Theodoros Chatzigiannakis Jun 14 '17 at 19:17
  • 8
    You can consider the garbage collector to be part of the runtime library that implements the language's equivalent to `malloc()`. – Barmar Jun 14 '17 at 20:51
  • 10
    The operation of a garbage collector depends upon the characteristics of the *allocator*, not the *compilation model*. The allocator knows every object that has been allocated; it allocated them. Now all you need is some way of knowing which objects are still *alive*, and the collector can deallocate all objects except them. Nothing in that description has anything to do with the compilation model. – Eric Lippert Jun 15 '17 at 17:17
  • 1
    GC is a feature of dynamic memory, not a feature of the interpreter. – Dmitry Grigoryev Jun 16 '17 at 12:06

6 Answers6

124

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.

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • 1
    Interesting. I would have never guessed that had it not been for those excerpts in my question. I guess my mistake was thinking of a compiler as strictly doing one and _only_ one thing; compiling. – Christian Dean Jun 14 '17 at 07:04
  • 4
    @ChristianDean what more things does a compiler do? The code for a garbagecollecter can also be compiled along with the rest of the code. Some people consider the linker a serperate process while some think of it as a step in the compiling process. – Pieter B Jun 14 '17 at 07:21
  • 53
    @ChristianDean Note that even C has a runtime library. While it doesn't have GC, it still performs memory management through that runtime library: `malloc()` and `free()` are not built in to the language, are not part of the operating system, but are functions in this library. C++ is also sometimes compiled with a garbage collection library, even though the language was not designed with GC in mind. – amon Jun 14 '17 at 07:29
  • 18
    C++ also contains a runtime library that does things like make `dynamic_cast` and exceptions work, even if you don't add a GC. – Sebastian Redl Jun 14 '17 at 08:04
  • 23
    The runtime library is not necessarily copied into each executable (which is called static linking) it may only be referenced (a path to the binary containing the library) and accessed at execution time: this is dynamic linking. – mouviciel Jun 14 '17 at 08:06
  • 16
    The compiler is also not required to directly jump into your program's entrypoint without anything else happening. I'm making an educated guess that every compiler actually inserts a bunch of platform-specific initialisation code before it calls `main()`, and it's perfectly legal to, say, fire up a GC thread in this code. (Assuming the GC isn't done inside memory allocation calls.) At runtime, GC only really needs to know what parts of an object are pointers or object references, and the compiler needs to emit the code to translate an object reference to a pointer if the GC relocates objects. – millimoose Jun 14 '17 at 09:43
  • 15
    @millimoose: Yes. For example, on GCC, this piece of code is `crt0.o` (Which stands for "**C** **R**un**T**ime, the very basics"), which gets linked with every program (or at least every program that isn't *free-standing*). – Jörg W Mittag Jun 14 '17 at 12:57
  • 3
    @millimoose Even if the compiler does not directly insert code before the user's entry point, DLLs have the ability to run code at init. So just by linking the dll, it can hook in to lifecycle events for the application. – Bradley Uffner Jun 14 '17 at 13:38
  • 1
    Not just a runtime library. The compiled program is *annotated* with info that will be needed by GC. – Daniel R Hicks Jun 14 '17 at 18:47
  • Technically it's the linker inserting code before main(), rather than the compiler, although they're often both in the same program. There will usually be an option for building freestanding programs, used on embedded platforms. – pjc50 Jun 16 '17 at 08:49
60

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.

Konrad Rudolph
  • 13,059
  • 4
  • 55
  • 75
  • this doesn't seem to offer anything substantial over points made and explained in [top answer](https://softwareengineering.stackexchange.com/a/350842/31260) posted 3 hours before – gnat Jun 14 '17 at 10:47
  • 12
    @gnat I felt it was useful/necessary because the top answer not strong enough by far: it mentions similar facts, but it fails to point out that singling out garbage collection is a completely artificial distinction. Fundamentally, OP’s assumption is flawed, and the top answer doesn’t mention this. Mine does (while avoiding the rather brusque term “flawed”). – Konrad Rudolph Jun 14 '17 at 12:49
  • It's not all that special, but I'd say it's *somewhat* special, since usually people think of libraries as something they explicitly call from their code; rather than an implementation of fundamental language semantics. I think the OP's wrong assumption here is rather that a compiler is only to translate code with a more or less straightforward way, rather than instrument it with library calls the author didn't specify. – millimoose Jun 14 '17 at 13:19
  • 7
    @millimoose Runtime libraries operate behind the scenes in a multitude of ways without explicit user interaction. Consider exception propagation and stack unwinding/destructor calling. Consider dynamic memory allocation (which is usually not just calling a function, as in C, even when there’s no garbage collection). Consider handling of dynamic type information (for casts etc). So the GC really isn’t unique. – Konrad Rudolph Jun 14 '17 at 14:01
  • @KonradRudolph I'm aware, but if the OP is coming from a C perspective, that is the likely misconception. (Or from the perspective of compiler construction class in whichever year of college.) And how the runtime library is used is pretty distinct from someone might imagine libraries work from the parts of them visible in programmer-written code. – millimoose Jun 14 '17 at 14:09
  • 4
    Yes, I admit I had worded that oddly. That was simply because I was skeptical of the compiler actual doing something like that. But now that I think about it, it does make much more sense.The compiler could simply link a garbage collector like any other part of the standard library. I believe some of my confusion stemmed from thinking of a garbage collector as only part of an interpreter implementation and not a separate program in its own right. – Christian Dean Jun 14 '17 at 15:04
  • Are stack unwinding for exceptions and run time type information in C++ really "run time libraries" in the sense that the code for doing that is in a distinct (e.g. .dll, .lib) file, the same way that the code for `printf` is? Or is it built-in to the the compiler? I'm skeptical because those are language facilities that need access to *language*-implementation specific information, as opposed to, say, libc which needs OS-specific information but accesses those (conceptually) through standard language facilities. – Peter - Reinstate Monica Oct 08 '22 at 13:35
  • @Peter-ReinstateMonica They’re different, but they’re still part of the runtime. – Konrad Rudolph Oct 09 '22 at 08:14
55

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.

avdgrinten
  • 674
  • 5
  • 4
  • 9
    Between utility libraries and JIT compiling, the lines between "compiled to native" and "runs in a runtime environment" are becoming more and more blurred. – corsiKa Jun 15 '17 at 02:15
  • 6
    Just to add a bit about languages that don't come with GC support: It's true that C and other such languages don't provide information about call stacks, but if you're OK with some platform-specific code (usually including a bit of assembly code) it's still possible to implement "conservative garbage collection". The [Boehm GC](https://en.wikipedia.org/wiki/Boehm_garbage_collector) is an example of this used in real life programs. – Matti Virkkunen Jun 15 '17 at 12:24
  • 2
    @corsiKa Or rather, the line is much more distinct. Now we see that those are different unrelated concepts, and not antonyms of eachother. – This company is turning evil. Jun 16 '17 at 09:54
  • 4
    One additional complexity that you need to be aware of in compiled vs interpreted runtimes relates to this sentence in your answer: "(Tracing) garbage collection usually starts by walking the call stacks of all threads that are currently running." My experience of implementing GC in a compiled environment is that tracing the stacks is not enough. The starting point is *usually* suspending the threads for long enough to trace *from their registers*, because they may have references in those registers that haven't yet been stored in the stack. For an interpreter, this isn't usually ... – Jules Jun 16 '17 at 10:49
  • ... a problem, because the environment can arrange for GC to take place at "safe points" where the interpreter knows that all data is safely stored in the interpreted stacks. – Jules Jun 16 '17 at 10:51
23

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.

Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125
  • Good answer. Minor nitpick: “A programming language is a specification written in some technical report” — There are many programming languages without explicit specification (beyond the reference implementation, of course). – Konrad Rudolph Jun 14 '17 at 14:02
  • 5
    You mean that there are many programming language *implementations* without an explicit specification. Yes, I agree with that. But my point is that a programming language is *not* a software (like some compiler or some interpreter). It is something which has a syntax and a [semantics](https://en.wikipedia.org/wiki/Semantics_(computer_science)) (perhaps both being ill-defined). – Basile Starynkevitch Jun 14 '17 at 14:03
  • No, I meant “programming languages”. Ruby is a *programming language* (in fact, there’s no implementation called “Ruby”; the implementations are called MRI, CRuby, YARV, etc.). Yet it famously has no formal specification (or maybe that changed? It didn’t, for a long time). – Konrad Rudolph Jun 14 '17 at 14:06
  • It still has some documentation, which could be understood as some poor specification (with as you said, some "reference implementation" for things undocumented) – Basile Starynkevitch Jun 14 '17 at 14:07
  • 4
    @KonradRudolph: That depends entirely on your definition of "formal" and "specification" :-D There is The [ISO/IEC 30170:2012 Ruby Programming Language Specification](http://iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=59579), which specifies a small subset of the intersection of Ruby 1.8 and 1.9. There is the [Ruby Spec Suite](https://github.com/ruby/spec), a set of examples of boundary cases that serve as a kind of "executable spec". Then, [*The Ruby Programming Language* by David Flanagan and Yukihiro Matsumoto](http://shop.oreilly.com/product/9780596516178.do). – Jörg W Mittag Jun 14 '17 at 14:12
  • 4
    Also, [The Ruby Documentation](https://ruby-doc.org/). Discussions of issues on the [Ruby Issue Tracker](http://bugs.ruby-lang.org/). Discussions on the ruby-core (English) and ruby-dev (Japanese) mailinglists. Common sense expectations of the community (e.g. `Array#[]` is O(1) worst-case, `Hash#[]` is O(1) amortized worst-case). And last but not least: matz's brain. – Jörg W Mittag Jun 14 '17 at 14:16
  • @JörgWMittag Let’s not get too hung up on a specific example. ;-) In my defence, my most active contact with Ruby predates RubySpec as well as the book. Anyway, my initial comment was merely meant to clarify that not all programming languages have a separate specification in the form of (something like) a technical report. – Konrad Rudolph Jun 14 '17 at 14:16
  • 6
    @KonradRudolph: The point is: even a language with no formal specification and only a single inplementation still can be separated into "the language" (the abstract rules and restrictions) and "the implementation" (the code processing programs according to those rules and restrictions). And the implementation still gives rise to a specification, albeit a trivial one, namely: "whatever the code does is the spec". That's how the ISO spec, RubySpec, and the RDocs were written, after all: by playing around witth and/or reverse engineering MRI. – Jörg W Mittag Jun 14 '17 at 14:18
  • @JörgWMittag I never said anything different. In fact, I explicitly clarified that Ruby is *not* the implementation. And my initial comment was pretty carefully worded, saying “explicit specification”, so I don’t understand why we’re still discussing this, five comments later. – Konrad Rudolph Jun 14 '17 at 14:20
  • 1
    Glad you brought up Bohem's garbage collector. I would recommend the OP study it because it is an excellent example of just how simple garbage collection can be, even when "bolted on" to an existing compiler. – Cort Ammon Jun 14 '17 at 23:01
  • @CortAmmon - Agreed. It's also surprising how effect conservative GC can be. Many years ago I used to work on a Java to native code ahead-of-time translator that used Boehm GC as its collector. Despite the fact that this theoretically gave it a disadvantage due to not understanding the memory layout of Java objects, the system gave Hotspot a run for its money in most memory-intensive tasks. (It didn't do so well in numeric tasks, because we didn't have the time or inclination to optimize heavily for those...) – Jules Jun 16 '17 at 11:02
6

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.

maaartinus
  • 2,633
  • 1
  • 21
  • 29
  • Both Ocaml and SBCL are native compilers. So there *are* "natively compiled language" implementations. – Basile Starynkevitch Jun 15 '17 at 04:11
  • @BasileStarynkevitch WAT? How does naming some less well-known compilers relate to my answer? Isn't SBCL as a compiler for a originally interpreted language an argument in favor of my claim that the distinction makes no sense? – maaartinus Jun 15 '17 at 08:29
  • Common Lisp (or any other language) is *not* interpreted or compiled. It is a programming language (a specification). Its implementation can be a compiler, or an interpreter, or something in between (e.g. a bytecode interpreter). SBCL is a interactive compiled implementation of Common Lisp. Ocaml is also a programming language (with both a bytecode interpreter and a native compiler as implementations). – Basile Starynkevitch Jun 15 '17 at 08:31
  • @BasileStarynkevitch That's what I'm claiming. 1. There's no such thing as interpreted or compiled language (though C is rarely interpreted and LISP used to be rarely compiled, but this doesn't really matter). 2. There are interpreted, compiled and mixed implementations for most well-known languages and there's no language precluding compilation or interpretation. – maaartinus Jun 15 '17 at 08:44
  • You can find interpreters for C and most implementations of Common Lisp have some *compiler* (at least to bytecode). The Common Lisp specification *explicitly* speaks of [compilation](http://www.lispworks.com/documentation/HyperSpec/Body/03_b.htm) – Basile Starynkevitch Jun 15 '17 at 08:44
  • @BasileStarynkevitch Sure, but *where do we disagree*??? See e.g. my last sentence. +++ Concerning bytecode, it works the same for Java which I used as an example. – maaartinus Jun 15 '17 at 08:52
  • 6
    I think your argument makes a lot of sense. The key point to grok is that you *always* run a "native program", or "never", however you want to see it. No exe on Windows is per se executable; it needs a loader and other OS features just to start and is [actually partly "interpreted" as well.](https://en.wikipedia.org/wiki/Portable_Executable) This becomes more obvious with .net executables. `java myprog` is as much or as little native as `grep myname /etc/passwd` or `ld.so myprog`: It is an executable (whatever that means) which takes an argument and performs operations with the data. – Peter - Reinstate Monica Jun 15 '17 at 09:25
3

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.

Paul Johnson
  • 139
  • 2