C++ Garbage Collector - Simple Automatic Memory Management

Question

I made a general smart pointer which fixes the problems of loops between std::shared_ptr's. While use is simple, I feel that my code is inefficient and clumsy. Here it is:

/*
 * gc.hpp
 *
 *  Created on: Nov 10, 2021
 *      Author: lambcoder
 */
#ifndef GC_HPP_
#define GC_HPP_
#include <any>

namespace lambcoder{

template<typename T>
class gcpointer;

class garbage_collector final{
    template<typename T>
    friend class gcpointer;

    template<typename T, typename... Ts>
    friend gcpointer<T> gcnew(Ts&&...);

    static garbage_collector global_gc;
    garbage_collector() {}

    struct Node{
        Node() = default;
        template<typename T, typename... Ts>
        Node(std::in_place_type_t<T>, Node* prev, Node* next, Ts&&... ts):
            prev{prev}, next{next}, obj{std::in_place_type<T>, std::forward<Ts>(ts)...}{}

        Node* prev = nullptr, *next = nullptr;
        std::any obj{};
        std::uint16_t ref_count = 1;

        template<typename T, typename... Ts>
        friend gcpointer<T> gcnew(Ts&&...);
    };
    Node* head{nullptr};
    static enum class State : std::uint8_t {weak, strong} weak_state;
public:
    ~garbage_collector(){
        weak_state = State::weak;
        Node* tmp = nullptr;
        while(head){
            tmp = head->next;
            delete head;
            head = tmp;
        }
    }
};

garbage_collector::State garbage_collector::weak_state = garbage_collector::State::strong;

garbage_collector garbage_collector::global_gc = {};

template<typename T>
class gcpointer{    
    using node_ptr = garbage_collector::Node*;
    node_ptr ptr = nullptr;
    gcpointer(node_ptr ptr) noexcept: ptr{ptr}{}
public:
    constexpr T& operator*(){
        return std::any_cast<T&>(ptr->obj);
    }
    constexpr T* operator->(){
        return ptr ? &this->operator*() : nullptr;
    }
    constexpr operator T*(){
        return this->operator->();
    }

    constexpr gcpointer() noexcept = default;
    constexpr gcpointer(std::nullptr_t) noexcept {};
    constexpr gcpointer(const gcpointer<T>& other) noexcept: ptr{other.ptr} {
        if(other.ptr != nullptr)
            ++ptr->ref_count;
    }
    gcpointer(gcpointer<T>&& other) noexcept: ptr{std::exchange(other.ptr, nullptr)} {}

    gcpointer<T>& operator=(const gcpointer<T>& other) noexcept{
        if(other.ptr == this->ptr) return *this;
        if(ptr != nullptr && --ptr->ref_count == 0){
            if(ptr == garbage_collector::global_gc.head) garbage_collector::global_gc.head = garbage_collector::global_gc.head->next;
            else if(ptr->prev) ptr->prev->next = ptr->next;
            if(ptr->next) ptr->next->prev = ptr->prev;
            delete ptr;
        }

        ptr = other.ptr;
        if(ptr != nullptr) ++ptr->ref_count;

        return *this;
    }
    gcpointer<T>& operator=(gcpointer<T>&& other) noexcept{
        if(other.ptr == this->ptr) return *this;
        if(ptr != nullptr && --ptr->ref_count == 0){
            if(ptr == garbage_collector::global_gc.head) garbage_collector::global_gc.head = garbage_collector::global_gc.head->next;
            else if(ptr->prev) ptr->prev->next = ptr->next;
            if(ptr->next) ptr->next->prev = ptr->prev;
            delete ptr;
        }

        ptr = std::exchange(other.ptr, nullptr);

        return *this;
    }

    gcpointer<T> release() noexcept{
        node_ptr tmp = ptr;
        ptr = nullptr;
        return gcpointer<T>(tmp);
    }

    ~gcpointer(){
        if(garbage_collector::weak_state == garbage_collector::State::strong){
            if(ptr != nullptr && --ptr->ref_count == 0){
                if(ptr == garbage_collector::global_gc.head) garbage_collector::global_gc.head = garbage_collector::global_gc.head->next;
                else if(ptr->prev) ptr->prev->next = ptr->next;
                if(ptr->next) ptr->next->prev = ptr->prev;
                delete ptr;
            }
        }
    }
    template<typename U, typename... Ts>
    friend gcpointer<U> gcnew(Ts&&...);
};

template<typename U, typename... Ts>
gcpointer<U> gcnew(Ts&&... ts){
    if(!garbage_collector::global_gc.head)
        return gcpointer<U>(
                garbage_collector::global_gc.head =
                new garbage_collector::Node(std::in_place_type<U>, nullptr, nullptr, std::forward<Ts>(ts)...)
        );
    else{
        return gcpointer<U>(
                garbage_collector::global_gc.head =
                garbage_collector::global_gc.head->prev =
                new garbage_collector::Node(std::in_place_type<U>, nullptr, garbage_collector::global_gc.head, std::forward<Ts>(ts)...)
        );
    }
}

}

Use and test:

#include <iostream>
#include "gc.hpp"

struct cat{
    cat(){ std::cout << "cat default ctor" << std::endl; }
    cat(const cat&){ std::cout << "cat copy ctor" << std::endl; }
    cat(cat&&){ std::cout << "cat move ctor" << std::endl; }

    cat& operator=(const cat&){ std::cout << "cat copy operator=" << std::endl; return *this;}
    cat& operator=(cat&&){ std::cout << "cat move operator=" << std::endl; return *this;}

