pcwalton

Occasional notes on Rust, Firefox, etc.

Removing Garbage Collection From the Rust Language

| Comments

I’ve been floating ways to simplify the memory management story in Rust around the core team lately. Memory management is a contentious topic, since we’ve worked hard to get to the current state of things, and with the push toward stability lately, there is a (quite reasonable!) resistance to any changes at this state. Still, I think the current memory management story in Rust is worth revisiting, as the current state of things may cause us problems down the line. Working with Dave Herman and Niko Matsakis, I’ve formulated a fairly concrete proposal at this point. The basic idea is to remove garbage collection from the core language and relegate it to the standard library, with a minimal set of language hooks in place to allow for flexible, pluggable automatic memory management.

This post is designed to explain the “why”, not the “how”—I’m leaving the concrete details of the proposed system to a future blog post or mailing list discussion. Rather, this explains the issue that I see with the current system. I think that the garbage collection story as it stands in Rust is not quite ideal, for three reasons: familiarity, simplicity, and flexibility. I’ll cover each in turn.

Familiarity

One of the most common questions almost every Rust beginner asks is “when do I use managed pointers, and when do I use owned pointers?” Or, more simply, “what are all these ~ and @ symbols everywhere?” Having worked on Rust for many years now, I’ve seen several reasons for the difficulty. Chief among them are:

  1. The difference between the stack and the heap is a difficult concept to grasp for many programmers used to languages like Java that don’t make such a distinction. This is, unfortunately, a fundamental difficulty of working in a systems language. There’s little that can be done about this without taking control of allocation out of the hands of the programmer. Doing that, however, would compromise the goals of the language—in low-level, performance-critical programming, being able to precisely control whether allocations occur on the stack or on the heap is crucial.

  2. The sigils make the code unfamiliar before the concepts are learned. Unlike the rest of the punctuation in Rust, ~ and @ are not part of the standard repertoire of punctuation in C-like languages, and as a result the language can seem intimidating. One of the benefits of keywords is that they are self-documenting in a way that punctuation is not. This could be fixed by switching to keywords, which I prefer for this reason; however, syntactic beauty is in the eye of the beholder and so I won’t lose sleep over this not changing if the community prefers the current syntax.

  3. There are two heaps, not just one, so beginners are confused as to which one to allocate into. This is a result of the “minimize sharing by default” philosophy of the concurrency system. However, the concurrency system has been part of the library rather than the language for several years now, so this seems somewhat out of place.

  4. Programmers don’t know which to use, since some operations are available with ~ and some operations are available with @. Actually, we were confused on this point for a long time as well—it wasn’t clear whether ~ or @ would become dominant. We debated for a long time which to present first, ~ or @. However, as the language and community evolved, and coding standards became more settled, a clear winner emerged: the owning pointer ~. In practice, the rule has been that programmers should use ~ to allocate in all circumstances except when they have no way of knowing precisely when the object in question should be freed.

Point (4), to me, is the most critical. The rule that emerged—~ over @—should not be surprising, in retrospect, as it is how systems software has been developed for decades. The key insight that was missing is that the owning pointer ~ is just the Rust equivalent of malloc and free. For many, probably most C programs, malloc and free are just fine (assuming you use them correctly, of course); each heap allocation is allocated in just one place and destroyed in just one place. Only when the lifetimes of objects become very complex do C and C++ programmers resort to manual reference counting to determine when an object should be freed (and many, perhaps most, C programs never get there). This is the role that has emerged for @ in Rust programs: @ is a replacement for manual reference counting in C programs. The kobject system in the Linux kernel, the GObject system in glib, and so forth, are the C equivalents of @ in Rust.

The key point here is that these are very specialized use cases in C, and @ has been relegated to a similarly marginal role in idiomatic Rust code. We thought for a while that many Rust programs would use @ extensively and that it would ease the learning curve for those not used to destructor-based memory management and references. This has not, however, been the case in practice. In reality, since the libraries all use owning pointers (~), Rust programmers have to learn them quickly anyhow. And once Rust programmers learn how to use ~ effectively, they quickly find @ relegated to a marginal role, if it’s used at all. ~ has so many advantages: deterministic allocation and destruction, interaction with the standard library, freedom from GC marking pauses, simpler semantics, appendability where vectors and strings are concerned, and sendability across tasks.

