Garbage Collector & C++

Ручное управление памятью с С++ — одновременно один из самых больших плюсов и минусов в языке. Действительно, эта парадигма позволяет создавать очень производительные программы, однако она же рождает и кучу проблем. Существует несколько способов избавится от них. Я попробовал несколько и в итоге пришел к сборщику мусора. В этой статье я хочу изложить не столько реализацию сборщика мусора на С++, сколько историю идеи и его использования, каково им пользоваться и почему в итоге от него отказался.



Итак, как у большинства программистов у меня есть свой проект, а именно двумерный игровой движок. На нем и производились все «эксперименты».

Этап первый: отладка памяти

Самая часто встречающаяся проблема при ручном управлении памятью — это утечки. Чтобы узнать о них нужно следить за памятью. Именно таков и был мой первоначальных подход. Следим за созданием и удалением объектов, проверяем после завершения программы что осталось не удаленным. Делается очень просто: перегружаем операторы new и delete, чтобы они могли принимать в параметрах имя файла исходного кода и строчку, откуда происходит аллокация, и храним все аллокации в одном месте. Для удобства объявляем макрос, который и передает имя файла и строку в оператор. Соответственно при удалении объекта удаляем запись о соответствующей аллокации.

Код

#include <vector>

class MemoryManager
{
	struct AllocInfo
	{
		const char* source;
		int         line;
		int         size;
		void*       data;
	};

	static MemoryManager   instance;
	std::vector<AllocInfo> allocations;

public:
	static void RegAllocation(void* ptr, int size, const char* source, int line)
	{
		AllocInfo info;
		info.data = ptr;
		info.size = size;
		info.source = source;
		info.line = line;

		instance.allocations.push_back(info);
	}

	static void UnregAllocation(void* ptr)
	{
		for (std::vector<AllocInfo>::iterator it = instance.allocations.begin(); it != instance.allocations.end(); ++it)
		{
			if (it->data == ptr)
			{
				instance.allocations.erase(it);
				return;
			}
		}
	}

	static void PrintInfo()
	{
		for (std::vector<AllocInfo>::iterator it = instance.allocations.begin(); it != instance.allocations.end(); ++it)
			printf("0x%x: %i bytes at %s: %i", it->data, it->size, it->source, it->line);
	}
};

MemoryManager MemoryManager::instance;

void* operator new(size_t size, const char* location, int line)
{
	void* res = ::operator new(size);
	MemoryManager::RegAllocation(res, size, location, line);
	return res;
}

void  operator delete(void* allocMemory, const char* location, int line)
{
	MemoryManager::UnregAllocation(allocMemory);
}

void  operator delete(void* allocMemory)
{
	MemoryManager::UnregAllocation(allocMemory);
}

#define mnew new(__FILE__, __LINE__)

int main()
{
	int* data = mnew int;

	MemoryManager::PrintInfo();

    return 0;
}

Плюсы

• просто и понятно
• не затратно в плане ресурсов
• в ходе выполнения программы мы знаем количество задействованной памяти

Минусы

• чтобы узнать об утечках, нужно завершать программу
• не очень информативно откуда именно происходят аллокации
• использование перегруженных операторов немного меняет синтаксис

Этап второй: умные указатели

И правда же, самое распространенное решение проблемы управления памятью — умные указатели. О них вас обязательно спросят на собеседовании. Идея проста: вместо обычных указателей мы используем шаблонные классы, которые работают как указатели, но имеют дополнительный функционал для автоматического освобождения объектов. Вместе с объектом храним счетчик ссылок, при присваивании значения указателю увеличиваем счетчик, при уничтожении указателя — уменьшаем. Если счетчик равен нулю — объект никому не нужен и его можно освободить. Однако, есть небольшая проблема — если два объекта ссылаются друг на друга, они никогда не будут освобождены, так как у обоих счетчик ссылок равен единице.



Слабые указатели решают эту проблему зацикленности. Один из указателей делается слабым, и теперь счетчики ссылок равны нулю и оба объекта могут быть освобождены.



Что ж, давайте придумаем ситуацию посложнее.



Такую ситуацию тоже можно разрешить с помощью слабых/сильных указателей, но будет ли это легче ручного управления? Если программист что-то сделает неправильно, результат будет такой же: утекший неосвобожденный объект. На самом деле, такие ситуации встречаются редко и в целом такой подход значительно упрощает работу с памятью.

Плюсы

• не требует много ресурсов
• гарантирует корректное освобождение объектов при правильной архитектуре
• просто в освоении

Минусы

• усложняет синтаксис
• в некоторых ситуациях сложно правильно выстроить слабые/сильные указатели
• зацикленные ссылки приводят к утечкам

