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() {}
віртуальний 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;
}

bool operator()
{
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;
}

bool operator()
{
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. Код з статті не оптимізований і наведено лише для розуміння роботи.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.