{"article":{"slug":"i-built-a-garbage-collector-for-a-language-that-doesnt-need-one","title":"I built a garbage collector for a language that doesn't need one","subtitle":null,"summary":"Clayton Ramsey describes building dumpster, a cycle-detecting garbage collector written in Rust for Rust, covering its reference-counting design, a concurrent implementation, benchmarks, and the fuzzing that caught subtle bugs.","content_type":"blog_post","language":"en","canonical_url":"https://claytonwramsey.com/blog/dumpster/","author":{"name":"Clayton Ramsey","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Clayton Ramsey","url":"https://claytonwramsey.com/","listing_slug":null,"listing":null},"topics":[{"name":"Rust","slug":"rust","url":"https://listedarticles.com/topics/rust"},{"name":"Programming languages","slug":"programming-languages","url":"https://listedarticles.com/topics/programming-languages"},{"name":"Memory management","slug":"memory-management","url":"https://listedarticles.com/topics/memory-management"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":6578,"reading_minutes":29,"published_at":"2023-08-14T00:00:00.000Z","added_at":"2026-10-22T20:12:12.570Z","updated_at":"2026-10-22T20:12:12.570Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/i-built-a-garbage-collector-for-a-language-that-doesnt-need-one","markdown_url":"https://listedarticles.com/articles/i-built-a-garbage-collector-for-a-language-that-doesnt-need-one.md","example":false,"citation":"Clayton Ramsey, Clayton Ramsey. \"I built a garbage collector for a language that doesn't need one.\" 14 Aug 2023. https://claytonwramsey.com/blog/dumpster/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://claytonwramsey.com/blog/dumpster/"},"body_markdown":"# I built a garbage collector for a language that doesn't need one\n\nIf carcinization happens when languages evolve to be more like Rust,\nthen what do you call it when Rust evolves to be more like Java?\nCaffeination?\n\nOver this summer, I’ve had a decent amount of time to kill. What better\nway to spend a beautiful hot summer than sitting inside, staring at core\ndumps in a supposedly memory-safe language? I built a garbage\ncollector - in short, a piece of software that manages allocations for\nanother, more exciting piece of software. The cool part: I made it in\nRust, for Rust - a language designed to eliminate garbage collection and\nwhich provides few facilities for making it work properly. Not only\nthat, I managed to make my garbage collector work with relatively few\ncompromises, which I’ll describe in further detail lower down.\n\nIf you don’t like reading, don’t care about the journey to implement it,\nor just want to get a sales pitch for the final result, check out the\nsource code on GitHub\n[here](https://github.com/claytonwramsey/dumpster). You can also\ndownload it directly from\n[crates.io](https://crates.io/crates/dumpster).\n\n## Background\n\nIf you’re familiar with the details of Rust and its standard library,\nfeel free to skip this section.\n\nThe core backing behind Rust’s memory model is *affine typing* and the\n*borrow checker*. Values may only be bound to one identifier at a time,\nand borrows (a.k.a. references) may not outlive the scope binding their\nreferent.\n\nFor example, the following code is invalid:\n\n```\nlet x = vec![1, 2, 3];\nlet y = x;\nprintln!(\"{x:?}\"); // compile error - x has already been moved\n```\n\nNormally, we work around this by borrowing against a binding, such as by\nmaking `y = &x` in the example above. However, we often need to share\nsome heap-allocated value without knowing which binding will live the\nlongest. The solution to this problem is shared ownership via garbage\ncollection.\n\nRust’s standard library offers two simple reference-counted garbage\ncollectors: the single-threaded\n[`Rc`](https://doc.rust-lang.org/std/rc/) and its atomically-indexed\ncounterpart [`Arc`](https://doc.rust-lang.org/std/sync/struct.Arc.html). They\noperate by maintaining a reference count in each heap allocation. Under\nmost circumstances, these work great, but they can’t handle cyclic\nreferences. Combined with interior mutability, it’s trivial to refute\nthem.\n\n```\nuse std::{cell::OnceCell, rc::Rc};\nstruct Foo(OnceCell>);\n\nlet x = Rc::new(Foo(OnceCell::new()));\nx.0.set(Rc::clone(&x));\n// My foo has a reference to itself. It can never be freed!\n```\n\nThis is why people actually get paid money to build garbage collectors.\nIf using a reference counter were all you needed, a number of people\nworking at Oracle would be out of a job.\n\n## Battle plan\n\nWe’d like to create some `Gc` data structure with a similar API to `Rc`\nand `Arc`, which can accept nearly any data type contained within, and\nstill manage to detect and collect cycles.\n\nWe have a few weapons at our disposal:\n\n- **`Drop`**: Every non-copiable data type in Rust can implement the\n `Drop` trait to ensure some code is called every time it is dropped.\n In our case, we can implement `Drop` for `Gc` to try to glean some\n knowledge about when an allocation becomes inaccessible.\n- **Traits**: We can construct some trait (in our case, let’s call it\n `Collectable`) as a mandatory requirement to be contained in a `Gc`.\n Creating this trait has some major downsides (libraries upstream of\n `dumpster` can’t implement it) but it’s a necessary evil.\n\nHowever, our formidable tools are matched by equally formidable\nchallenges:\n\n- **Undetectable moves**. When a value is moved in Rust, there is no\n way to detect that fact from within that value. If we had some sort\n of trait like `OnMove` which could allow for a function to be called\n every time it had moved, we could use it to detect when a `Gc` moved\n inside another `Gc`, making it unrooted, and allowing us to create a\n simple mark-sweep collector. At this rate, though, we would just\n reinvent C++’s copy constructors.\n- **Variable-sized data**. I foolishly decided to make it so that `Gc`\n could store `?Sized` types, which is more flexible for library users\n (enabling things like `Gc<[T]>`).\n- **Type erasure**. In a typical Rust program, generics are\n implemented via monomorphization, and no type information is\n retained at runtime. This makes it harder to clean up an allocation\n without prior context.\n\nWith these two, relatively simple tools, we have enough to build a\ncollector which can handle just about any data type inside.\n\n## My approach\n\nWe need to detect whether a `Gc` is reachable without actually scanning\nthe stack. I’ll start with a few definitions, using graph-theoretical\nlanguage.\n\n1. An allocation graph 𝐺=(𝑉,𝐸,𝑟) is a directed graph with a root\n node 𝑟∈𝑉 whose indegree is zero.\n2. A node 𝑣 in an allocation graph is said to be *accessible* if and\n only if there exists a path from 𝑟 to 𝑣 in the graph.\n\nIt should be clear to see why these definitions are useful to us. We can\nimagine each node being one allocation, pretending that all data not\nindirected through a `Gc` is part of an imaginary allocation for the\nroot. Additionally, each `Gc` acts as an edge connecting two\nallocations. If an allocation is accessible in the graph-theoretical\nsense, it’s still possible for a program to reach it, and if not, it’s\nsafe to free that allocation. Note that the indegree of a node is\nprecisely equal to the reference count of its corresponding allocation.\n\nI’ll roughly outline our approach to determining whether some node\n𝑛:≠𝑟 is accessible.\n\n1. Find 𝑊, the set of all descendants of 𝑛. Construct the subgraph\n 𝐻 of 𝐺 whose vertex set is 𝑊, preserving all edges connecting\n nodes in 𝑊.\n2. Find the set of nodes 𝐴⊆𝑊 for which the indegree of each\n 𝑎∈𝐴 in 𝐻 is *not* equal to its indegree in 𝐺.\n3. For each 𝑎∈𝐴, mark it and its descendants as accessible.\n4. If and only if 𝑛 was marked as accessible, it is accessible.\n\nHere’s a serpentine implementation in pseudocode, if that’s what you\nprefer.\n\n```\ndef is_accessible(n):\n counts = {n: n.indegree()}\n for (_, m) in n.edges():\n dfs(m, counts)\n\n reachable = set()\n for (a, count) in counts:\n if count != 0:\n mark(a, reachable)\n\n return n in reachable\n\ndef dfs(n, counts):\n if n not in counts.keys():\n counts[n] = n.indegree()\n for (_, m) in n.edges():\n dfs(m, counts)\n\n counts[n] -= 1\n\ndef mark(a, reachable):\n if a not in reachable:\n reachable.add(a)\n for (_, b) in a.edges():\n mark(b, reachable)\n```\n\nIt should be pretty clear to see that `is_accessible` runs in\n𝑂(|𝑉|+|𝐸|) time.\n\n### Reference counting with extra steps\n\nOur single-threaded `Gc` will behave much like an `Rc`, but with some\nminor details changed.\n\nFirst, we define a `Gc` and the allocation it points to, a `GcBox`.\n\n```\npub struct Gc {\n ptr: NonNull>\n}\n\n#[repr(C)]\nstruct GcBox {\n ref_count: Cell,\n value: T\n}\n```\n\nWe can then hook into the `Drop` behavior for our `Gc` to make it all\nwork.\n\n```\nimpl Drop for Gc {\n fn drop(&mut self) {\n let box_ref = unsafe { self.ptr.as_ref() };\n match box_ref.ref_count.get() {\n 0 => (),\n n => {\n box_ref.ref_count.set(n - 1);\n if n == 1 || !is_accessible(box_ref) {\n box_ref.ref_count.set(0);\n unsafe {\n drop_in_place(addr_of_mut!(ptr.as_mut().value));\n dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));\n }\n }\n }\n }\n }\n}\n```\n\nI, being very clever, decided to use a sentinel value of 0 for the\nreference count when an allocation is being cleaned up (to prevent\nspurious double-frees).\n\nHowever, this code has a problem - how the hell are we supposed to\nimplement `is_accessible`?\n\n### Trait hackery\n\nOur pseudocode for `is_accessible` required us to be able to access the\nset of edges going out from a node. Doing so is kind of hard. If we were\nwriting this in C, we would scan the allocation on the heap, looking for\ndata that looked like they could be pointers into other allocations. In\nRust, though, we can be a lot more precise by adding a small constraint\nto every garbage-collected type.\n\nIf the garbage collector wasn’t enough, we’re bringing the visitor\npattern over from Java. We force every garbage-collected value to\nimplement the `Collectable` trait, which will delegate some `Visitor` to\neach of its garbage-collected fields.\n\n```\npub struct Gc {\n // same as before ...\n}\n\npub trait Collectable {\n fn accept(&self, visitor: &mut V);\n}\n\npub trait Visitor {\n fn visit_gc(&mut self, gc: &Gc);\n}\n```\n\nFor example, an array might implement it by delegating to `accept` on\neach of its elements.\n\n```\nimpl Collectable for [T] {\n fn accept(&self, visitor: &mut V) {\n self.iter().for_each(|elem| elem.accept(visitor));\n }\n}\n```\n\nWe can now write code that finds the outgoing edges from each allocation\nby simply applying a visitor to the allocation. I ended up writing two\nvisitors - one for the `dfs` step and one for the `mark` step.\n\nI would have liked to make `Collectable` object-safe, but that would\nalso require `Visitor` to be object safe. That, in turn, would cause\nevery garbage collector to be coercible to `Gc`, which\nwould only be possible on nightly, making it impossible to write a\nstable crate.\n\n### Bulk dropping\n\nA cursory analysis of the implementation of `Drop` above shows that the\ncall to `is_accessible` runs in linear time with respect to the total\nnumber of `Gc`s existing. You would be excused for thinking that `drop`,\nas written, runs in linear time. However, the call to `drop_in_place`\ncould also result in another `Gc` being dropped, yielding a\nquadratic-time cleanup. This is unacceptable, especially since our first\ncall to `is_accessible` actually did all the work of determining whether\nthe allocations are reachable from the original one - if the original\nallocation being freed was inaccessible, any allocation referred to by\nit should also be inaccessible.\n\nWe can save our time on marking by a pretty simple method: we’ll do one\nmore pass through the reference graph, recording a pointer to each\nallocation to be destroyed and its implementation of `drop`. Then, once\nwe’ve found every inaccessible allocation, we’ll drop them all in one\nquick go.\n\nThere’s one final problem, though: each `Gc` owned by a dropped value\ncould itself try to manipulate the reference counts of its pointees,\nresulting in undefined behavior, or worse, slow code. However, all\nproblems in computer science can be solved by adding more state or more\nindirection. We opt to solve it with extra state this time, creating a\nthread-local value called `COLLECTING`.\n\nWhen we do a bulk-drop, we set `COLLECTING` to `true`. Then, when we\ncall `drop` on a `Gc`, it checks the state of `COLLECTING`. If\n`COLLECTING` is true, the `Gc` does nothing when dropped (not even\naffecting its reference count). To handle outbound edges to\nstill-accessible allocations, we add one more traversal before the final\ncleanup to handle outbound edges.\n\nLet’s take a look at what the code for that roughly looks like now.\n\n```\nthread_local! {\n static COLLECTING: Cell = Cell::new(false);\n}\n\nimpl Drop for Gc {\n fn drop(&mut self) {\n if COLLECTING.with(Cell::get) { return; }\n let box_ref = unsafe { self.ptr.as_ref() };\n match box_ref.ref_count.get() {\n 0 => (),\n 1 => {\n box_ref.ref_count.set(0);\n unsafe {\n drop_in_place(addr_of_mut!(ptr.as_mut().value));\n dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));\n }\n }\n n => {\n box_ref.ref_count.set(n - 1);\n unsafe { collect(self.ptr) };\n }\n }\n }\n}\n```\n\n`collect` is the function we’ll write to check if the allocation is\naccessible and perform a bulk cleanup if needed. There’s one more\nproblem before we can implement `collect`, though: our psuedocode\nrequired us to be able to store each allocation as a key in `counts` and\nalso to access the allocation’s neighbors. This means we have to use a\nlittle bit of type erasure to achieve our ends. I won’t go into too much\ndetail, but we need to be able to do two things:\n\n- Store pointers to allocations as keys in a hash-map.\n- Reconstruct a stored pointer using type information to make it\n possible to do work.\n\nDue to the limitations of Rust, these are actually mutually exclusive.\nBecause it’s undefined behavior (due to provenance issues) to compare\nthe raw data in pointers, we can’t erase a pointer and then use it as a\nkey in a hash-map. However, we can’t just get a pointer to the first\nbyte of the allocation, because our allocation could be `?Sized`.\n\nAs a result, my implementation actually has two different kinds of\nerased pointers: a thin pointer which can be used for comparisons and a\nfat pointer which can be used to reconstruct a pointer to any type.\n\n```\nstruct AllocationId(NonNull>); // used as a key in hash-maps\nstruct ErasedPtr([usize; 2]); // used as a reconstructible pointer to the allocation\n```\n\nThen, all the functions which need to know the type information of the\nallocation (such as `dfs` and `mark`) can be stored opaquely as function\npointers, and when called, they can “rehydrate” the `ErasedPtr` passed\nin with type information.\n\nBelow, I’ve included an example of how it can be used to implement\n`dfs`.\n\n```\nunsafe fn dfs(\n ptr: ErasedPtr,\n counts: &mut HashMap\n) {\n struct DfsVisitor<'a> {\n counts: &'a mut HashMap,\n }\n\n impl Visitor for DfsVisitor<'_> {\n fn visit_gc(&mut self, gc: &Gc) {\n let id = AllocationId::new(gc.ptr);\n\n if counts.insert(id, unsafe { gc.ptr.as_ref().ref_count.get() }) {\n (**gc).accept(self);\n }\n\n *counts.get_mut(&id).unwrap() -= 1;\n }\n }\n // pretend that `specify` converts the pointer back into NonNull\n let specified = ptr.specify::();\n specified.as_ref().accept(&mut DfsVisitor { counts });\n}\n```\n\nI won’t include the implementation of `collect` here because it’s\nlengthy and not even the final revision of the cleanup algorithm, but\nyou can trust me that it works. After much gnashing of teeth and tearing\nof hair, this is finally enough to achieve bulk dropping, making calling\n`drop()` on a `Gc` a linear-time operation.\n\n### Amortizing\n\nWhat’s that, you say? You need your reference operations to work in\n𝑂(1) time? Why are programmers these days so picky?\n\nLuckily, it isn’t too hard to make our garbage-collection efforts\nterminate in average-case 𝑂(1) time. Instead of calling `collect`\ndirectly, we’ll just punt the allocation, which may be inaccessible,\ninto a set of “dirty” allocations. In my code, I call that set a\ndumpster. Then, once every |𝐸| times an allocation is dropped, we’ll\ngo through the whole dumpster and collect them all in 𝑂(|𝐸|) time.\nAmortized across all allocations, that’s technically 𝑂(1), enabled by\nthe same accounting wizardry that makes array-backed lists useful and\nthat caused the 2008 financial crisis.\n\nTo save ourselves a little bit of work, whenever an allocation is\naccessed (such as by dereferencing or cloning), we can yank the\nallocation away from that same dirty set since it was just proven to be\naccessible.\n\n## Are we concurrent yet?\n\nSo far, the garbage collector I’ve been outlining to you has been a\nsingle-threaded collector, which can only store thread-local\ngarbage-collected values. I’m told that all code worth writing ends up\nbeing concurrent, so we have to do better than that. Lucky for us, this\nalgorithm can be made to operate concurrently with little effort,\nassuming that only one thread collects at a time.\n\nHowever, even if only one thread is collecting, we can still run into\nsome nasty concurrency issues. Let’s imagine that we have 2 allocations,\n𝑎 and 𝑏, plus the imaginary “root” allocation 𝑟, where 𝑎 can\nonly be accessed from 𝑟 and 𝑏 can only be accessed from 𝑎.\n\n![image](https://claytonwramsey.com/blog/dumpster/chain2.dot.svg)\n\nNow, consider performing a depth-first search starting from 𝑎. First,\nwe record that 𝑎 has 1 unaccounted-for-reference in `counts`. Then, we\nmove on to looking at 𝑏 because it’s one of 𝑎’s children.\n\nHowever, between when we record 𝑎’s reference count and examine 𝑏,\nanother malicious thread mutates 𝑏, adding a back-reference from 𝑏\nto 𝑎.\n\n![image](https://claytonwramsey.com/blog/dumpster/onecycle.dot.svg)\n\nThen, the depth-first search will return to 𝑎, decrement the number of\nunaccounted references, and assume that all incoming references to 𝑎\nand 𝑏 were totally accounted for (and therefore inaccessible). Then\nthe garbage collector would happily destroy 𝑎 and 𝑏’s allocations,\nleaving a dangling reference to the heap, potentially causing a\nuse-after-free or other gnarly memory errors.\n\n### Resolving concurrency\n\nThe simplest solution to this concurrency issue is to just wrap\neverything in a big fat lock by forcing every single operation involving\na `Gc` to acquire a single global mutex, preventing any sort of\nconcurrency bugs at all. However, that’s ridiculously slow.\n\nWe’d like to have an approach that only needs to achieve mutual\nexclusion over a small subset of all allocations if at all possible. To\ndo so, let’s take a closer look at our concurrency problem: we can see\nthat we only really get erroneous results when another thread mutates\nthe subgraph 𝐻 as we interact with it. The solution is quite clever -\nwe tag every `Gc` with a special number, which I’ll call a collecting\ntag.\n\nFirst, we’ll add a global atomic integer called the `COLLECTING_TAG`.\n\n```\nstatic COLLECTING_TAG: AtomicUsize = AtomicUsize::new(0);\n```\n\nWhenever we create or clone a new `Gc`, we’ll annotate it with the\ncurrent value of `COLLECTING_TAG`.\n\n```\n// this new `Gc` type is intended to be `Sync`.\n\npub struct Gc {\n ptr: NonNull>,\n tag: AtomicUsize,\n}\n\nimpl Gc {\n pub fn new(x: T) -> Gc {\n // (other bookkeeping hidden)\n\n Gc {\n ptr: /* initialization of GcBox */,\n tag: COLLECTING_TAG.load(Ordering::Relaxed),\n }\n }\n}\n```\n\nNext, at the start of the collection process, we’ll increment the value\nof `COLLECTING_TAG` just before we call `dfs`.\n\n```\nfn collect() {\n COLLECTING_TAG.fetch_add(1, Ordering::Relaxed);\n // carry on with DFS and such\n}\n```\n\nLastly, whenever we encounter a `Gc` during the `dfs` process, we’ll\ncheck its tag. If the tag is equal to the current value of\n`COLLECTING_TAG`, that means the `Gc` was created after `dfs` started.\nIf so, then whatever spot we found the `Gc` in must have been\naccessible, and we can mark it as so. To prevent us from visiting the\nsame edge twice (due to shenanigans), we’ll also update the tag on every\nedge we visit to the value of `COLLECTING_TAG`.\n\nLet’s return to our broken example to show how this modification fixes\nit. We return to our reference graph with 𝑎 pointing to 𝑏 and 𝑟\npointing to 𝑎. Since every `Gc` must be annotated with a tag, let’s\nsay they’re all tagged with 0.\n\n![](https://claytonwramsey.com/blog/dumpster/chain2labeled.dot.svg)\n\nNext, when `dfs` begins, `COLLECTING_TAG` is incremented to 1. As a\nresult, the new reference created by a malicious thread must be tagged\nwith 1.\n\n![](https://claytonwramsey.com/blog/dumpster/onecyclelabeled.dot.svg)\n\nNow, when `dfs` visits the edge pointing from 𝑏 to 𝑎, it sees that\nthe reference is labeled with a tag of 1, and therefore both 𝑏 and 𝑎\nmust be accessible - no accidental early deallocations here.\n\n### Moving in and out\n\nWe might hope that tagging the pointers is sufficient to prevent all\nconcurrency bugs. However, this is sadly not enough. To show why, we’ll\nbegin with an example.\n\nFirst, let’s imagine an allocation called 𝑥, which contains two\noptional references to itself.\n\n```\nstruct X {\n x1: Mutex>>,\n x2: Mutex>>,\n}\n```\n\nAt the start of our example, there will be only one `Gc` pointing from\ninside 𝑥 to itself, and the other slot that can hold a `Gc` will be\nempty. 𝑥 is accessible directly from the root allocation 𝑟, and all\nexisting references are tagged with 0. For the sake of clarity, I’ll\ndraw the arrow representing the first slot in 𝑥 with a solid line and\nthe second slot with a dashed line.\n\n![](https://claytonwramsey.com/blog/dumpster/dash0.dot.svg)\n\nNow, let’s have `dfs` begin, starting at 𝑥.\n\n1. We increment `COLLECTING_TAG` to 1.\n2. `dfs` records that 𝑥 has 2 unaccounted-for references at the\n start.\n3. `dfs` visits the 𝑥’s first slot and tags the currently-existing\n self reference in that slot. 𝑥 now has 1 unaccounted-for\n reference.\n\n ![image](https://claytonwramsey.com/blog/dumpster/dash1.dot.svg)\n4. A malicious thread intervenes, first moving the `Gc` from 𝑥’s\n first slot to 𝑟, then moving the original `Gc` which connected 𝑟\n to 𝑥 into 𝑥’s second slot.\n\n ```\n fn do_evil(r_to_x: Gc) {\n let z = std::mem::take(&mut *r_to_x.x1.lock().unwrap());\n *z.x2.lock().unwrap() = r_to_x;\n }\n ```\n\n ![image](https://claytonwramsey.com/blog/dumpster/dash2.dot.svg)\n5. `dfs` continues, now visiting the second slot in 𝑥. Seeing another\n reference to 𝑥, we decrement the number of unaccounted-for\n references to 0.\n6. `dfs` found no ancestors of 𝑥 with unaccounted-for ancestors, so\n we free 𝑥. However, 𝑥 is still accessible!\n\nThis problem stumped me for a decent while. It seems impossible to\nprevent other threads from do-si-do-ing every `Gc` pointing to an\nallocation in order to fool our search. Luckily, there is a way through.\nSince tagging every `Gc` worked out for us before, we’ll try tagging\nevery allocation.\n\n```\n#[repr(C)]\nstruct GcBox {\n ref_count: AtomicUsize,\n tag: AtomicUsize,\n value: T\n}\n```\n\nNext, every time a `Gc` is dereferenced, we’ll update the tag in the\nallocation to the current value of `COLLECTING_TAG`.\n\n```\nimpl std::ops::Deref for GcBox {\n type Target = T;\n\n fn deref(&self) -> &Self::Target {\n let box_ref: &GcBox = unsafe { self.ptr.as_ref() };\n box_ref.tag.store(COLLECTING_TAG.load(Ordering::Acquire), Ordering::Release);\n &box_ref.value\n }\n}\n```\n\nWhenever `dfs` observes that the tag on an allocation is equal to\n`COLLECTING_TAG`, that means that the allocation was accessed, and\ntherefore accessible. In order to shuffle references around in our above\nexample, the malicious thread would have to dereference a `Gc`,\nnotifying the search and preventing an early deallocation.\n\nIn fact, this is enough to prove that `dfs` will *never* incorrectly\nmark an allocation as inaccessible, even under concurrent execution.\nThis blog post is already rather long, so I’ll only provide a rough\nsketch of the proof.\n\n**Theorem: `dfs` will never erroneously mark an allocation as\ninaccessible.**\n\nProof:\n\n1. If `dfs` encounters a `Gc` created after `dfs` begins, it will know\n that the referent is accessible.\n2. Due to (1), if `dfs` marked some allocation 𝑎 as inaccessible, it\n must have only visited `Gc`s pointing to 𝑎 which existed before\n `dfs` began.\n3. Weakening the statement from (2), if `dfs` marked some allocation\n 𝑎 as inaccessible, it must have only visited `Gc`s pointing to 𝑎\n which existed when 𝑎’s reference count was recorded.\n4. `dfs` never visits a `Gc` while it points from the root allocation\n 𝑟 to any other allocation.\n5. `dfs` must visit every `Gc` which pointed to an allocation at the\n point when its reference count was recorded in order to mark it as\n inaccessible.\n6. Due to (4) and (5), if 𝑎 is marked as inaccesssible, any `Gc`\n which at any point connected 𝑟 to 𝑎 must have been moved to\n connect another node (not 𝑟) to 𝑎.\n7. Due to (6), there is no lifetime `'x` which can borrow against a\n `Gc` pointing from 𝑟 to 𝑎 and last between when `dfs` first\n visits 𝑎 and when it last visits 𝑎.\n8. The final `Gc` to move into 𝑎 before `dfs` must have been moved\n while another borrow against a `Gc` pointing from 𝑟 to 𝑎\n existed. Let the lifetime of that borrow be `'y`.\n9. Because `'y` lasts longer than the final move, `'y` can be extended\n to last arbitrarily long, even until after `dfs` has finished\n visiting every `Gc` pointing to 𝑎.\n10. Due to (7), `'y` must not have existed before `dfs` first visited\n 𝑎. Therefore, if 𝑎 is erroneously marked as inaccessible, a `Gc`\n pointing to 𝑎 must have been dereferenced to generate a borrow\n with lifetime `'y`.\n11. If a `Gc` pointing to 𝑎 was dereferenced before the last time\n `dfs` visited a `Gc` pointing to 𝑎, then `dfs` would have observed\n that 𝑎’s tag had changed. Therefore, if an allocation was\n erroneously marked as inaccessible, it must have been marked as\n accessible. Therefore no allocations were ever erroneously marked as\n inacessible by `dfs`. QED.\n\nThis proof is relatively handwavy, but it should be possible for an\nastute reader to fill in the details. I will leave it to such astute\nreaders to prove the complementary proof to this; namely, that `dfs`\nwill never erroneously mark an allocation as accessible.\n\nI also think that it’s really cool that the entire mechanism of the\ncorrectness of this approach is totally supported by Rust’s borrow\nchecking semantics. It makes the whole thing feel like it fits right in.\n\n### It’s the weak ones that count\n\nThere’s one more cause for memory safety issues from concurrency. If an\nallocation is freed because its reference count reached zero, it could\nstill be accessible by another thread because it was stored in the\nglobal dumpster. We can’t guarantee that we’ve obliterated all\nreferences to that allocation from every other thread’s memory, so it\nseems like we’re hosed.\n\nHowever, there’s no problem in computer science that can’t be solved by\nadding more state. Taking a leaf from `Rc`’s book and adapting it\nliberally, we annotate each allocation with a “weak” reference count,\nwhich is the number of times it’s referenced by a dumpster or cleanup\nthread. We’ll rename our original reference count to be the strong count\ninstead.\n\n```\n#[repr(C)]\nstruct GcBox {\n strong: AtomicUsize,\n weak: AtomicUsize,\n tag: AtomicUsize,\n value: T,\n}\n```\n\nThen, when dropping the last strong reference to a `Gc`, we first check\nthat its weak reference count is nonzero before we can deallocate it. If\nnot, it’s the cleanup threads’ problem to take care of it.\n\nWhenever an allocation is removed from a dumpster and about to be thrown\naway by a thread running a cleanup procedure, the thread decrements the\nweak count of the allocation and checks if both the weak and strong\ncount have reached zero. If so, that thread can then safely destroy the\nallocation.\n\n### Deadlocked!\n\nImagine that we want to create a `Gc>`, and then drop a `Gc`\npointing to it while the `Mutex` is locked.\n\n```\nlet gc1 = Gc::new(Mutex::new(()));\nlet gc2 = gc1.clone();\n\nlet guard = gc1.lock()?;\ndrop(gc2); // suppose this triggers a cleanup\ndrop(guard);\n```\n\nWhile traversing the reference graph, the `dfs` visitor would attempt to\nvisit the mutex, lock it, and try to carry on. However, since the same\nthread that triggered the allocation still holds a guard to that mutex,\nthe thread would deadlock disastrously. Lucky for us, we know that any\nallocation with a held mutex guard must still be accessible (due to\n`Mutex`’s excellent API), so we can be certain that if we fail to\nacquire a mutex, we have immediate proof that an allocation is\naccessible.\n\nTo take advantage of that, we’ll make visiting a collectable type a\nfallible operation, and make it so that failing to acquire a lock also\nfails the visit.\n\n```\npub trait Collectable {\n fn accept(&self, visitor: &mut V) -> Result<(), ()>;\n}\n\npub trait Visitor {\n fn visit_gc(&mut self, gc: &Gc) -> Result<(), ()>;\n}\n\nimpl Collectable for Mutex {\n fn accept(&self, visitor: &mut V) -> Result<(), ()> {\n // pretend poison errors don't exist\n self.try_lock().map_err(|_| ())?.accept(visitor);\n Ok(())\n }\n}\n```\n\n### Sharing your dumpsters\n\n![A hand-drawn garbage truck in ink on a white background. It’s crudelydone, as if drawn by the sort of person who knows what perspective isbut doesn’t quite understand how itworks.](https://claytonwramsey.com/blog/dumpster/garbagetruck.jpg)\n\nYou’ve made it this far into this (admittedly rather lengthy) post.\nEnjoy this hand-drawn picture by yours truly.\n\nWhen implementing this garbage collector, one of the biggest bottlenecks\nwith concurrent performance is accessing the one, global dumpster every\nsingle time a `Gc` is dropped. If using a `Mutex`, this will\nremove nearly all parallelism from the whole system and make you wonder\nwhy you paid all that money for a 16-core computer.\n\nAs a result, any sane person might lean for a concurrent hashmap. There\nare many Rust implementations - I tried\n[`chashmap`](https://gitlab.redox-os.org/redox-os/chashmap) but gave up\non it due to a [rare panic\nbug](https://gitlab.redox-os.org/redox-os/chashmap/-/issues/3), and then\nI tried [`dashmap`](https://github.com/xacrimon/dashmap), which worked\nfine but was too slow as thread counts increased.\n\nThe heart of the issue is that concurrently updating any data structure\nis going to be slow. Even so-called “concurrent” data structures which\nuse clever sharded locks have this issue - there’s always some\ncontention overhead. The best workaround to concurrency slowdowns is to\njust not do things concurrently. We can fix this by making every thread\nhave its own dumpster, and then having a global collection of\nto-be-cleaned allocations which I’ll call the *garbage truck*. Whenever\nanother allocation is marked dirty, we can check if this thread’s\ndumpster is full according to some heuristic, and if so, transfer all\nthe allocations from this thread’s dumpster to the garbage truck. I’ve\nincluded some pseudocode for the whole process below.\n\n```\ndumpster = set() # local to this thread\ngarbage_truck = mutex(set()) # global to all threads\n\ndef mark_dirty(allocation):\n dumpster.add(allocation)\n if is_full(dumpster):\n garbage_truck.lock()\n for trash_bag in dumpster:\n garbage_truck.add(trash_bag)\n garbage_truck.unlock()\n dumpster = set()\n```\n\nIf `is_full` returns `true` rarely enough, there will be almost no\ncontention over the garbage truck. This means that the concurrency\noverhead is vastly reduced and we get to pocket some great performance\nreturns.\n\n## Okay, but how fast is it?\n\nIn short, this garbage collector runs pretty fast!\n\nIn the end, I made two different garbage collector implementations - one\nwhich is thread-local, saving us from all the concurrency headaches, and\nanother thread-safe one that has all the bells and whistles at the cost\nof some performance. Borrowing from\n[`once_cell`](https://github.com/matklad/once_cell)’s API, the former\nlives in the `unsync` module of the crate and the latter in `sync`.\n\nNext, I collected all the garbage collectors I could find in order to\ncompare them. I selected all the ones which had a similar API to\n`dumpster`, were published on [crates.io](https://crates.io), and\nactually worked.\n\n| Name | Concurrent? | Like `dumpster`? |\n| --- | --- | --- |\n| `dumpster` (unsync) | ❌ | ✅ |\n| `dumpster` (sync) | ✅ | ✅ |\n| [`Rc`](https://doc.rust-lang.org/std/rc/struct.Rc.html) | ❌ | ✅ |\n| [`Arc`](https://doc.rust-lang.org/std/sync/struct.Arc.html) | ✅ | ✅ |\n| [`bacon-rajan-cc`](https://github.com/fitzgen/bacon-rajan-cc) | ❌ | ✅ |\n| [`cactusref`](https://github.com/artichoke/cactusref) | ❌ | ❌ |\n| [`elise`](https://github.com/wusyong/elise) | ✅ | ❌ |\n| [`gc`](https://github.com/Manishearth/rust-gc) | ❌ | ✅ |\n| [`gcmodule`](https://github.com/quark-zju/gcmodule) | yes, but with a different API | ✅ |\n| [`rcgc`](https://crates.io/crates/rcgc) | ❌ | ❌ |\n| [`shredder`](https://github.com/Others/shredder) | ✅ | ✅ |\n\nI excluded the ones that didn’t have a `dumpster`-like API because it\nwould have been a pain to set up a benchmarking harness to handle them.\nIf you feel this is poor diligence, you can go benchmark them yourself.\nI also included `Rc` and `Arc`, even though they don’t collect cycles,\nbecause they’re a decent baseline for the minimum performance of a\ngarbage collector. During my research, I also found that\n`bacon-rajan-cc` doesn’t initiate collections of its own accord, so I\nadded a version of each of `dumpster`’s garbage collectors which doesn’t\nautomatically trigger collections in the spirit of competitive fairness.\nThose versions are labeled as “manual.” Lastly, I found that `gcmodule`\nsimply stack-overflows and sometimes segfaults when facing extremely\nlarge collection loads, so I removed it from the benchmark set.\n\nAs my benchmark, I decided to do the very simplest thing I could think\nof: have a bunch of allocations randomly add and remove references to\neach other in a loop, dropping and creating new allocations as well. To\naccount for random noise, I ran 100 trials of each garbage collector\ndoing 1 million operations. Each operation is either the creation of a\nreference or a deletion.\n\nFirst, I ran a benchmark of all the garbage collectors, measuring pure\nsingle-threaded performance. I’ve shown my benchmark results as a set of\nviolin plots below, relating runtime to frequency.\n\n![A violin plot, titled “Single-threaded GC comparison.” The x-axis islabeled “Runtime for 1M ops (ms),” and the y-axis is labeled “Garbagecollector,” with various collectors labeled on the ticks. In order, thegarbage collectors on the y-axis are Arc, Rc, shredder, bacon-rajan-cc,gc, dumpster (sync/manual), dumpster (sync), dumpster (unsync/manual),and dumpster (unsync). The x-axis ranges from 0 ms to 4000 ms. All ofthe violins, except for shredder’s, are very near to the left side. Theviolin labeled “shredder” is far off to the right side, with a mean ofroughly 3700ms.](https://claytonwramsey.com/blog/dumpster/single_threaded.png)\n\nThis plot doesn’t tell us much other than that `shredder` is slow. To\ntake a closer look, let’s remove `shredder` from the list and see what\nwe find.\n\n![The same violin plot as before, but now shredder’s violin and y-axislabel have been removed. The x-axis now varies from 40 to 160 ms. Theviolin labeled Rc is furthest to the left, followed by Arc,bacon-rajan-cc, dumpster (unsync), dumpster (unsync/manual), dumpster(sync/manual), gc, and finally dumpster(sync).](https://claytonwramsey.com/blog/dumpster/single_threaded_sans_shredder.png)\n\n`dumpster`’s unsync implementation is in a decent position, beat out\nonly by the non-cycle-detecting allocators and `bacon-rajan-cc`.\n`bacon-rajan-cc` has very little overhead and is quite performant.\n\nI think there are two main reasons why the concurrent version of the\ngarbage collector is much slower than the single-threaded one. First,\nmoving allocations from a thread-local dumpster to the global garbage\ntruck takes some time. Second, the `dfs` operation in a concurrent\nenvironment must record the current set of children of an allocation,\ntypically in a separate heap-allocated structure, to prevent some\nconcurrency bugs. It’s certainly possible to mitigate the losses from\nthe first issue, but the second is harder to handle.\n\nMy guess as to why the concurrent version is significantly slower when\nusing automatic collection triggering is that it’s a consequence of my\ntesting harness. Currently, it runs all the tests in a loop, so the\nsingle-threaded benchmark could run directly after the multi-threaded\none and be forced to clean up some of its garbage.\n\nIn any event, let’s move on to the results from the multi-threaded\nbenchmark.\n\n![A scatter plot, titled “Parallel garbage collector scaling.” Thex-axis is labeled “Number of threads” and varies from 1 to 16. They-axis is labeled “Time for 1M ops (ms)” and varies from 0 to 3500. Onthe legend, there are four series: dumpster (sync), dumpster(sync/manual), shredder, and Arc. The points associated with shredder’sseries start out at 3500ms for 1 thread, scaling asymptotically down toroughly 1800ms at 6 threads. All other points are very close tozero.](https://claytonwramsey.com/blog/dumpster/scaling.png)\n\nThe only other concurrent garbage collector available for me to test\nagainst was `shredder`, and it looks like it wasn’t much of a\ncompetition.\n\n![A scatter plot, titled “Parallel garbage collector scaling (sansshredder).” The x-axis remains the same as before, but now the y-axisonly goes up to 200ms. “shredder” has been removed from the legend, butotherwise it is the same as the previous image. The points associatedwith dumpster (sync) and dumpster (sync/manual) start out at roughly 80ms for 1 thread, jump up to about 110 ms for 2 threads, then decreaseasymptotically to around 70 ms for 16 threads. Meanwhile, the pointsassociated with Arc start out at roughly 70 ms for 1 thread and decreaseasymptotically with the thread count to around 25 ms for 15threads.](https://claytonwramsey.com/blog/dumpster/scaling_sans_shredder.png)\n\n`dumpster` doesn’t scale as smoothly as I’d like with thread count, but\nit’s a relief that performance does actually improve with thread count,\nexcept for the jump from one thread to two. I think being only 3x slower\nthan Arc is a decent victory, especially for a project that I wasn’t\npaid any money to do. I’m not much of an expert at high-performance\ncomputing in concurrent situations, so trying to optimize this further\nwould likely just be an adventure in trying random things and seeing if\nthey yield an improvement. If anyone out there has clever ideas on how\nto optimize this approach, let me know! My email is on the “About” page.\n\n## Coda\n\nOver the last few months, I built a garbage collector for Rust from\nscratch. I implemented a novel (ish) algorithm of my own design, got it\nto work in both single-threaded and multi-threaded contexts, and showed\nthat it was actually pretty performant.\n\nThe implementation of this crate is now [up on\ncrates.io](https://crates.io/crates/dumpster) and available for anyone\nto download. It’s licensed under the GNU GPLv3.\n\nSpecial thanks to [Wisha](https://wisha.page/),\n[Charlie](https://seniormars.com/), and\n[Shreyas](https://shreyasminocha.me/) for reviewing this post, fielding\nmy bad questions, and putting up with me rambling about this for nearly\ntwo months straight.\n\n## Postscript\n\nI have a few things that I thought were interesting along the way but\ndidn’t quite have a good spot to include in the story above, so they’ll\nall be mish-mashed in here.\n\n### Ode to bad good ideas\n\nThe final, polished solution you see in this blog post is actually quite\nfar from my original idea. In particular, almost all of my first ideas\nfor handling concurrency didn’t work. Here’s a quick roll of them all:\n\n- Wrap a `Mutex` around every single allocation’s reference count and\n hold them while doing `dfs`\n- Save on space in `Gc`s by tagging only the lowest bit instead of\n adding an entire `usize`\n- Make everything enable dynamic dispatch so we can have real\n Java-like objects\n- Clean up allocations locally on every thread\n- Avoid directly dropping allocations and instead cleverly decrement\n their reference count\n\n### Cool nightly tricks\n\n`Rc` and the other pointer types are somewhat “blessed” in that they can\naccess nightly features from the Rust compiler and still be consumed by\nstable projects. `dumpster` has no such blessings.\n\nI would like to implement `CoerceUnsized` unconditionally for all my\ngarbage collectors, but that’s simply not possible on stable yet.\n\nLikewise, pending the implementation of strict provenance, there’s\nactually no way for a stable crate to manipulate the address portion of\na fat pointer. This means that even if I found some space optimization\nusing lower bit tagging, I wouldn’t be able to use it because it’s gated\nbehind a nightly feature.\n\n### Another path to `Gc`\n\nWithout the ability to coerce `Gc` as an unsized type, I can’t make\n`Collectable` object safe due to the function signature of `accept`,\nwhich forces `Visitor` to also be object-safe, forcing `visit`\noperations to also be object-safe.\n\nI’ve thought of a slightly different approach, though. We can make\n`Visitor` a single concrete type, and that makes `Collectable` trivially\nobject-safe. The downside here is that I would then have to store all 5\nof my current visitor implementations in the same structure, and that\nloses a lot of my nice type safety features and adds a large runtime\npenalty. I’m not very happy with that idea, though.\n\n### Miri rules\n\nI would probably not have been able to finish this project without\n[`cargo miri`](https://github.com/rust-lang/miri). If you haven’t heard\nof it, you should download it right now and run all of your Rust\nprojects with it. It’s such a fantastic tool for debugging unsafe code\nthat I wish I could have it in other languages, too - valgrind is a poor\nsubstitute for it when using C.\n\n### Testing and debugging\n\nEarly on, I had just a few handwritten tests. The first reference graph\nthat I found that gave me trouble looked like this:\n\n![](https://claytonwramsey.com/blog/dumpster/test4.dot.svg)\n\nHowever, once I had simple graphs with multiple cycles down, it was hard\nto come up with new tests. As a result, I resorted to fuzzing, using the\nsame approach as my benchmark - randomly generating references and then\nseeing if they got cleaned up properly.\n\nDebugging the results of those fuzzed tests absolutely sucked, though.\nThe experience of trying to find the source of an issue was awful, so I\nended up having to make some (crude) tools to make the process easier.\nEventually, I had settled on printing out the reference graph at choice\ntimes during the run of my tests and then visualizing them to get a good\nguess of what was wrong. However, when making the concurrent\nimplementation, printing something can change the execution behavior of\nthe program. Not only that, it’s not always obvious what the issue is. I\nhad one bug which only occurred after several thousand operations had\ncompleted, resulting in reference graphs that looked like this:\n\n![](https://claytonwramsey.com/blog/dumpster/evil.dot.svg)\n\nThe graph above was made by fuzzing my garbage collector, using the same\napproach as my benchmarks.\n","body_html":"

I built a garbage collector for a language that doesn't need one

\n

If carcinization happens when languages evolve to be more like Rust,\nthen what do you call it when Rust evolves to be more like Java?\nCaffeination?

\n

Over this summer, I’ve had a decent amount of time to kill. What better\nway to spend a beautiful hot summer than sitting inside, staring at core\ndumps in a supposedly memory-safe language? I built a garbage\ncollector - in short, a piece of software that manages allocations for\nanother, more exciting piece of software. The cool part: I made it in\nRust, for Rust - a language designed to eliminate garbage collection and\nwhich provides few facilities for making it work properly. Not only\nthat, I managed to make my garbage collector work with relatively few\ncompromises, which I’ll describe in further detail lower down.

\n

If you don’t like reading, don’t care about the journey to implement it,\nor just want to get a sales pitch for the final result, check out the\nsource code on GitHub\nhere. You can also\ndownload it directly from\ncrates.io.

\n

Background

\n

If you’re familiar with the details of Rust and its standard library,\nfeel free to skip this section.

\n

The core backing behind Rust’s memory model is affine typing and the\nborrow checker. Values may only be bound to one identifier at a time,\nand borrows (a.k.a. references) may not outlive the scope binding their\nreferent.

\n

For example, the following code is invalid:

\n
let x = vec![1, 2, 3];\nlet y = x;\nprintln!("{x:?}"); // compile error - x has already been moved
\n

Normally, we work around this by borrowing against a binding, such as by\nmaking y = &x in the example above. However, we often need to share\nsome heap-allocated value without knowing which binding will live the\nlongest. The solution to this problem is shared ownership via garbage\ncollection.

\n

Rust’s standard library offers two simple reference-counted garbage\ncollectors: the single-threaded\nRc and its atomically-indexed\ncounterpart Arc. They\noperate by maintaining a reference count in each heap allocation. Under\nmost circumstances, these work great, but they can’t handle cyclic\nreferences. Combined with interior mutability, it’s trivial to refute\nthem.

\n
use std::{cell::OnceCell, rc::Rc};\nstruct Foo(OnceCell<Rc<Foo>>);\n\nlet x = Rc::new(Foo(OnceCell::new()));\nx.0.set(Rc::clone(&x));\n// My foo has a reference to itself. It can never be freed!
\n

This is why people actually get paid money to build garbage collectors.\nIf using a reference counter were all you needed, a number of people\nworking at Oracle would be out of a job.

\n

Battle plan

\n

We’d like to create some Gc data structure with a similar API to Rc\nand Arc, which can accept nearly any data type contained within, and\nstill manage to detect and collect cycles.

\n

We have a few weapons at our disposal:

\n

  • Drop: Every non-copiable data type in Rust can implement the

    Drop trait to ensure some code is called every time it is dropped.\nIn our case, we can implement Drop for Gc to try to glean some\nknowledge about when an allocation becomes inaccessible.

  • Traits: We can construct some trait (in our case, let’s call it

    Collectable) as a mandatory requirement to be contained in a Gc.\nCreating this trait has some major downsides (libraries upstream of\ndumpster can’t implement it) but it’s a necessary evil.

\n

However, our formidable tools are matched by equally formidable\nchallenges:

\n

  • Undetectable moves. When a value is moved in Rust, there is no

    way to detect that fact from within that value. If we had some sort\nof trait like OnMove which could allow for a function to be called\nevery time it had moved, we could use it to detect when a Gc moved\ninside another Gc, making it unrooted, and allowing us to create a\nsimple mark-sweep collector. At this rate, though, we would just\nreinvent C++’s copy constructors.

  • Variable-sized data. I foolishly decided to make it so that Gc

    could store ?Sized types, which is more flexible for library users\n(enabling things like Gc<[T]>).

  • Type erasure. In a typical Rust program, generics are

    implemented via monomorphization, and no type information is\nretained at runtime. This makes it harder to clean up an allocation\nwithout prior context.

\n

With these two, relatively simple tools, we have enough to build a\ncollector which can handle just about any data type inside.

\n

My approach

\n

We need to detect whether a Gc is reachable without actually scanning\nthe stack. I’ll start with a few definitions, using graph-theoretical\nlanguage.

\n

  1. An allocation graph 𝐺=(𝑉,𝐸,𝑟) is a directed graph with a root

    node 𝑟∈𝑉 whose indegree is zero.

  2. A node 𝑣 in an allocation graph is said to be accessible if and

    only if there exists a path from 𝑟 to 𝑣 in the graph.

\n

It should be clear to see why these definitions are useful to us. We can\nimagine each node being one allocation, pretending that all data not\nindirected through a Gc is part of an imaginary allocation for the\nroot. Additionally, each Gc acts as an edge connecting two\nallocations. If an allocation is accessible in the graph-theoretical\nsense, it’s still possible for a program to reach it, and if not, it’s\nsafe to free that allocation. Note that the indegree of a node is\nprecisely equal to the reference count of its corresponding allocation.

\n

I’ll roughly outline our approach to determining whether some node\n𝑛:≠𝑟 is accessible.

\n

  1. Find 𝑊, the set of all descendants of 𝑛. Construct the subgraph

    𝐻 of 𝐺 whose vertex set is 𝑊, preserving all edges connecting\n nodes in 𝑊.

  2. Find the set of nodes 𝐴⊆𝑊 for which the indegree of each

    𝑎∈𝐴 in 𝐻 is not equal to its indegree in 𝐺.

  3. For each 𝑎∈𝐴, mark it and its descendants as accessible.
  4. If and only if 𝑛 was marked as accessible, it is accessible.
\n

Here’s a serpentine implementation in pseudocode, if that’s what you\nprefer.

\n
def is_accessible(n):\n    counts = {n: n.indegree()}\n    for (_, m) in n.edges():\n        dfs(m, counts)\n\n    reachable = set()\n    for (a, count) in counts:\n        if count != 0:\n            mark(a, reachable)\n\n    return n in reachable\n\ndef dfs(n, counts):\n    if n not in counts.keys():\n        counts[n] = n.indegree()\n        for (_, m) in n.edges():\n            dfs(m, counts)\n\n    counts[n] -= 1\n\ndef mark(a, reachable):\n    if a not in reachable:\n        reachable.add(a)\n        for (_, b) in a.edges():\n            mark(b, reachable)
\n

It should be pretty clear to see that is_accessible runs in\n𝑂(|𝑉|+|𝐸|) time.

\n

Reference counting with extra steps

\n

Our single-threaded Gc will behave much like an Rc, but with some\nminor details changed.

\n

First, we define a Gc and the allocation it points to, a GcBox.

\n
pub struct Gc<T: ?Sized> {\n    ptr: NonNull<GcBox<T>>\n}\n\n#[repr(C)]\nstruct GcBox<T: ?Sized> {\n    ref_count: Cell<usize>,\n    value: T\n}
\n

We can then hook into the Drop behavior for our Gc to make it all\nwork.

\n
impl<T: ?Sized> Drop for Gc<T> {\n    fn drop(&mut self) {\n        let box_ref = unsafe { self.ptr.as_ref() };\n        match box_ref.ref_count.get() {\n            0 => (),\n            n => {\n                box_ref.ref_count.set(n - 1);\n                if n == 1 || !is_accessible(box_ref) {\n                    box_ref.ref_count.set(0);\n                    unsafe {\n                        drop_in_place(addr_of_mut!(ptr.as_mut().value));\n                        dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));\n                    }\n                }\n            }\n        }\n    }\n}
\n

I, being very clever, decided to use a sentinel value of 0 for the\nreference count when an allocation is being cleaned up (to prevent\nspurious double-frees).

\n

However, this code has a problem - how the hell are we supposed to\nimplement is_accessible?

\n

Trait hackery

\n

Our pseudocode for is_accessible required us to be able to access the\nset of edges going out from a node. Doing so is kind of hard. If we were\nwriting this in C, we would scan the allocation on the heap, looking for\ndata that looked like they could be pointers into other allocations. In\nRust, though, we can be a lot more precise by adding a small constraint\nto every garbage-collected type.

\n

If the garbage collector wasn’t enough, we’re bringing the visitor\npattern over from Java. We force every garbage-collected value to\nimplement the Collectable trait, which will delegate some Visitor to\neach of its garbage-collected fields.

\n
pub struct Gc<T: Collectable + ?Sized> {\n   // same as before ...\n}\n\npub trait Collectable {\n    fn accept<V: Visitor>(&self, visitor: &mut V);\n}\n\npub trait Visitor {\n    fn visit_gc<T: Collectable + ?Sized>(&mut self, gc: &Gc<T>);\n}
\n

For example, an array might implement it by delegating to accept on\neach of its elements.

\n
impl<T: Collectable> Collectable for [T] {\n    fn accept<V: Visitor>(&self, visitor: &mut V) {\n        self.iter().for_each(|elem| elem.accept(visitor));\n    }\n}
\n

We can now write code that finds the outgoing edges from each allocation\nby simply applying a visitor to the allocation. I ended up writing two\nvisitors - one for the dfs step and one for the mark step.

\n

I would have liked to make Collectable object-safe, but that would\nalso require Visitor to be object safe. That, in turn, would cause\nevery garbage collector to be coercible to Gc<dyn Collectable>, which\nwould only be possible on nightly, making it impossible to write a\nstable crate.

\n

Bulk dropping

\n

A cursory analysis of the implementation of Drop above shows that the\ncall to is_accessible runs in linear time with respect to the total\nnumber of Gcs existing. You would be excused for thinking that drop,\nas written, runs in linear time. However, the call to drop_in_place\ncould also result in another Gc being dropped, yielding a\nquadratic-time cleanup. This is unacceptable, especially since our first\ncall to is_accessible actually did all the work of determining whether\nthe allocations are reachable from the original one - if the original\nallocation being freed was inaccessible, any allocation referred to by\nit should also be inaccessible.

\n

We can save our time on marking by a pretty simple method: we’ll do one\nmore pass through the reference graph, recording a pointer to each\nallocation to be destroyed and its implementation of drop. Then, once\nwe’ve found every inaccessible allocation, we’ll drop them all in one\nquick go.

\n

There’s one final problem, though: each Gc owned by a dropped value\ncould itself try to manipulate the reference counts of its pointees,\nresulting in undefined behavior, or worse, slow code. However, all\nproblems in computer science can be solved by adding more state or more\nindirection. We opt to solve it with extra state this time, creating a\nthread-local value called COLLECTING.

\n

When we do a bulk-drop, we set COLLECTING to true. Then, when we\ncall drop on a Gc, it checks the state of COLLECTING. If\nCOLLECTING is true, the Gc does nothing when dropped (not even\naffecting its reference count). To handle outbound edges to\nstill-accessible allocations, we add one more traversal before the final\ncleanup to handle outbound edges.

\n

Let’s take a look at what the code for that roughly looks like now.

\n
thread_local! {\n    static COLLECTING: Cell<bool> = Cell::new(false);\n}\n\nimpl<T: Collectable + ?Sized> Drop for Gc<T> {\n    fn drop(&mut self) {\n        if COLLECTING.with(Cell::get) { return; }\n        let box_ref = unsafe { self.ptr.as_ref() };\n        match box_ref.ref_count.get() {\n            0 => (),\n            1 => {\n                box_ref.ref_count.set(0);\n                unsafe {\n                    drop_in_place(addr_of_mut!(ptr.as_mut().value));\n                    dealloc(ptr.as_ptr().cast(), Layout::for_value(ptr.as_ref()));\n                }\n            }\n            n => {\n                box_ref.ref_count.set(n - 1);\n                unsafe { collect(self.ptr) };\n            }\n        }\n    }\n}
\n

collect is the function we’ll write to check if the allocation is\naccessible and perform a bulk cleanup if needed. There’s one more\nproblem before we can implement collect, though: our psuedocode\nrequired us to be able to store each allocation as a key in counts and\nalso to access the allocation’s neighbors. This means we have to use a\nlittle bit of type erasure to achieve our ends. I won’t go into too much\ndetail, but we need to be able to do two things:

\n
  • Store pointers to allocations as keys in a hash-map.

  • Reconstruct a stored pointer using type information to make it

    possible to do work.

\n

Due to the limitations of Rust, these are actually mutually exclusive.\nBecause it’s undefined behavior (due to provenance issues) to compare\nthe raw data in pointers, we can’t erase a pointer and then use it as a\nkey in a hash-map. However, we can’t just get a pointer to the first\nbyte of the allocation, because our allocation could be ?Sized.

\n

As a result, my implementation actually has two different kinds of\nerased pointers: a thin pointer which can be used for comparisons and a\nfat pointer which can be used to reconstruct a pointer to any type.

\n
struct AllocationId(NonNull<Cell<usize>>); // used as a key in hash-maps\nstruct ErasedPtr([usize; 2]);              // used as a reconstructible pointer to the allocation
\n

Then, all the functions which need to know the type information of the\nallocation (such as dfs and mark) can be stored opaquely as function\npointers, and when called, they can “rehydrate” the ErasedPtr passed\nin with type information.

\n

Below, I’ve included an example of how it can be used to implement\ndfs.

\n
unsafe fn dfs<T: Collectable + ?Sized>(\n    ptr: ErasedPtr,\n    counts: &mut HashMap<AllocationId, usize>\n) {\n    struct DfsVisitor<'a> {\n       counts: &'a mut HashMap<AllocationId, usize>,\n    }\n\n    impl Visitor for DfsVisitor<'_> {\n        fn visit_gc<U>(&mut self, gc: &Gc<U>) {\n            let id = AllocationId::new(gc.ptr);\n\n            if counts.insert(id, unsafe { gc.ptr.as_ref().ref_count.get() }) {\n                (**gc).accept(self);\n            }\n\n            *counts.get_mut(&id).unwrap() -= 1;\n        }\n    }\n    // pretend that `specify` converts the pointer back into NonNull<T>\n    let specified = ptr.specify::<T>();\n    specified.as_ref().accept(&mut DfsVisitor { counts });\n}
\n

I won’t include the implementation of collect here because it’s\nlengthy and not even the final revision of the cleanup algorithm, but\nyou can trust me that it works. After much gnashing of teeth and tearing\nof hair, this is finally enough to achieve bulk dropping, making calling\ndrop() on a Gc a linear-time operation.

\n

Amortizing

\n

What’s that, you say? You need your reference operations to work in\n𝑂(1) time? Why are programmers these days so picky?

\n

Luckily, it isn’t too hard to make our garbage-collection efforts\nterminate in average-case 𝑂(1) time. Instead of calling collect\ndirectly, we’ll just punt the allocation, which may be inaccessible,\ninto a set of “dirty” allocations. In my code, I call that set a\ndumpster. Then, once every |𝐸| times an allocation is dropped, we’ll\ngo through the whole dumpster and collect them all in 𝑂(|𝐸|) time.\nAmortized across all allocations, that’s technically 𝑂(1), enabled by\nthe same accounting wizardry that makes array-backed lists useful and\nthat caused the 2008 financial crisis.

\n

To save ourselves a little bit of work, whenever an allocation is\naccessed (such as by dereferencing or cloning), we can yank the\nallocation away from that same dirty set since it was just proven to be\naccessible.

\n

Are we concurrent yet?

\n

So far, the garbage collector I’ve been outlining to you has been a\nsingle-threaded collector, which can only store thread-local\ngarbage-collected values. I’m told that all code worth writing ends up\nbeing concurrent, so we have to do better than that. Lucky for us, this\nalgorithm can be made to operate concurrently with little effort,\nassuming that only one thread collects at a time.

\n

However, even if only one thread is collecting, we can still run into\nsome nasty concurrency issues. Let’s imagine that we have 2 allocations,\n𝑎 and 𝑏, plus the imaginary “root” allocation 𝑟, where 𝑎 can\nonly be accessed from 𝑟 and 𝑏 can only be accessed from 𝑎.

\n
\"image\"
\n

Now, consider performing a depth-first search starting from 𝑎. First,\nwe record that 𝑎 has 1 unaccounted-for-reference in counts. Then, we\nmove on to looking at 𝑏 because it’s one of 𝑎’s children.

\n

However, between when we record 𝑎’s reference count and examine 𝑏,\nanother malicious thread mutates 𝑏, adding a back-reference from 𝑏\nto 𝑎.

\n
\"image\"
\n

Then, the depth-first search will return to 𝑎, decrement the number of\nunaccounted references, and assume that all incoming references to 𝑎\nand 𝑏 were totally accounted for (and therefore inaccessible). Then\nthe garbage collector would happily destroy 𝑎 and 𝑏’s allocations,\nleaving a dangling reference to the heap, potentially causing a\nuse-after-free or other gnarly memory errors.

\n

Resolving concurrency

\n

The simplest solution to this concurrency issue is to just wrap\neverything in a big fat lock by forcing every single operation involving\na Gc to acquire a single global mutex, preventing any sort of\nconcurrency bugs at all. However, that’s ridiculously slow.

\n

We’d like to have an approach that only needs to achieve mutual\nexclusion over a small subset of all allocations if at all possible. To\ndo so, let’s take a closer look at our concurrency problem: we can see\nthat we only really get erroneous results when another thread mutates\nthe subgraph 𝐻 as we interact with it. The solution is quite clever -\nwe tag every Gc with a special number, which I’ll call a collecting\ntag.

\n

First, we’ll add a global atomic integer called the COLLECTING_TAG.

\n
static COLLECTING_TAG: AtomicUsize = AtomicUsize::new(0);
\n

Whenever we create or clone a new Gc, we’ll annotate it with the\ncurrent value of COLLECTING_TAG.

\n
// this new `Gc` type is intended to be `Sync`.\n\npub struct Gc<T: Collectable + Send + Sync + ?Sized> {\n    ptr: NonNull<GcBox<T>>,\n    tag: AtomicUsize,\n}\n\nimpl <T: Collectable + Send + Sync + ?Sized> Gc<T> {\n    pub fn new(x: T) -> Gc<T> {\n        // (other bookkeeping hidden)\n\n        Gc {\n            ptr: /* initialization of GcBox<T> */,\n            tag: COLLECTING_TAG.load(Ordering::Relaxed),\n        }\n    }\n}
\n

Next, at the start of the collection process, we’ll increment the value\nof COLLECTING_TAG just before we call dfs.

\n
fn collect() {\n    COLLECTING_TAG.fetch_add(1, Ordering::Relaxed);\n    // carry on with DFS and such\n}
\n

Lastly, whenever we encounter a Gc during the dfs process, we’ll\ncheck its tag. If the tag is equal to the current value of\nCOLLECTING_TAG, that means the Gc was created after dfs started.\nIf so, then whatever spot we found the Gc in must have been\naccessible, and we can mark it as so. To prevent us from visiting the\nsame edge twice (due to shenanigans), we’ll also update the tag on every\nedge we visit to the value of COLLECTING_TAG.

\n

Let’s return to our broken example to show how this modification fixes\nit. We return to our reference graph with 𝑎 pointing to 𝑏 and 𝑟\npointing to 𝑎. Since every Gc must be annotated with a tag, let’s\nsay they’re all tagged with 0.

\n
\"\"
\n

Next, when dfs begins, COLLECTING_TAG is incremented to 1. As a\nresult, the new reference created by a malicious thread must be tagged\nwith 1.

\n
\"\"
\n

Now, when dfs visits the edge pointing from 𝑏 to 𝑎, it sees that\nthe reference is labeled with a tag of 1, and therefore both 𝑏 and 𝑎\nmust be accessible - no accidental early deallocations here.

\n

Moving in and out

\n

We might hope that tagging the pointers is sufficient to prevent all\nconcurrency bugs. However, this is sadly not enough. To show why, we’ll\nbegin with an example.

\n

First, let’s imagine an allocation called 𝑥, which contains two\noptional references to itself.

\n
struct X {\n    x1: Mutex<Option<Gc<X>>>,\n    x2: Mutex<Option<Gc<X>>>,\n}
\n

At the start of our example, there will be only one Gc pointing from\ninside 𝑥 to itself, and the other slot that can hold a Gc will be\nempty. 𝑥 is accessible directly from the root allocation 𝑟, and all\nexisting references are tagged with 0. For the sake of clarity, I’ll\ndraw the arrow representing the first slot in 𝑥 with a solid line and\nthe second slot with a dashed line.

\n
\"\"
\n

Now, let’s have dfs begin, starting at 𝑥.

\n
  1. We increment COLLECTING_TAG to 1.

  2. dfs records that 𝑥 has 2 unaccounted-for references at the

    start.

  3. dfs visits the 𝑥’s first slot and tags the currently-existing

    self reference in that slot. 𝑥 now has 1 unaccounted-for\n reference.

    \n
    \"image\"

  4. A malicious thread intervenes, first moving the Gc from 𝑥’s

    first slot to 𝑟, then moving the original Gc which connected 𝑟\n to 𝑥 into 𝑥’s second slot.

    \n

    \n fn do_evil(r_to_x: Gc<X>) {\n let z = std::mem::take(&mut *r_to_x.x1.lock().unwrap());\n *z.x2.lock().unwrap() = r_to_x;\n }\n

    \n
    \"image\"

  5. dfs continues, now visiting the second slot in 𝑥. Seeing another

    reference to 𝑥, we decrement the number of unaccounted-for\n references to 0.

  6. dfs found no ancestors of 𝑥 with unaccounted-for ancestors, so

    we free 𝑥. However, 𝑥 is still accessible!

\n

This problem stumped me for a decent while. It seems impossible to\nprevent other threads from do-si-do-ing every Gc pointing to an\nallocation in order to fool our search. Luckily, there is a way through.\nSince tagging every Gc worked out for us before, we’ll try tagging\nevery allocation.

\n
#[repr(C)]\nstruct GcBox<T: Collectable + Send + Sync + ?Sized> {\n    ref_count: AtomicUsize,\n    tag: AtomicUsize,\n    value: T\n}
\n

Next, every time a Gc is dereferenced, we’ll update the tag in the\nallocation to the current value of COLLECTING_TAG.

\n
impl<T: Collectable + Send + Sync + ?Sized> std::ops::Deref for GcBox<T> {\n    type Target = T;\n\n    fn deref(&self) -> &Self::Target {\n        let box_ref: &GcBox<T> = unsafe { self.ptr.as_ref() };\n        box_ref.tag.store(COLLECTING_TAG.load(Ordering::Acquire), Ordering::Release);\n        &box_ref.value\n    }\n}
\n

Whenever dfs observes that the tag on an allocation is equal to\nCOLLECTING_TAG, that means that the allocation was accessed, and\ntherefore accessible. In order to shuffle references around in our above\nexample, the malicious thread would have to dereference a Gc,\nnotifying the search and preventing an early deallocation.

\n

In fact, this is enough to prove that dfs will never incorrectly\nmark an allocation as inaccessible, even under concurrent execution.\nThis blog post is already rather long, so I’ll only provide a rough\nsketch of the proof.

\n

Theorem: dfs will never erroneously mark an allocation as\ninaccessible.

\n

Proof:

\n

  1. If dfs encounters a Gc created after dfs begins, it will know

    that the referent is accessible.

  2. Due to (1), if dfs marked some allocation 𝑎 as inaccessible, it

    must have only visited Gcs pointing to 𝑎 which existed before\n dfs began.

  3. Weakening the statement from (2), if dfs marked some allocation

    𝑎 as inaccessible, it must have only visited Gcs pointing to 𝑎\n which existed when 𝑎’s reference count was recorded.

  4. dfs never visits a Gc while it points from the root allocation

    𝑟 to any other allocation.

  5. dfs must visit every Gc which pointed to an allocation at the

    point when its reference count was recorded in order to mark it as\n inaccessible.

  6. Due to (4) and (5), if 𝑎 is marked as inaccesssible, any Gc

    which at any point connected 𝑟 to 𝑎 must have been moved to\n connect another node (not 𝑟) to 𝑎.

  7. Due to (6), there is no lifetime 'x which can borrow against a

    Gc pointing from 𝑟 to 𝑎 and last between when dfs first\n visits 𝑎 and when it last visits 𝑎.

  8. The final Gc to move into 𝑎 before dfs must have been moved

    while another borrow against a Gc pointing from 𝑟 to 𝑎\n existed. Let the lifetime of that borrow be 'y.

  9. Because 'y lasts longer than the final move, 'y can be extended

    to last arbitrarily long, even until after dfs has finished\n visiting every Gc pointing to 𝑎.

  10. Due to (7), 'y must not have existed before dfs first visited

    𝑎. Therefore, if 𝑎 is erroneously marked as inaccessible, a Gc\n pointing to 𝑎 must have been dereferenced to generate a borrow\n with lifetime 'y.

  11. If a Gc pointing to 𝑎 was dereferenced before the last time

    dfs visited a Gc pointing to 𝑎, then dfs would have observed\n that 𝑎’s tag had changed. Therefore, if an allocation was\n erroneously marked as inaccessible, it must have been marked as\n accessible. Therefore no allocations were ever erroneously marked as\n inacessible by dfs. QED.

\n

This proof is relatively handwavy, but it should be possible for an\nastute reader to fill in the details. I will leave it to such astute\nreaders to prove the complementary proof to this; namely, that dfs\nwill never erroneously mark an allocation as accessible.

\n

I also think that it’s really cool that the entire mechanism of the\ncorrectness of this approach is totally supported by Rust’s borrow\nchecking semantics. It makes the whole thing feel like it fits right in.

\n

It’s the weak ones that count

\n

There’s one more cause for memory safety issues from concurrency. If an\nallocation is freed because its reference count reached zero, it could\nstill be accessible by another thread because it was stored in the\nglobal dumpster. We can’t guarantee that we’ve obliterated all\nreferences to that allocation from every other thread’s memory, so it\nseems like we’re hosed.

\n

However, there’s no problem in computer science that can’t be solved by\nadding more state. Taking a leaf from Rc’s book and adapting it\nliberally, we annotate each allocation with a “weak” reference count,\nwhich is the number of times it’s referenced by a dumpster or cleanup\nthread. We’ll rename our original reference count to be the strong count\ninstead.

\n
#[repr(C)]\nstruct GcBox<T: Collectable + Send + Sync + ?Sized> {\n    strong: AtomicUsize,\n    weak: AtomicUsize,\n    tag: AtomicUsize,\n    value: T,\n}
\n

Then, when dropping the last strong reference to a Gc, we first check\nthat its weak reference count is nonzero before we can deallocate it. If\nnot, it’s the cleanup threads’ problem to take care of it.

\n

Whenever an allocation is removed from a dumpster and about to be thrown\naway by a thread running a cleanup procedure, the thread decrements the\nweak count of the allocation and checks if both the weak and strong\ncount have reached zero. If so, that thread can then safely destroy the\nallocation.

\n

Deadlocked!

\n

Imagine that we want to create a Gc<Mutex<()>>, and then drop a Gc\npointing to it while the Mutex is locked.

\n
let gc1 = Gc::new(Mutex::new(()));\nlet gc2 = gc1.clone();\n\nlet guard = gc1.lock()?;\ndrop(gc2); // suppose this triggers a cleanup\ndrop(guard);
\n

While traversing the reference graph, the dfs visitor would attempt to\nvisit the mutex, lock it, and try to carry on. However, since the same\nthread that triggered the allocation still holds a guard to that mutex,\nthe thread would deadlock disastrously. Lucky for us, we know that any\nallocation with a held mutex guard must still be accessible (due to\nMutex’s excellent API), so we can be certain that if we fail to\nacquire a mutex, we have immediate proof that an allocation is\naccessible.

\n

To take advantage of that, we’ll make visiting a collectable type a\nfallible operation, and make it so that failing to acquire a lock also\nfails the visit.

\n
pub trait Collectable {\n    fn accept<V: Visitor>(&self, visitor: &mut V) -> Result<(), ()>;\n}\n\npub trait Visitor {\n    fn visit_gc<T: Collectable + ?Sized>(&mut self, gc: &Gc<T>) -> Result<(), ()>;\n}\n\nimpl<T: Collectable + ?Sized> Collectable for Mutex<T> {\n    fn accept<V: Visitor>(&self, visitor: &mut V) -> Result<(), ()> {\n        // pretend poison errors don't exist\n        self.try_lock().map_err(|_| ())?.accept(visitor);\n        Ok(())\n    }\n}
\n

Sharing your dumpsters

\n
\"A
\n

You’ve made it this far into this (admittedly rather lengthy) post.\nEnjoy this hand-drawn picture by yours truly.

\n

When implementing this garbage collector, one of the biggest bottlenecks\nwith concurrent performance is accessing the one, global dumpster every\nsingle time a Gc is dropped. If using a Mutex<HashMap>, this will\nremove nearly all parallelism from the whole system and make you wonder\nwhy you paid all that money for a 16-core computer.

\n

As a result, any sane person might lean for a concurrent hashmap. There\nare many Rust implementations - I tried\nchashmap but gave up\non it due to a rare panic\nbug, and then\nI tried dashmap, which worked\nfine but was too slow as thread counts increased.

\n

The heart of the issue is that concurrently updating any data structure\nis going to be slow. Even so-called “concurrent” data structures which\nuse clever sharded locks have this issue - there’s always some\ncontention overhead. The best workaround to concurrency slowdowns is to\njust not do things concurrently. We can fix this by making every thread\nhave its own dumpster, and then having a global collection of\nto-be-cleaned allocations which I’ll call the garbage truck. Whenever\nanother allocation is marked dirty, we can check if this thread’s\ndumpster is full according to some heuristic, and if so, transfer all\nthe allocations from this thread’s dumpster to the garbage truck. I’ve\nincluded some pseudocode for the whole process below.

\n
dumpster = set() # local to this thread\ngarbage_truck = mutex(set()) # global to all threads\n\ndef mark_dirty(allocation):\n    dumpster.add(allocation)\n    if is_full(dumpster):\n        garbage_truck.lock()\n        for trash_bag in dumpster:\n            garbage_truck.add(trash_bag)\n        garbage_truck.unlock()\n        dumpster = set()
\n

If is_full returns true rarely enough, there will be almost no\ncontention over the garbage truck. This means that the concurrency\noverhead is vastly reduced and we get to pocket some great performance\nreturns.

\n

Okay, but how fast is it?

\n

In short, this garbage collector runs pretty fast!

\n

In the end, I made two different garbage collector implementations - one\nwhich is thread-local, saving us from all the concurrency headaches, and\nanother thread-safe one that has all the bells and whistles at the cost\nof some performance. Borrowing from\nonce_cell’s API, the former\nlives in the unsync module of the crate and the latter in sync.

\n

Next, I collected all the garbage collectors I could find in order to\ncompare them. I selected all the ones which had a similar API to\ndumpster, were published on crates.io, and\nactually worked.

\n
NameConcurrent?Like dumpster?
dumpster (unsync)❌✅
dumpster (sync)✅✅
Rc❌✅
Arc✅✅
bacon-rajan-cc❌✅
cactusref❌❌
elise✅❌
gc❌✅
gcmoduleyes, but with a different API✅
rcgc❌❌
shredder✅✅
\n

I excluded the ones that didn’t have a dumpster-like API because it\nwould have been a pain to set up a benchmarking harness to handle them.\nIf you feel this is poor diligence, you can go benchmark them yourself.\nI also included Rc and Arc, even though they don’t collect cycles,\nbecause they’re a decent baseline for the minimum performance of a\ngarbage collector. During my research, I also found that\nbacon-rajan-cc doesn’t initiate collections of its own accord, so I\nadded a version of each of dumpster’s garbage collectors which doesn’t\nautomatically trigger collections in the spirit of competitive fairness.\nThose versions are labeled as “manual.” Lastly, I found that gcmodule\nsimply stack-overflows and sometimes segfaults when facing extremely\nlarge collection loads, so I removed it from the benchmark set.

\n

As my benchmark, I decided to do the very simplest thing I could think\nof: have a bunch of allocations randomly add and remove references to\neach other in a loop, dropping and creating new allocations as well. To\naccount for random noise, I ran 100 trials of each garbage collector\ndoing 1 million operations. Each operation is either the creation of a\nreference or a deletion.

\n

First, I ran a benchmark of all the garbage collectors, measuring pure\nsingle-threaded performance. I’ve shown my benchmark results as a set of\nviolin plots below, relating runtime to frequency.

\n
\"A
\n

This plot doesn’t tell us much other than that shredder is slow. To\ntake a closer look, let’s remove shredder from the list and see what\nwe find.

\n
\"The
\n

dumpster’s unsync implementation is in a decent position, beat out\nonly by the non-cycle-detecting allocators and bacon-rajan-cc.\nbacon-rajan-cc has very little overhead and is quite performant.

\n

I think there are two main reasons why the concurrent version of the\ngarbage collector is much slower than the single-threaded one. First,\nmoving allocations from a thread-local dumpster to the global garbage\ntruck takes some time. Second, the dfs operation in a concurrent\nenvironment must record the current set of children of an allocation,\ntypically in a separate heap-allocated structure, to prevent some\nconcurrency bugs. It’s certainly possible to mitigate the losses from\nthe first issue, but the second is harder to handle.

\n

My guess as to why the concurrent version is significantly slower when\nusing automatic collection triggering is that it’s a consequence of my\ntesting harness. Currently, it runs all the tests in a loop, so the\nsingle-threaded benchmark could run directly after the multi-threaded\none and be forced to clean up some of its garbage.

\n

In any event, let’s move on to the results from the multi-threaded\nbenchmark.

\n
\"A
\n

The only other concurrent garbage collector available for me to test\nagainst was shredder, and it looks like it wasn’t much of a\ncompetition.

\n
\"A
\n

dumpster doesn’t scale as smoothly as I’d like with thread count, but\nit’s a relief that performance does actually improve with thread count,\nexcept for the jump from one thread to two. I think being only 3x slower\nthan Arc is a decent victory, especially for a project that I wasn’t\npaid any money to do. I’m not much of an expert at high-performance\ncomputing in concurrent situations, so trying to optimize this further\nwould likely just be an adventure in trying random things and seeing if\nthey yield an improvement. If anyone out there has clever ideas on how\nto optimize this approach, let me know! My email is on the “About” page.

\n

Coda

\n

Over the last few months, I built a garbage collector for Rust from\nscratch. I implemented a novel (ish) algorithm of my own design, got it\nto work in both single-threaded and multi-threaded contexts, and showed\nthat it was actually pretty performant.

\n

The implementation of this crate is now up on\ncrates.io and available for anyone\nto download. It’s licensed under the GNU GPLv3.

\n

Special thanks to Wisha,\nCharlie, and\nShreyas for reviewing this post, fielding\nmy bad questions, and putting up with me rambling about this for nearly\ntwo months straight.

\n

Postscript

\n

I have a few things that I thought were interesting along the way but\ndidn’t quite have a good spot to include in the story above, so they’ll\nall be mish-mashed in here.

\n

Ode to bad good ideas

\n

The final, polished solution you see in this blog post is actually quite\nfar from my original idea. In particular, almost all of my first ideas\nfor handling concurrency didn’t work. Here’s a quick roll of them all:

\n

  • Wrap a Mutex around every single allocation’s reference count and

    hold them while doing dfs

  • Save on space in Gcs by tagging only the lowest bit instead of

    adding an entire usize

  • Make everything enable dynamic dispatch so we can have real

    Java-like objects

  • Clean up allocations locally on every thread

  • Avoid directly dropping allocations and instead cleverly decrement

    their reference count

\n

Cool nightly tricks

\n

Rc and the other pointer types are somewhat “blessed” in that they can\naccess nightly features from the Rust compiler and still be consumed by\nstable projects. dumpster has no such blessings.

\n

I would like to implement CoerceUnsized unconditionally for all my\ngarbage collectors, but that’s simply not possible on stable yet.

\n

Likewise, pending the implementation of strict provenance, there’s\nactually no way for a stable crate to manipulate the address portion of\na fat pointer. This means that even if I found some space optimization\nusing lower bit tagging, I wouldn’t be able to use it because it’s gated\nbehind a nightly feature.

\n

Another path to Gc<dyn T>

\n

Without the ability to coerce Gc as an unsized type, I can’t make\nCollectable object safe due to the function signature of accept,\nwhich forces Visitor to also be object-safe, forcing visit\noperations to also be object-safe.

\n

I’ve thought of a slightly different approach, though. We can make\nVisitor a single concrete type, and that makes Collectable trivially\nobject-safe. The downside here is that I would then have to store all 5\nof my current visitor implementations in the same structure, and that\nloses a lot of my nice type safety features and adds a large runtime\npenalty. I’m not very happy with that idea, though.

\n

Miri rules

\n

I would probably not have been able to finish this project without\ncargo miri. If you haven’t heard\nof it, you should download it right now and run all of your Rust\nprojects with it. It’s such a fantastic tool for debugging unsafe code\nthat I wish I could have it in other languages, too - valgrind is a poor\nsubstitute for it when using C.

\n

Testing and debugging

\n

Early on, I had just a few handwritten tests. The first reference graph\nthat I found that gave me trouble looked like this:

\n
\"\"
\n

However, once I had simple graphs with multiple cycles down, it was hard\nto come up with new tests. As a result, I resorted to fuzzing, using the\nsame approach as my benchmark - randomly generating references and then\nseeing if they got cleaned up properly.

\n

Debugging the results of those fuzzed tests absolutely sucked, though.\nThe experience of trying to find the source of an issue was awful, so I\nended up having to make some (crude) tools to make the process easier.\nEventually, I had settled on printing out the reference graph at choice\ntimes during the run of my tests and then visualizing them to get a good\nguess of what was wrong. However, when making the concurrent\nimplementation, printing something can change the execution behavior of\nthe program. Not only that, it’s not always obvious what the issue is. I\nhad one bug which only occurred after several thousand operations had\ncompleted, resulting in reference graphs that looked like this:

\n
\"\"
\n

The graph above was made by fuzzing my garbage collector, using the same\napproach as my benchmarks.

","headings":[{"level":1,"text":"I built a garbage collector for a language that doesn't need one","id":"i-built-a-garbage-collector-for-a-language-that-doesn-t-need-one"},{"level":2,"text":"Background","id":"background"},{"level":2,"text":"Battle plan","id":"battle-plan"},{"level":2,"text":"My approach","id":"my-approach"},{"level":3,"text":"Reference counting with extra steps","id":"reference-counting-with-extra-steps"},{"level":3,"text":"Trait hackery","id":"trait-hackery"},{"level":3,"text":"Bulk dropping","id":"bulk-dropping"},{"level":3,"text":"Amortizing","id":"amortizing"},{"level":2,"text":"Are we concurrent yet?","id":"are-we-concurrent-yet"},{"level":3,"text":"Resolving concurrency","id":"resolving-concurrency"},{"level":3,"text":"Moving in and out","id":"moving-in-and-out"},{"level":3,"text":"It’s the weak ones that count","id":"it-s-the-weak-ones-that-count"},{"level":3,"text":"Deadlocked!","id":"deadlocked"},{"level":3,"text":"Sharing your dumpsters","id":"sharing-your-dumpsters"},{"level":2,"text":"Okay, but how fast is it?","id":"okay-but-how-fast-is-it"},{"level":2,"text":"Coda","id":"coda"},{"level":2,"text":"Postscript","id":"postscript"},{"level":3,"text":"Ode to bad good ideas","id":"ode-to-bad-good-ideas"},{"level":3,"text":"Cool nightly tricks","id":"cool-nightly-tricks"},{"level":3,"text":"Another path to Gc","id":"another-path-to-gc-dyn-t"},{"level":3,"text":"Miri rules","id":"miri-rules"},{"level":3,"text":"Testing and debugging","id":"testing-and-debugging"}]}}