Этап третий: велосипедостроительство

Опробовав умные указатели, я остался неудовлетворен. Просто хочется использовать один у тот же тип умного указателя везде и не задумываться о зацикленных ссылках. Пусть он сам о них задумывается. Но как это сделать? Представим ситуацию:



Нужно как-то узнать что два нижних объекта зациклены и их можно удалить, ведь на них никто не ссылается. По рисунку уже несложно догадаться: если ссылки от объекта не ведут к верхнеуровневым объектам, значит он может быть освобожден. Верхнеуровневые объекты — это, грубо говоря, те объекты, с которых начинается инициализация приложения. Для С++ это объекты на стеке и статические.

Этап четвертый: сборщик мусора

Думаю, внимательный читатель уже понял, что это и есть схема работы сборщика мусора, только наоборот. Самый простой сборщик работает примерно так: спускаясь по ссылкам о�� верхнеуровневых объектов помечаем всех как актуальные, после этого мы имеем право удалить те, что оказались не помеченными.



Для реализации нам потребуется такой же шаблонный класс указателя, как и в случае с умными указателями. Плюс нужен сам сборщик, который будет за всем следить и производить собственно сборку мусора.

Чуть больше кода

#include <vector>
#include <map>
#include <algorithm>

class IPtr;

template<typename T>
struct Destroyer
{
	static void Destroy(void* obj)
	{ 
		(*(T*)(obj)).~T();
	}
};

class MemoryManager
{
public:
	struct ObjectInfo
	{
		void*              object;
		size_t             size;
		bool               mark;
		const char*        source;
		int                line;
		std::vector<IPtr*> pointers;

		void(*destroy)(void*) = nullptr;
	};

private:
	static MemoryManager         instance;
	std::map<void*, ObjectInfo*> objects;
	std::vector<IPtr*>           pointers;
	size_t                       allocatedBytes = 0;
	bool                         currentMark = true;

public:
	static void CollectGarbage();

protected:
	void MarkObject(ObjectInfo* info);

	friend void* operator new(size_t size, const char* source, int line);
	friend void operator delete(void* object, const char* source, int line);
	friend void operator delete(void* object);

	template<typename T>
	friend class Ptr;
};

MemoryManager MemoryManager::instance;

class IPtr
{
protected:
	void*                      object;
	MemoryManager::ObjectInfo* info;

public:
	virtual ~IPtr() {}
	virtual bool IsRoot() const = 0;

protected:
	void MarkInvalid()
	{
		object = nullptr;
		info = nullptr;
	}

	friend void operator delete(void* object);
	friend class MemoryManager;
};

template<typename T>
class Ptr: public IPtr
{
public:
	Ptr()
	{
		object = nullptr;
		info = nullptr;

		MemoryManager::instance.pointers.push_back(this);
	}

	Ptr(T* object)
	{
		this->object = object;

		auto fnd = MemoryManager::instance.objects.find(object);
		if (fnd != MemoryManager::instance.objects.end())
		{
			info = fnd->second;
			info->pointers.push_back(this);

			if (!info->destroy)
				info->destroy = &Destroyer<T>::Destroy;
		}

		MemoryManager::instance.pointers.push_back(this);
	}

	Ptr(const Ptr<T>& other)
	{
		object = other.object;
		info = other.info;

		if (info)
			info->pointers.push_back(this);

		MemoryManager::instance.pointers.push_back(this);
	}

	~Ptr()
	{
		if (info)
		{
			auto fnd = std::find(info->pointers.begin(), info->pointers.end(), this);
			if (fnd != info->pointers.end())
				info->pointers.erase(fnd);
		}

		auto fnd = std::find(MemoryManager::instance.pointers.begin(), MemoryManager::instance.pointers.end(), this);
		if (fnd != MemoryManager::instance.pointers.end())
			MemoryManager::instance.pointers.erase(fnd);
	}

	T* Get() const
	{
		return (T*)object;
	}

	bool IsValid() const
	{
		return object != nullptr;
	}

	bool IsRoot() const
	{
		return false;
	}

	operator bool()
	{
		return object != nullptr;
	}

	operator T*()
	{
		return (T*)object;
	}

	T* operator->()
	{
		return (T*)object;
	}

	T& operator*()
	{
		return *(T*)object;
	}

	const T& operator*() const
	{
		return *(T*)object;
	}

	Ptr<T>& operator=(const Ptr<T>& other)
	{
		if (info)
		{
			auto fnd = std::find(info->pointers.begin(), info->pointers.end(), this);
			if (fnd != info->pointers.end())
				info->pointers.erase(fnd);
		}

		object = other.object;
		info = other.info;

		if (info)
			info->pointers.push_back(this);

		return *this;
	}

