C++ mark & sweep toy gc

marksweep.cpp

#include <cstddef>
#include <cstdint>
#include <iostream>
#include <variant>
#include <vector>

typedef int64_t i64;
typedef uint64_t u64;
typedef float f32;
typedef double f64;
typedef size_t usize;

static usize totalAlloc = 0;
static usize totalDealloc = 0;
static usize totalGCCalls = 0;
static usize totalGCTime = 0;

struct Object;

class ObjectValue {
public:
  typedef f64 Numeric;
  typedef std::vector<Object *> Array;

private:
  typedef std::variant<Numeric, Array> Value;

  Value value;

  ObjectValue(Value val) : value{val} {}

  template <typename T>
  T &getOrPanic() noexcept {
    if (T *val = std::get_if<T>(&value)) {
      return *val;
    }

    std::cerr << "failed to get value\n";
    exit(EXIT_FAILURE);
  }

public:
  static ObjectValue initNumeric(Numeric num) {
    return ObjectValue(num);
  }

  static ObjectValue initArray() {
    return ObjectValue(Array());
  }

  Array &asArray() {
    return getOrPanic<Array>();
  }

  Numeric &asNumeric() {
    return getOrPanic<Numeric>();
  }

  bool isNumeric() const {
    return std::holds_alternative<Numeric>(value);
  }

  bool isArray() const {
    return std::holds_alternative<Array>(value);
  }
};

struct Object {
  Object *next = nullptr;
  ObjectValue value;
  bool isMarked = false;

  void mark() {
    if (isMarked)
      return;
    isMarked = true;
    if (value.isArray()) {
      for (int i = 0; i < value.asArray().size(); i++) {
        value.asArray()[i]->mark();
      }
    }
  }
};

const usize MaxStackSize = 1000;
const usize GCThreshold = 1000;

class VM {
  Object *heapObjects = nullptr;
  Object *stack[MaxStackSize] = {nullptr};
  usize stackSize = 0;
  usize heapMaxObjects = 0;
  usize heapObjectsCnt = 0;

  void gcMarkAll() {
    for (int i = 0; i < stackSize; i++) {
      stack[i]->mark();
    }
  }

  void gcSweep() {
    auto **obj = &heapObjects;
    while (*obj) {
      if ((*obj)->isMarked) {
        (*obj)->isMarked = false;
        obj = &(*obj)->next;
      } else {
        auto *tmp = (*obj)->next;
        delete *obj;
        totalDealloc++;
        heapObjectsCnt--;
        *obj = tmp;
      }
    }
  }

public:
  VM() = default;
  ~VM() {
    gc();
  }

  Object *newObject(ObjectValue value) {
    if (heapObjectsCnt >= heapMaxObjects)
      gc();

    auto *obj = new (Object){.value = value};
    obj->next = heapObjects;
    heapObjects = obj;
    heapObjectsCnt++;
    totalAlloc++;

    return obj;
  }

  void push(Object *obj) {
    stack[stackSize++] = obj;
  }

  Object *pop() {
    return stack[--stackSize];
  }

  void gc() {
    totalGCCalls++;

    gcMarkAll();
    gcSweep();
    heapMaxObjects = heapObjectsCnt == 0 ? GCThreshold : heapObjectsCnt * 2;
  }
};

int main() {
  VM vm;
  for (int i = 0; i < MaxStackSize; i++) {
    for (int k = 0; k < i; k++) {
      auto *obj = vm.newObject(ObjectValue::initArray());
      vm.push(obj);
      for (int j = 0; j < 1000; j++) {
        obj->value.asArray().push_back(vm.newObject(ObjectValue::initNumeric(j)));
      }
    }

    for (int k = 0; k < i; k++) {
      vm.pop();
    }

    vm.gc();

    std::cout << '.' << std::flush;
  }

  std::cout << "\n\n";
  std::cout << "total alloc:\t" << totalAlloc << '\n';
  std::cout << "total dealloc:\t" << totalDealloc << '\n';
  std::cout << "GC calls:\t" << totalGCCalls << '\n';
  std::cout << '\n';

  return 0;
}