Ручное управление памятью с С++ — одновременно один из самых больших плюсов и минусов в языке. Действительно, эта парадигма позволяет создавать очень производительные программы, однако она же рождает и кучу проблем. Существует несколько способов избавится от них. Я попробовал несколько и в итоге пришел к сборщику мусора. В этой статье я хочу изложить не столько реализацию сборщика мусора на С++, сколько историю идеи и его использования, каково им пользоваться и почему в итоге от него отказался.
Итак, как у большинства программистов у меня есть свой проект, а именно двумерный игровой движок. На нем и производились все «эксперименты».
Самая часто встречающаяся проблема при ручном управлении памятью — это утечки. Чтобы узнать о них нужно следить за памятью. Именно таков и был мой первоначальных подход. Следим за созданием и удалением объектов, проверяем после завершения программы что осталось не удаленным. Делается очень просто: перегружаем операторы new и delete, чтобы они могли принимать в параметрах имя файла исходного кода и строчку, откуда происходит аллокация, и храним все аллокации в одном месте. Для удобства объявляем макрос, который и передает имя файла и строку в оператор. Соответственно при удалении объекта удаляем запись о соответствующей аллокации.
Плюсы
Минусы
И правда же, самое распространенное решение проблемы управления памятью — умные указатели. О них вас обязательно спросят на собеседовании. Идея проста: вместо обычных указателей мы используем шаблонные классы, которые работают как указатели, но имеют дополнительный функционал для автоматического освобождения объектов. Вместе с объектом храним счетчик ссылок, при присваивании значения указателю увеличиваем счетчик, при уничтожении указателя — уменьшаем. Если счетчик равен нулю — объект никому не нужен и его можно освободить. Однако, есть небольшая проблема — если два объекта ссылаются друг на друга, они никогда не будут освобождены, так как у обоих счетчик ссылок равен единице.
Слабые указатели решают эту проблему зацикленности. Один из указателей делается слабым, и теперь счетчики ссылок равны нулю и оба объекта могут быть освобождены.
Что ж, давайте придумаем ситуацию посложнее.
Такую ситуацию тоже можно разрешить с помощью слабых/сильных указателей, но будет ли это легче ручного управления? Если программист что-то сделает неправильно, результат будет такой же: утекший неосвобожденный объект. На самом деле, такие ситуации встречаются редко и в целом такой подход значительно упрощает работу с памятью.
Плюсы
Минусы
Опробовав умные указатели, я остался неудовлетворен. Просто хочется использовать один у тот же тип умного указателя везде и не задумываться о зацикленных ссылках. Пусть он сам о них задумывается. Но как это сделать? Представим ситуацию:
Нужно как-то узнать что два нижних объекта зациклены и их можно удалить, ведь на них никто не ссылается. По рисунку уже несложно догадаться: если ссылки от объекта не ведут к верхнеуровневым объектам, значит он может быть освобожден. Верхнеуровневые объекты — это, грубо говоря, те объекты, с которых начинается инициализация приложения. Для С++ это объекты на стеке и статические.
Думаю, внимательный читатель уже понял, что это и есть схема работы сборщика мусора, только наоборот. Самый простой сборщик работает примерно так: спускаясь по ссылкам о�� верхнеуровневых объектов помечаем всех как актуальные, после этого мы имеем право удалить те, что оказались не помеченными.
Для реализации нам потребуется такой же шаблонный класс указателя, как и в случае с умными указателями. Плюс нужен сам сборщик, который будет за всем следить и производить собственно сборку мусора.
Внимательный читатель наверняка заметил еще одно — за удобство мы платим производительностью. Мы получаем все типичные минусы сборщиков мусора: излишний расход памяти и большое время работы сборки мусора. Именно на моем проекте игрового движка это фатальный минус, ведь на каждый кадр должно уходить несколько миллисекунд и просто нет времени чтобы все остановить и произвести сборку мусора. Однако, есть и хороший момент, этот сборщик мусора полностью наш и мы можем делать все что захотим!
Первое что приходит в голову — это то, что мы полностью управляем моментом сборки мусора. Совсем не обязательно делать это посреди геймплея. Можно сделать это как раз тогда, когда и происходит наибольшее количество инициализаций и уничтожений объектов, во время загрузки уровней. При разработке игр не принято делать много аллокаций/уничтожений во время активной игры. Если при каждом выстреле загружать и создавать объект пули, никакая оптимизация памяти вас не спасет. Поэтому делать долгую сборку мусора между уровнями кажется довольно живучей идеей.
Следующая идея — вовсе не вызывать сборку мусора или делать это крайне редко. Объекты по-прежнему удалять вручную или умными указателями, а сборщик мусора можно использовать в роли отладчика и подстраховки. В таком варианте мы получим производительность эквивалентную ручному управлению памятью и безопасность от утечек при сборке мусора.
Таким образом мы можем использовать сборщик по-разному. При быстром прототипировании нас не заботит производительность, но нужна стабильность, в этом случае используем автоматическую сборку. В обычной ситуации стараемся вручную управлять памятью, а сборщик нам подсказывает и подстраховывает. Ну и кон��чно же его можно просто выключить и перейти к полностью ручному управлению.
Помимо этого можно реализовать еще немного «вкусностей». Так как мы используем шаблонные классы-указатели, мы можем проверять их на корректность, то есть при удалении объекта вручную делать все ссылки на него невалидными. И далее в нужных местах их проверять. Еще одно из возможных улучшений — это дефрагментация памяти. На этапе сборки мусора можно перерасположить актуальные объекты в памяти для уменьшения кеш-промахов процессора, что несомненно даст прирост производительности.
Плюсы
Минусы
В конце концов на решение об отказе от сборщика повлияла специфика моего проекта. Проект планируется с открытым исходным кодом и он нацелен прежде всего на удобство использования. Усложнение и без того сложного синтаксиса С++ специфичными указателями и добавление сборщика мусора несомненно плохо повлияют на проект. Просто представьте знакомство разработчика с новой технологией: ему необходимо изучать новое API да еще и с мудреной моделью управления памятью, тем более, что большинство программистов С++ и так неплохо управляются с памятью вручную.
Окончательно я убедился в возврате к ручной модели когда принял решение использовать скрипты. Именно они нужны для простоты и удобства. Делаешь прототип или простую игру — используй скрипты, экономь время и ресурсы. Необходима гибкость и производительность — добро пожаловать в С++. Тем, кто будет использовать С++ на самом деле вряд ли понадобится сборщик мусора.
Вот так я и вернулся к началу. Надеюсь мой опыт будет полезен или хотя бы интересен другим велосипедостроителям.
P.S. Код из статьи не оптимизирован и приведен лишь для понимания работы.
Итак, как у большинства программистов у меня есть свой проект, а именно двумерный игровой движок. На нем и производились все «эксперименты».
Этап первый: отладка памяти
Самая часто встречающаяся проблема при ручном управлении памятью — это утечки. Чтобы узнать о них нужно следить за памятью. Именно таков и был мой первоначальных подход. Следим за созданием и удалением объектов, проверяем после завершения программы что осталось не удаленным. Делается очень просто: перегружаем операторы 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.
При вызове сборки мусора меняется булевая переменная маркера на противоположную и начинается цикл отметки объектов. Цикл проходит по верхнеуровневым указателям, затем рекурсивно по их дочерним указателям. Дочерний указатель — это тот, что находится в теле объекта. После этого все объекты, у которых маркер не совпадает с текущим удаляются.
Для работы с объектами вместо привычных указателей используются шаблонные классы Ptr и RootPtr. RootPtr необходим для обозначения верхнеуровневых объектов, так как в ходе выполнения программы невозможно узнать что объект создан на стеке или статически (поправьте меня, если я не прав). При инициализации или копировании указателей происходит добавление и удаление указателей из соответствующих ObjectInfo.
При вызове сборки мусора меняется булевая переменная маркера на противоположную и начинается цикл отметки объектов. Цикл проходит по верхнеуровневым указателям, затем рекурсивно по их дочерним указателям. Дочерний указатель — это тот, что находится в теле объекта. После этого все объекты, у которых маркер не совпадает с текущим удаляются.
Внимательный читатель наверняка заметил еще одно — за удобство мы платим производительностью. Мы получаем все типичные минусы сборщиков мусора: излишний расход памяти и большое время работы сборки мусора. Именно на моем проекте игрового движка это фатальный минус, ведь на каждый кадр должно уходить несколько миллисекунд и просто нет времени чтобы все остановить и произвести сборку мусора. Однако, есть и хороший момент, этот сборщик мусора полностью наш и мы можем делать все что захотим!
Этап пятый: импровизация
Первое что приходит в голову — это то, что мы полностью управляем моментом сборки мусора. Совсем не обязательно делать это посреди геймплея. Можно сделать это как раз тогда, когда и происходит наибольшее количество инициализаций и уничтожений объектов, во время загрузки уровней. При разработке игр не принято делать много аллокаций/уничтожений во время активной игры. Если при каждом выстреле загружать и создавать объект пули, никакая оптимизация памяти вас не спасет. Поэтому делать долгую сборку мусора между уровнями кажется довольно живучей идеей.
Следующая идея — вовсе не вызывать сборку мусора или делать это крайне редко. Объекты по-прежнему удалять вручную или умными указателями, а сборщик мусора можно использовать в роли отладчика и подстраховки. В таком варианте мы получим производительность эквивалентную ручному управлению памятью и безопасность от утечек при сборке мусора.
Таким образом мы можем использовать сборщик по-разному. При быстром прототипировании нас не заботит производительность, но нужна стабильность, в этом случае используем автоматическую сборку. В обычной ситуации стараемся вручную управлять памятью, а сборщик нам подсказывает и подстраховывает. Ну и кон��чно же его можно просто выключить и перейти к полностью ручному управлению.
Помимо этого можно реализовать еще немного «вкусностей». Так как мы используем шаблонные классы-указатели, мы можем проверять их на корректность, то есть при удалении объекта вручную делать все ссылки на него невалидными. И далее в нужных местах их проверять. Еще одно из возможных улучшений — это дефрагментация памяти. На этапе сборки мусора можно перерасположить актуальные объекты в памяти для уменьшения кеш-промахов процессора, что несомненно даст прирост производительности.
Плюсы
- защищенность от утечек и использования некорректных указателей
- минимальные затраты при работе в полуавтоматическом режиме
- максимальное удобство при полностью автоматическом режиме
Минусы
- усложнение синтаксиса
- необходимо понимание схемы работы и использования
- процесс сборки мусора все еще занимает значительное время
Этап шестой: возврат к началу
В конце концов на решение об отказе от сборщика повлияла специфика моего проекта. Проект планируется с открытым исходным кодом и он нацелен прежде всего на удобство использования. Усложнение и без того сложного синтаксиса С++ специфичными указателями и добавление сборщика мусора несомненно плохо повлияют на проект. Просто представьте знакомство разработчика с новой технологией: ему необходимо изучать новое API да еще и с мудреной моделью управления памятью, тем более, что большинство программистов С++ и так неплохо управляются с памятью вручную.
Окончательно я убедился в возврате к ручной модели когда принял решение использовать скрипты. Именно они нужны для простоты и удобства. Делаешь прототип или простую игру — используй скрипты, экономь время и ресурсы. Необходима гибкость и производительность — добро пожаловать в С++. Тем, кто будет использовать С++ на самом деле вряд ли понадобится сборщик мусора.
Вот так я и вернулся к началу. Надеюсь мой опыт будет полезен или хотя бы интересен другим велосипедостроителям.
P.S. Код из статьи не оптимизирован и приведен лишь для понимания работы.