	Ptr<T>& operator=(T* other)
	{
		if (info)
		{
			auto fnd = std::find(info->pointers.begin(), info->pointers.end(), this);
			if (fnd != info->pointers.end())
				info->pointers.erase(fnd);
		}

		object = other; 
		
		auto fnd = MemoryManager::instance.objects.find(object);
		if (fnd != MemoryManager::instance.objects.end())
		{
			info = fnd->second;
			info->pointers.push_back(this);

			if (!info->destroy)
				info->destroy = &Destroyer<T>::Destroy;
		}
		else info = nullptr;

		return *this;
	}
};

template<typename T>
class RootPtr: public Ptr<T>
{
public:
	RootPtr():Ptr() {}

	RootPtr(T* object):Ptr(object) {}

	RootPtr(const Ptr<T>& other):Ptr(other) {}

	bool IsRoot() const
	{
		return true;
	}

	operator bool()
	{
		return object != nullptr;
	}

	operator T*()
	{
		return (T*)object;
	}

	T* operator->()
	{
		return (T*)object;
	}

	T& operator*()
	{
		return *(T*)object;
	}

	const T& operator*() const
	{
		return *(T*)object;
	}

	RootPtr<T>& operator=(const Ptr<T>& other)
	{
		Ptr<T>::operator=(other);
		return *this;
	}

	RootPtr<T>& operator=(T* other)
	{
		Ptr<T>::operator=(other);
		return *this;
	}
};

void* operator new(size_t size, const char* source, int line)
{
	void* res = malloc(size);

	MemoryManager::ObjectInfo* objInfo = new MemoryManager::ObjectInfo();
	objInfo->object = res;
	objInfo->size = size;
	objInfo->mark = MemoryManager::instance.currentMark;
	objInfo->source = source;
	objInfo->line = line;

	MemoryManager::instance.objects[res] = objInfo;
	MemoryManager::instance.allocatedBytes += size;

	return res;
}

void operator delete(void* data, const char* source, int line)
{
	delete data;
}

void operator delete(void* data)
{
	auto fnd = MemoryManager::instance.objects.find(data);

	if (fnd != MemoryManager::instance.objects.end())
	{
		MemoryManager::instance.allocatedBytes -= fnd->second->size;

		for (auto ptr : fnd->second->pointers)
			ptr->MarkInvalid();

		delete fnd->second;
		MemoryManager::instance.objects.erase(fnd);
	}

	free(data);
}

void MemoryManager::CollectGarbage()
{
	instance.currentMark = !instance.currentMark;

	for (auto ptr : instance.pointers)
	{
		if (ptr->IsRoot())
		{
			if (ptr->info)
				instance.MarkObject(ptr->info);
		}
	}

	std::vector< std::map<void*, ObjectInfo*>::iterator > freeObjects;
	for (auto obj = instance.objects.begin(); obj != instance.objects.end(); ++obj)
	{
		if (obj->second->mark != instance.currentMark)
			freeObjects.push_back(obj);
	}

	for (auto obj : freeObjects)
	{
		instance.allocatedBytes -= obj->second->size;

		obj->second->destroy(obj->first);
		free(obj->first);

		for (auto ptr : obj->second->pointers)
			ptr->MarkInvalid();

		delete obj->second;
		instance.objects.erase(obj);
	}
}

void MemoryManager::MarkObject(ObjectInfo* info)
{
	info->mark = MemoryManager::instance.currentMark;

	char* left = (char*)info->object;
	char* right = left + info->size;

	for (auto ptr : instance.pointers)
	{
		char* cptr = (char*)ptr;
		if (cptr >= left && cptr < right)
		{
			if (ptr->info && ptr->info->mark != MemoryManager::instance.currentMark)
				MarkObject(ptr->info);
		}
	}
}

#define mnew new(__FILE__, __LINE__)

struct B;
struct C;
struct D;

struct A
{
	Ptr<B> pb;
	Ptr<C> pc;

	A() { printf("A()\n"); }
	~A() { printf("~A()\n"); }
};

struct B
{
	Ptr<C> pc;

	B() { printf("B()\n"); }
	~B() { printf("~B()\n"); }
};

struct C
{
	Ptr<D> pd;

	C() { printf("C()\n"); }
	~C() { printf("~C()\n"); }
};

struct D
{
	Ptr<C> pc;

	D() { printf("D()\n"); }
	~D() { printf("~D()\n"); }
};

int main()
{
	RootPtr<A> pa = mnew A;

	pa->pb = mnew B;
	pa->pc = mnew C;

	pa->pc->pd = mnew D;
	pa->pc->pd->pc = pa->pc;

	pa->pc = nullptr;

	MemoryManager::CollectGarbage();

    return 0;
}

