Shifgrethor: garbage collection as a Rust library

[masonk]

From one humanities major to another, I salute you! I’m amazed that you’ve been at this for such a short time, as well.

Getting back to the GC, though. Would a tricolor mark-and-sweep algorithm be implementable under the constraints that shifgrethor’s API imposes? Like a naive mark-and-sweep, it is a precise, tracing collector.

In practice, it achieves excellent latency even for large heap sizes, and it never moves a pointer, so the whole pinning problem just drops out. The tradeoff of “extra work, but concurrently on another core” is an increasingly good one for modern hardware.

[withoutboats]

Getting back to the GC, though. Would a tricolor mark-and-sweep algorithm be implementable under the constraints that shifgrethor’s API imposes? Like a naive mark-and-sweep, it is a precise, tracing collector.

Nothing about that algorithm prevents it from being used in shifgrethor. Its designed to be run concurrently with program operations (as opposed to “stop the world” GCs which run no user code during collection, like shifgrethor’s current operation). Concurrent GCs in general can introduce some tricky problems, but not specific to that algorithm.

[withoutboats]

Post #3: Rooting GC’d objects in Rust. This provides a brief look at well-known rooting strategies used by other languages, and then goes into detail on how rooting is implemented in shifgrethor, including the somewhat novel concept of the 'root lifetime (which will come up in later posts as well).

Shifgrethor III: Rooting

[madmalik]

Looking at this, it occurred to me: what if we just stopped tracking roots in the stack at all? Instead of this doubly linked list of roots, we could actually use a proper global stack.

I just started experimenting with exactly that today Nice to see that i was on the right path.

[skippy]

I hope I’m not jumping the gun by posting this before @withoutboats, but I see the 4th post is up now!

Shifgrethor IV: Tracing

Another great post in this amazing series. After reading the previous posts on GC in Rust leading up to this project, it really feels like there’s something special here.

[withoutboats]

Thanks, I was just coming here to post it!

[skippy]

The Rust community has written some amazing series, but I’ve never been as excited as I am about this one. Ever since the first post came out, I spend half of my days checking to see if there’s a new post to read or just rereading the existing posts and poring over the source code.

Thanks so much for the effort you’re putting into this!

[crlf0710]

The posts are great, but is shifgrethor ready to be published to crates.io some time soon?

[madmalik]

Again, interesting read. Thanks for doing the work and writing about it!

[skippy]

I’m curious about how Shifgrethor’s interior mutability rules work, in comparison to something like a List<T> in e.g. C#. My knowledge of GCs and Rust is limited, so please bear with me.

In C#, I could easily have a List<T> that allows me to add/remove other GC items inside it. This is a far different situation to Rust of course, since ownership/mutability isn’t in play.

However, if I wanted something similar in Rust with Shifgrethor, how would this look? Is this even a valid use case? I’m wondering if there could be some kind of “updatable” GC pointer that allows this, that could be put inside the Vec. Is there a better way to achieve something similar?

[withoutboats]

This is the subject of a future post in the series, but in brief: the tricky part of interior mutability is making sure that you can’t unroot a Gc pointer while you’re mutating it (for example, by swapping it onto the stack, where its no longer being traced). Probably collections like the one you’ve described will be best handled by custom collection types that have APIs designed to make sure you never get access to an unrooted (or unrootable) gc pointer.

[withoutboats]

The posts are great, but is shifgrethor ready to be published to crates.io some time soon?

Not sure! It’s pretty much done as far as its current iteration goes, but its current iteration is to support this blog series describing the research into what Rust can express, and not to be generally useful. Once the blog series concludes, I’d be interested in sharing ownership with anyone who thinks shifgrethor has the potential to be used for real programs & helping to support them in trying to improve its performance & ergonomics.

[skippy]

Ok, cool. I think I understand… let me see if I have this correct.

An updatable pointer could work then, if you were forced to create a new root whenever you use it? Unlike GcStore which, IIUC, is just a simple transmute into a Gc as long as you access it through some other Gc. That would then let you swap it out onto the stack like you mentioned, since it has been properly rooted. You just have to pay the expense of rooting, vs the free transmute.

I’m anxious to see what’s next once the blog series concludes as well. I don’t have the expertise to drive design, and I don’t have a use case… but I’d love to work on this.

[withoutboats]

An updatable pointer could work then, if you were forced to create a new root whenever you use it?

In general, growing collections is not a problem: for example, you’ll trace every element of a List, so adding new members to the list is no problem, because they’ll also be traced. The problem is that when you take an element from the list, you have to make sure that it is still rooted wherever you put it.

[madmalik]

Once the blog series concludes, I’d be interested in sharing ownership with anyone who thinks shifgrethor has the potential to be used for real programs & helping to support them in trying to improve its performance & ergonomics.

Imo, the most reusable part of this the rooting mechanism - do you think it would be possible to generalise that part or is it to integrated with the inner workings of shifgrethor?

[withoutboats]

Imo, the most reusable part of this the rooting mechanism - do you think it would be possible to generalise that part or is it to integrated with the inner workings of shifgrethor?

I think that an API could be introduced to allow users to choose their own GC implementation, though the safety requirements on that GC are somewhat complicated/specific (e.g. a copying collector would have to support pinning of some kind).

[skippy]

I’m curious about the rooting strategy, which seems to be the breakthrough here, and the ergonomic hit you mentioned it introducing. It seems like whenever you need a root there’s only really one way to do it. In other words, it’s 100% rote boilerplate and there’s no decision to make, you just add in letroot!() as appropriate. Is that correct?

I really don’t know much about Rust macros… but would this allow a hypothetical #[gc] attribute on a function that eases the ergonomic hit? Something like the following, where each root!() would get transformed into an appropriate letroot!() call that appears in the right place before the statement, with an appropriately unique identifier.

let x: Gc<u8> = root!().gc(0);

fn_call(1, 2, root!().gc(0), root!().gc(1));

let y: Gc<Foo> = Foo::new(root!());

becoming:

letroot!(root);
let x: Gc<u8> = root.gc(0);

letroot!(root1); letroot!(root2);
fn_call(1, 2, root1.gc(0), root2.gc(1));

letroot!(root);
let y: Gc<Foo> = Foo::new(root);

As far as I understand, you can’t define a real macro like I have the root!() calls in the original, since it needs to do things out of order. But I think an attribute macro could do that rewrite inside its function.

I’m probably getting a little ahead of myself here…

Edit: I guess what I’m really looking to confirm here is that the rooting strategy you have seems to require very little magic to do automatically. That makes me hopeful about future cleverness to ease any ergonomic hits.

[withoutboats]

It seems like whenever you need a root there’s only really one way to do it. In other words, it’s 100% rote boilerplate and there’s no decision to make, you just add in letroot!() as appropriate. Is that correct?

A macro like root!(0); could work (no compiler support needed), but you want to be able to pass the root to function calls so that they can return Gc types. In complex code you don’t always want the gc’d pointer to be rooted in the same scope that its created in.

[skippy]

A macro like root!(0); could work (no compiler support needed), but you want to be able to pass the root to function calls so that they can return Gc types. In complex code you don’t always want the gc’d pointer to be rooted in the same scope that its created in.

For some #[gc] marked function, could this be done by adding in Root arguments automatically as well? As in, for each Gc in the return type with a lifetime not tied to an argument Gc, generate a Root argument at the start. Even if it would work, I’m not sure if that kind of magic is discouraged in Rust.

E.g.:

#[gc] fn new<'root>() -> Gc<'root, Self> { ... }

becomes:

fn new<'root>(root: Root<'root>) -> Gc<'root, Self> { ... }

[withoutboats]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.