C++ gives you std::shared_ptr and std::unique_ptr so you never have to manually manage memory again. Naturally, I decided to ignore that and write my own garbage collector for fun.

It’s simple, it’s educational, and it has an algorithm so inefficient it would make a Bubble Sort blush.

The “Pool” Concept

The core idea is a Pool class that pre-allocates a chunk of memory. When you ask for an object, it hands you a std::shared_ptr with a custom deleter. When that pointer dies, instead of delete-ing the memory, it pushes it back onto a freelist stack.

template <typename T>
class Pool {
    std::vector<std::shared_ptr<T>> freelist;

    // ...

    void destroy(std::shared_ptr<T>&& elem) {
        Ptr p = elem;
        elem->~T(); // Call destructor manually
        freelist.emplace_back(std::move(p)); // Return to pool
    }
};

This is actually a standard optimization technique. The “freelist” means we avoid expensive new and delete syscalls during runtime.

The Cycle Problem

But what about circular references? If Object A points to B, and B points to A, their reference_count will never drop to zero. std::shared_ptr can’t help you here.

A real GC (like Java’s) uses “Mark and Sweep” to find unreachable islands of objects. I… used nested loops.

void gc() {
    for (std::size_t i = 0; i < freelist.size(); i++) {
        for (std::size_t j = 0; j < freelist.size(); j++)
            if (i != j && 
                freelist[i]->pointsTo == freelist[j] && 
                freelist[i] == freelist[j]->pointsTo) {
                
                std::cout << "Deleting circular" << std::endl;
                freelist[i]->pointsTo.reset();
                freelist[j]->pointsTo.reset();
            }
    }
    freelist.clear();
}

Yes, that gc() function is $O(N^2)$. It iterates through the entire freelist to find pairs of objects pointing to each other. It only detects cycles of length 2. It’s hilariously limited.

The Verdict

This implementation is a toy. It shows the danger of rolling your own memory management. While the Pool allocator is a valid performance strategy (used in game engines and HFT), the manual cycle detection is where clarity and performance go to die.

But hey, it passed the unit tests.

Check out the code in my Systems Playground.