I think we’re better off teaching ~ as the go-to solution for most programs and relegating @ to a specialized role. @ has its use cases, to be sure; large, event-driven C++ programs use reference counting for a reason. But those use cases are specialized. Beginners should not be asking “should I use ~ or @?” The answer is almost always ~.

In this regard relegating @ to a library is just the natural conclusion of this approach. I feel that what beginners should be taught is that ~ is the way to allocate in Rust, and letting an ~ owning pointer go out of scope is the way you free in Rust. This is what we should be teaching in the language tutorial. As beginners become more comfortable with this and explore the libraries, they will learn about ways to achieve more dynamic memory management: tracing garbage collection with the Gc type, reference counting with the Rc type, and thread-safe reference counting with the Arc type. But by building only ~ into the language, we can reduce confusion by, in effect, making the language more opinionated.

Simplicity

Although Rust didn’t start out that way, one of the most interesting applications of Rust has been very low-level programming, even down to the level of kernels. The interest in this application of Rust was something of a surprise to us, but in hindsight it makes perfect sense. Low-level control over memory management isn’t something that most applications software, especially on the server side, wants; most of that software has migrated over to languages like Java, Ruby, and JavaScript that trade control and performance for convenience by making memory management automatically, and dynamically, managed by the runtime. The remaining class of software, most of which is written in C and C++, is software that must manage memory manually in order to achieve some combination of performance, simplicity, and/or the ability to self-host. The prospect of using a new language for this class of software, which includes OS kernels, game engines, and browser engines among others, is what is fueling the growth of the nascent Rust community.

It might be possible to create a language that presents only a simple, fully automatic memory management system at first, and which surfaces the machinery of safe manual memory management* only when the programmer requires it for maximum performance. This would ease the learning curve, as programmers would be able to write many, perhaps most programs without ever learning how to manage memory at all. However, at this point I don’t think that this language exists yet, and in particular I don’t think Rust is that language. There are basically two problems here: (1) ~ owning pointers are everywhere in Rust, from the standard library to the built-in macros, making learning about them a necessity from the get-go; and (2) it is basically impossible to program Rust without at least a cursory understanding of references (a.k.a. & pointers) and their lifetime semantics; even vec::each() uses references.

Despite the fact that this might seem like a negative result, I actually think it’s quite positive for the project. It helps to define the project’s scope. I don’t think automatic memory management in Rust is ever going to be as convenient as memory management in, say, Ruby or Java, and that’s OK! The same level of control that adds cognitive overhead to memory management in Rust compared to other languages also makes Rust able to go where few other industry languages have. This space, I think, is where Rust can really shine.

In short, I think that Rust as a language should focus on roughly the same application domain as C++ does.†

Important to this effort is to have as small of a runtime as possible, just as C++ does, leaving higher-level abstractions to libraries. And, in fact, we are almost there already. The only runtime support that compiled Rust programs require are a small set of “language items”, which are magic functions or traits written in Rust that are known to the compiler. Looking at the set of language items, and disqualifying legacy items that will be removed soon such as annihilate and log_type, there are just a few categories:

  1. Operator traits, like Add and Sub. These are analogous to operator+, operator-, and so forth in C++.

  2. Memory primitives, like str_eq. These are somewhat legacy at this point and probably could be converted to LLVM intrinsics like memcmp without much trouble, especially after dynamically sized types happens. In any case, in most C++ compilers memcmp and friends are builtins.

  3. Failure: fail and fail_bounds_check. This is analogous to throw in C++, although a Rust program that doesn’t want to use stack unwinding might want to use abort instead (which would be like -fno-exceptions) or do something more elaborate like the Linux kernel’s “oops” functionality.

  4. Allocation primitives malloc and free. These have direct C++ equivalents: operator new and operator delete.

  5. Garbage collection primitives.