    ~cat(){ std::cout << "cat dtor" << std::endl; }
};

struct B;
struct A{
    A(){ std::cout << "A default ctor" << std::endl; }
    A(const A&){ std::cout << "A copy ctor" << std::endl; }
    A(A&&){ std::cout << "A move ctor" << std::endl; }

    A& operator=(const A&){ std::cout << "A copy operator=" << std::endl; return *this;}
    A& operator=(A&&){ std::cout << "A move operator=" << std::endl; return *this;}

    ~A(){ std::cout << "A dtor" << std::endl; }
    lambcoder::gcpointer<B> ptr;
};
struct B{
    B(){ std::cout << "B default ctor" << std::endl; }
    B(const B&){ std::cout << "B copy ctor" << std::endl; }
    B(B&&){ std::cout << "B move ctor" << std::endl; }

    B& operator=(const B&){ std::cout << "B copy operator=" << std::endl; return *this;}
    B& operator=(B&&){ std::cout << "B move operator=" << std::endl; return *this;}

    ~B(){ std::cout << "B dtor" << std::endl; }
    lambcoder::gcpointer<A> ptr;
};

int main(){
    auto gcp = lambcoder::gcnew<int>(2);
    auto gcpcat1 = lambcoder::gcnew<cat>(), gcpcat2 = lambcoder::gcnew<cat>(*gcpcat1);
    std::cout << *gcp << std::endl;

    auto gcb = lambcoder::gcnew<B>();
    auto gca = lambcoder::gcnew<A>();
    gcb->ptr = gca;
    gca->ptr = gcb;
    std::cout << "Done!\n";
}

Output:

cat default ctor
cat copy ctor
2
B default ctor
A default ctor
Done!
cat dtor
cat dtor
A dtor
B dtor

As can be seen from the output, no memory leaks occurred.

Pros:

• Easy to use.

Cons:

• Involves double allocation per element.
• Doesn't reuse memory space.
• High overhead (up to 26 bytes per element: three pointers and 2 bytes worth of reference count).
• Isn't much better (or better at all) than std::shared_ptr
• When in a scenario with two objects (like B and A) that reference each other, deletion of objects is delayed until the end of execution.
• Finally, custom allocators can't be used.

Questions:

• Is this use for this implementation of garbage collection? Does it have ANY advantage over std::shared_ptr and std::weak_ptr?

• The garbage collector deallocates Node's once their object is deallocated. Should the garbage collector instead reuse the Node?

• At the current moment, custom allocators are not allowed because the garbage collector might have to manually deallocate memory, and Node's are untyped and don't store an allocator. Should the design change so that garbage collectors for certain types (passed a certain allocator type in the template arguments) must be declared and gcpointer's created from them? With this approach, one allocation could be eliminated (since Node's would be typed) Usage of this approach would look something like this:

   lambcoder::garbage_collector<std::allocator<int>> gcint;
   auto gcpi = gcint.gcnew(2);
   lambcoder::garbage_collector<std::allocator<cat>> gccat;
   auto gcpcat1 = gccat.gcnew(), gcpcat2 = gccat.gcnew(*gcpcat1);
  

• Should I keep my current design, but add the aforementioned?

• Is there any way to allocate the object with its Node? Should I?

• Are there any other design changes that are recommended?

Answer 1

First, we need to fix the errors.

• The most obvious one is that the #ifndef GC_HPP_ has no matching #endif.
• We're missing an include of <cstdint> for the fixed-width integer types.
• We're missing <utility> for std::exchange, std::forward and std::in_place_type.

With those addressed, we can inspect the code.

It's not clear why we need exact-sized types, rather than (e.g. std::uint_fast16_t). Is it important that the ref-count overflows once there's 65536 pointers to an object? I would expect a std::size_t to be a safer choice.

Node should have deleted copy constructor and assignment operator, to prevent unintended double ownership of the raw pointers next and prev.

garbage_collector itself should also be made non-copyable.

It's better to explicitly default the constructor, rather than provide one with an empty body:

garbage_collector() = default;

I don't see why weak_state is shared across all the garbage collector instances. Shouldn't it be local to each one?

No need for this-> in the operator definitions:

constexpr T* operator->(){
    return ptr ? &operator*() : nullptr;
}
constexpr operator T*(){
    return operator->();
}

The common code to decrement reference count and possibly free a node is written out three times. This should be refactored into a private function.

Overall, I'd say the biggest design flaw is the assumption of a singleton. Not only does it make it hard to properly unit-test the collector, but it defeats an obvious use case, where a data structure wants to clean up its own members (but only its own) when it is destructed. That's easily fixed, of course, at the expense of having a reference member in each Node.

Answer 2

In addition to Toby's answer:

Remove operator T*()

This is quite dangerous: it allows implicit casts from a garbage collected pointer to a raw pointer to the object. Note that std::shared_ptr doesn't have such a cast operator.

Consider making garbage_collector templated as well

Instead of having one garbage collector for all objects, it is possible to create individual garbage collectors for each type T, by making garbage_collector a template<typename T> as well. This reduces the size of the global linked lists, which might be handy if you do implement some form of intermediate garbage collection.

Cycles are only cleaned up on program exit

If you want to be better than std::shared_ptr, you want to be able to detect and clean up cycles while a program is still running. At the moment, cycles are not cleaned up until the global garbage_collector object(s) are destroyed. However, a program might want to ensure at some point that all objects are cleaned up. Consider adding a function to force all objects maintained by a garbage_collector to be destroyed.

Of course, it would be better to avoid writing a program where such cycles can occur, but then you probably also wouldn't need a garbage collector anymore.