anz 26 апр 2016 в 23:44

Garbage Collector & C++

11 мин

32K

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

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

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

Самая часто встречающаяся проблема при ручном управлении памятью — это утечки. Чтобы узнать о них нужно следить за памятью. Именно таков и был мой первоначальных подход. Следим за созданием и удалением объектов, проверяем после завершения программы что осталось не удаленным. Делается очень просто: перегружаем операторы 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. Код из статьи не оптимизирован и приведен лишь для понимания работы.

Теги:

C++ GC memory

Хабы:

Garbage Collector & C++

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

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

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

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

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

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

Публикации

Истории

Работа

Ближайшие события