Of these, the only language items that don’t have direct C++ equivalents are the garbage collection primitives. If those were eliminated, then Rust as a language would be every bit as freestanding as C++ is. In terms of suitability for kernel and embedded development, Rust would be on truly equal footing.

In summary: (1) all Rust programmers have to know how ~ and & work, despite the presence of @; (2) the only additional runtime primitives that Rust exposes and C++ doesn’t are those related to @.

Flexibility

When it comes to memory management, there are obviously many different strategies: stack allocation, heap allocation with malloc and free, arena allocation, and garbage collection. What’s less well known is that even among garbage collection, there are many different approaches, each with advantages and disadvantages. There’s thread-local GC, thread-safe GC, incremental GC, generational GC, reference counting, thread-safe reference counting, deferred reference counting, ulterior reference counting—the list goes on and on. (For a good survey of automatic memory management techniques and how they relate to one another, check out “A Unified Theory of Garbage Collection” by Bacon et al.) A program that wants to maximize performance among some axis (latency versus throughput) and remain safe with objects with complex lifetimes may have reasons to choose one or the other.

Specifically, there’s the perennial debate between reference counting and tracing garbage collection. Many applications are better with tracing GC because of the increased throughput it provides and straightforward handling of cycles, and many applications are better with reference counting because of implementation simplicity, cache behavior, mostly-incremental operation, and promptness of deallocation. It makes sense for applications to be able to choose between the two. Even more important is the tradeoff between thread-safe and thread-local garbage collection: concurrent garbage collection is practically always more expensive than thread-local garbage collection, so it makes sense for programs to restrict concurrent GC (including atomic reference counting) to be used only when needed.

Integrating multiple tracing garbage collectors or cycle collectors into one system is a hard problem, and I don’t think Rust is going to really solve it. However, integrating reference counting into a garbage collected system is straightforward, as long as cycles are not created (and in Rust we can forbid the creation of such cycles through clever use of the type system). In practice this seems to work well: we typically use thread-local tracing GC for data with complex lifetimes within one task, and we use thread-safe reference counting for data that must be shared between tasks.

Equally important is the ability to integrate with external garbage collection systems (usually reference counted ones). This is a problem that is often overlooked, but is terribly important for client software such as mobile apps and browser engines. On Windows, apps must integrate with the reference-counted COM system in order to use DirectX and other APIs. On the Mac and on iOS, apps have to integrate with Objective-C and the closely-related Core Foundation, also reference-counted systems. On Linux, GNOME apps have to integrate with GObject, again a reference-counted system. On Android, apps have to integrate with the garbage-collected Dalvik subsystem via the JNI. All of this requires that the memory management system in the language be deeply flexible.

Because of this, I’m suspect of blessing any particular form of automatic memory management in the core language. In Rust, the @ type is not only blessed with special syntax, but is eligible for borrowing and other operations in a way that user-defined types aren’t. Although Rust provides the facilities needed to build practically all the other forms of garbage collection, as well as those needed to integrate with external GC systems in a safe way, the resulting smart pointers feel second-class compared to @. A systems language designed to work in a diverse set of environments should have the flexibility to create memory management abstractions that feel first-class.

Conclusion

For these three reasons—familiarity, simplicity, and flexibility—I’d like to propose removing @ pointers from the language and replacing them with a small set of hooks allowing the same functionality to be implemented as a library and on user-defined types. We would ship tracing GC as part of the standard library and make it just as powerful and convenient as it is today (except for the @ syntax). We’d gain a flexible set of abstractions, make the language easier to learn, and make Rust into a truly freestanding language environment.

* Note that the safe qualifier here disqualifies manually-built free lists in garbage-collected languages, as these manually-built free lists provide no protection against errors like double “frees”, leaks, and danging pointers. (They’re significantly worse than true manual memory management anyhow; the GC still has to trace through objects in arenas at mark time, copy the objects within out into the tenured generation when they survive a minor collection, write barrier the objects, and so forth.)

† Note that I don’t mean you shouldn’t write Web frameworks and Web sites in Rust: in fact, I think Rust would be a fantastic language for many classes of Web server software, especially that which must scale to the highest loads and squeeze every ounce of performance out of the servers on the racks.

Comments