I've been thinking a lot about garbage collectors for compiled languages again

Funnily enough my idea for a multi threaded gc for Rust is basically how boehm does it too (well at least on linux): On a GC cycle you send a unix signal to all other threads to make them pause and then in the signal handler you save all regs, then walk the stack and regs upwards over 8 byte values. Any value that falls into the gc heap and is a valid allocation is assumed to be a ptr and that object gets marked

Pretty clever

Though I'm working on a single threaded GC for Rust now. That one actually has a real use case too: I don't have to use Rc<T> and .clone() them all over the place in my compiler! Just beautiful wrapped pointers with copy semantics 😌

@retoor Was your GC just part of a higher level code or actual pointer and byte level? Because that's when it becomes tricky :P

Right now I'm kinda struggling how to make the memory allocator not waste a bunch of space

I'm thinking creating a ram-sized virtual memory region and then committing the pages I need but for each n pages I also have one metadata page so that "is this pointer a valid allocation" (which is needed for the conservative tracing routine) can be efficient -- without wasting one slot per page for page metadata. At higher size classes (> 16 byte) that's just wasted space...

Hm, how does a GC make any sense for Rust?
Rust won’t let you compile code with unmanaged memory left for a GC to collect at runtime.

@Lensflare Well it *can* if you make it do it :P

It's really not *that* complex though. Rust can be as low level as C, so essentially I'm just implementing a spin on conservative tracing garbage collection (and it's single threaded, so quite a lot easier)

So if you call a gc cycle, I load the current stack pointer and walk over the raw stack. Anything that looks like a valid gc pointer (i.e. it points to within my gc heap) is treated like a real pointer and that object gets tagged. Then you go over your heap and delete all dead objects

From a Rust standpoint it's no problem: Gc<T> is just a raw ptr with a deref impl. That cannot result in UB since aslong as somebody still holds a gc handle it won't get deleted. And once nobody holds it, nobody can obverse the deletion