That's exactly why I was excited to write this chapter. They have a reputation for being hard, but the core algorithm is really just a simple graph traversal.

https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga...

I've implemented a couple of scripting languages, but thus far I've ignored GC. It is something I'd like to experiment with in the future though.

The reason being that allocation can be much faster. The GCed code can allocate memory with as much as an increment of a pointer (and that is atomic, so no thread locking needed).

malloc/free always do full function calls, and they might/will descent into dealing with fragmentation (aka finding free space). Likewise, free() isn't free and cross-thread allocation/deallocation can further complicate things.

Nitpick (and mostly for others reading): incrementing the address of a pointer if done locally (as in, using a local variable of sorts) may be atomic, but storing the updated pointer somewhere may not. If a bump allocator wants to support concurrent allocations, it should make sure to use the right atomic operations (typically this just a compare-and-swap of the old pointer with the locally incremented one).

But if you cannot move memory (adjust pointers like most GCs do) then you will have to deal with fragmentation, which slows down allocation (or causes other drawbacks).

Moving GC can also make the program faster due to memory compactation and hence being more efficient wrt CPU cache and TLB.

Turned out the vast majority of allocations are tiny object instances of a handful of different sizes. As a result minimizing fragmentation is as easy as allocating pools of a fixed size for small objects, and round up larger objects to a multiple of block size. There are still truly pathological patterns possible, and a compacting / generational gc may still be worth it later both to deal with that and to reduce the cost of a collection, but for a lot of uses you can get away with simple options like that.