Copying GC implementation

[maximecb]

Current GC progress:

• Objects
• Strings
• Arrays
• ByteArrays
• Basic message allocator GC
• Basic GC testing
• Add gc_check in every place where we allocate memory
• More rigorous testing
• Closures (like objects)
• Hashes (WIP Marco)
• Actors need to wait on receiver when message allocator is full
• Automatic message allocator expansion
• Double-check that all example programs work reliably with GC

I'm just sharing this plan/thoughts in case people want to comment. Plush doesn't yet have a garbage collector. The language has actors, which are independent interpreters running in separate threads. I've designed the system to try and minimize locking. There is no global VM lock, and currently each actor has its own allocator. I wanted to avoid a situation where actors would need to lock on a global allocator each time memory needs to be allocated.

When sending messages to another actor, the data needs to be copied. At the moment, the way this is done is that each actor has a mailbox allocator for incoming messages. This makes it possible for the actor sending the message to lock on the mailbox allocator of the receiver. That means the receiver can continue its execution uninterrupted while messages are being copied into its mailbox.

In terms of garbage collection, I'd like to go for a simple approach. I want to avoid generational garbage collection for now. We could either go with mark-and-sweep or a copying GC. There are two big advantage with a copying GC. The first is that bump allocation is very fast. The second is that collection time is proportional to the amount of live memory. These things could be an advantage in a language that allocates a lot of temporary data, especially since modern CPUs are very fast at copying memory.

I'm trying to design the system so that garbage collection for one actor can run without interrupting the other actors. I would expect that even if an actor has several hundred megabytes of live data, collection should take less than 10 milliseconds, meaning no visible penalty in the context an interactive game.

There is already logic to copy objects for sending a message in deepcopy.rs, and so maybe some of that code could be reused or adapted for a copying GC. In theory, you could traverse and copy objects from an old allocator into a new allocator.

There is a tricky bit, which is that when an actor receives a message, we need to transfer ownership of this message from the mailbox allocator to the receiving actor. Ideally we'd like to be able to do that without copying this data. This poses a bit of a challenge because we have a situation where the mailbox allocator can get full and need to trigger its own GC. In that case it may need to synchronize with the actor. Similarly, if the main allocator of an actor is full, it may need to trigger GC. I suppose this is maybe a simpler situation because if an actor's main GC trigger, we can just not copy, not move the data from its mailbox allocator.

Another tricky aspect is when an actor calls into host functions. This may cause data to be allocated. If a host function can allocate new data, this could trigger a GC. In this case we need to be careful to make sure the GC is aware of all the roots so that we don't end up with objects accidentally being collected.

[maximecb]

@Maaarcocr I implemented a sketch of the idea I was talking about earlier:
6fd408d

This makes it possible to run the test program benchmark/alloc_objs.psh in a loop, collecting the memory multiple times. Right now this only works because that program only allocates objects and there is basically no live data. However this test highlighted that there is a bug in the interpreter somewhere and the stack keeps growing indefinitely as the loop iterates 😆 Oops!

I also didn't implement the logic to copy in values from the message allocator. That might turn out to be slightly complicated to do because there can be a number of objects that are waiting inside the actor's message queue. These objects should all be copied over I think... Which might involve taking all the pending messages out of the queue, copying them and pushing them back into the queue?

[Maaarcocr]

I also didn't implement the logic to copy in values from the message allocator. That might turn out to be slightly complicated to do because there can be a number of objects that are waiting inside the actor's message queue. These objects should all be copied over I think... Which might involve taking all the pending messages out of the queue, copying them and pushing them back into the queue?

for messages in the queue: couldn't we consider them as roots, copy them out of the message allocator and then remap the values?

[maximecb]

for messages in the queue: couldn't we consider them as roots, copy them out of the message allocator and then remap the values?

Yes we have to, but the tricky bit is that the messages in the queue haven't been read yet, so we need to put them back in the queue somehow lol. We may need to push them back into the sender endpoint after they are remapped or something 😆

[maximecb]

While looking at the code generation to implement GC I also discovered a latent bug in the way closure variables are handled (lol). That's 3 bugs fixed while working on the GC so far...

[maximecb]

I fixed some bugs and added some new GC tests:

tests/gc_linked_list.psh
tests/gc_str_concat.psh

Still lots of things that are not working with the GC, but I figure we can keep adding more tests as we fix more issues and get more things working correctly with it :)

[maximecb]

@Maaarcocr I was able to get the logic to grow the heap working, new working test:

tests/gc_list_extend.psh

Also, the raytracer example, which allocates a lot of objects, is able to execute and survive multiple GC cycles:

cargo run examples/raytracer.psh 1 800 800

Still missing heap-allocated arrays to be able to run examples/city.psh which allocates a lot of arrays.

[maximecb]

@Maaarcocr I added two new GC tests for arrays:

tests/gc_alloc_arrays.psh
tests/gc_grow_array.psh

Seems there's a hidden bug in Plush somewhere though. I get an array with capacity zero when the GC triggers in:

cargo run examples/city.psh

This is an array-heavy program. Not sure what's happening. Probably an error in the GC code, maybe some root not getting updated 🤔

[Maaarcocr]

@maximecb I hope it's okay that my activity is a bit lower during the week, I'll get back to this with more time on the weekend!