Как это работает

Для каждого созданного объекта создается мета-информация ObjectInfo и хранится в менеджере памяти MemoryManager. Каждый такой объект создается перегруженным оператором new. ObjectInfo хранит в себе информацию о размере объекта, месте, откуда он был создан, список указателей на него и указатель на функцию для вызова деструктора этого объекта.

Для работы с объектами вместо привычных указателей используются шаблонные классы Ptr и RootPtr. RootPtr необходим для обозначения верхнеуровневых объектов, так как в ходе выполнения программы невозможно узнать что объект создан на стеке или статически (поправьте меня, если я не прав). При инициализации или копировании указателей происходит добавление и удаление указателей из соответствующих ObjectInfo.

При вызове сборки мусора меняется булевая переменная маркера на противоположную и начинается цикл отметки объектов. Цикл проходит по верхнеуровневым указателям, затем рекурсивно по их дочерним указателям. Дочерний указатель — это тот, что находится в теле объекта. После этого все объекты, у которых маркер не совпадает с текущим удаляются.

Внимательный читатель наверняка заметил еще одно — за удобство мы платим производительностью. Мы получаем все типичные минусы сборщиков мусора: излишний расход памяти и большое время работы сборки мусора. Именно на моем проекте игрового движка это фатальный минус, ведь на каждый кадр должно уходить несколько миллисекунд и просто нет времени чтобы все остановить и произвести сборку мусора. Однако, есть и хороший момент, этот сборщик мусора полностью наш и мы можем делать все что захотим!

Этап пятый: импровизация

Первое что приходит в голову — это то, что мы полностью управляем моментом сборки мусора. Совсем не обязательно делать это посреди геймплея. Можно сделать это как раз тогда, когда и происходит наибольшее количество инициализаций и уничтожений объектов, во время загрузки уровней. При разработке игр не принято делать много аллокаций/уничтожений во время активной игры. Если при каждом выстреле загружать и создавать объект пули, никакая оптимизация памяти вас не спасет. Поэтому делать долгую сборку мусора между уровнями кажется довольно живучей идеей.

Следующая идея — вовсе не вызывать сборку мусора или делать это крайне редко. Объекты по-прежнему удалять вручную или умными указателями, а сборщик мусора можно использовать в роли отладчика и подстраховки. В таком варианте мы получим производительность эквивалентную ручному управлению памятью и безопасность от утечек при сборке мусора.

Таким образом мы можем использовать сборщик по-разному. При быстром прототипировании нас не заботит производительность, но нужна стабильность, в этом случае используем автоматическую сборку. В обычной ситуации стараемся вручную управлять памятью, а сборщик нам подсказывает и подстраховывает. Ну и кон��чно же его можно просто выключить и перейти к полностью ручному управлению.

Помимо этого можно реализовать еще немного «вкусностей». Так как мы используем шаблонные классы-указатели, мы можем проверять их на корректность, то есть при удалении объекта вручную делать все ссылки на него невалидными. И далее в нужных местах их проверять. Еще одно из возможных улучшений — это дефрагментация памяти. На этапе сборки мусора можно перерасположить актуальные объекты в памяти для уменьшения кеш-промахов процессора, что несомненно даст прирост производительности.

Плюсы

• защищенность от утечек и использования некорректных указателей
• минимальные затраты при работе в полуавтоматическом режиме
• максимальное удобство при полностью автоматическом режиме

Минусы

• усложнение синтаксиса
• необходимо понимание схемы работы и использования
• процесс сборки мусора все еще занимает значительное время

Этап шестой: возврат к началу

В конце концов на решение об отказе от сборщика повлияла специфика моего проекта. Проект планируется с открытым исходным кодом и он нацелен прежде всего на удобство использования. Усложнение и без того сложного синтаксиса С++ специфичными указателями и добавление сборщика мусора несомненно плохо повлияют на проект. Просто представьте знакомство разработчика с новой технологией: ему необходимо изучать новое API да еще и с мудреной моделью управления памятью, тем более, что большинство программистов С++ и так неплохо управляются с памятью вручную.
Окончательно я убедился в возврате к ручной модели когда принял решение использовать скрипты. Именно они нужны для простоты и удобства. Делаешь прототип или простую игру — используй скрипты, экономь время и ресурсы. Необходима гибкость и производительность — добро пожаловать в С++. Тем, кто будет использовать С++ на самом деле вряд ли понадобится сборщик мусора.

Вот так я и вернулся к началу. Надеюсь мой опыт будет полезен или хотя бы интересен другим велосипедостроителям.

P.S. Код из статьи не оптимизирован и приведен лишь для понимания работы.