Немного теории
Не буду долго рассусоливать о том, что такое сборщик мусора и для чего он нужен (на эту тему уже есть достаточно статей). Но хочу отметить несколько важных деталей.
Сборщик мусора - один из способов решения проблемы контроля памяти.
Основное отличие от "умных" указателей с++ заключается в том, что подсчет ссылок на объекты и дальнейшее решение о высвобождении памяти происходит не в самом указателе, а в неком одном глобальном объекте. Очистка происходит не одного объекта, а всех, или порции невалидных.
Сборщик мусора - не аллокатор. Хоть проблема выделения/освобождения памяти затрагивает вопрос о фрагментации/дефрагментации кучи, но сборщик мусора не призван ее решать. Он может работать в связке со своим аллокатором, но основное его преимущество заключается в том, что память очищается не хаотично и не "лавинообразно".
Что хотим получить?
При написании игрового движка появилась потребность в автоматическом контроле памяти (удивительно, не правда ли?). Поэтому было решено написать свой сборщик мусора и заодно попытаться выжать из него максимум производительности.
Основные требования:
Скорость по выделению и освобождению памяти должна быть сравнима с обычными c-style указателями.
Объем затраченной памяти на работу сборщика может быть большим, но разумным.
Сборщик должен предоставлять удобный интерфейс сравни "умным" указателям.
Основная идея жизни объектов - объект жив до тех пор, пока существует кто-то, кто ссылается на него, но возможно прямое удаление объекта.
Идея и ее развитие
Возьмем за основу архитектуру "умных" указателей и перенесем всю работу с ссылками на объекты в некий singleton.
Действующие лица:
template<typename T> struct TGCPointer; //наш умный указатель
class GGarbageCollector; // сборщик мусораВ нашем случае отдельный класс под слабые ссылки не нужен, так как наша парадигма подразумевает использование только одного типа указатель, а создание слабой ссылки происходит за счет использования обычного указателя.
Подразумевается, что проект со сборщиком мусора использует только предоставляемый новый умный указатель, а обычные указатели использует только либо в контексте слабой ссылки, либо в изолированных системах с ручным контролем памяти.
TGCPointer<int> A; // сильная ссылка
int* B; //слабая ссылка1) Начало
Обозначим интерфейс работы.
GGarbageCollector
Hidden text
/*
Main garbage manager.
*/
class GGarbageCollector
{
public:
static inline GGarbageCollector* Get()
{
static GGarbageCollector GC;
return &GC;
}
private:
inline GGarbageCollector() {}
public:
/*
Force collect garbage.
*/
inline void ForceGC()
{
//TODO, об этом далее
}
/*
@return total objects count who are under surveillance.
*/
inline unsigned int GetTotalObjectsCount() const noexcept
{
//TODO, об этом далее
}
/*
@return the number of objects destroyed at the last iteration of garbage collection.
*/
inline unsigned int GetLastGarbagedObjectsCount() const noexcept
{
//TODO, об этом далее
}
/*
@return index of the garbage collection iteration.
*/
inline unsigned int GetGarbageCollectionIndex() const noexcept
{
//TODO, об этом далее
}
/*
Check that object address is in GarbageCollector.
*/
inline bool IsGCObjectValid(const void* Object) const noexcept
{
//TODO, об этом далее
}
/*
Check that object address is in GarbageCollector and hasn't got any refs.
*/
inline bool IsGCObjectPendingToKill(const void* Object) const noexcept
{
//TODO, об этом далее
}
};Как видим, наш сборщик умеет не только собирать мусор, но и отвечать на вопрос о валидности адреса. Адрес - это число, поэтому у него можно спросить об обычном указателе, если конечно тот когда-то был виден сборщику, но об этом позже.
TGCPointer
Hidden text
template<typename T>
struct TGCPointer
{
public:
inline TGCPointer() {}
inline TGCPointer(T* InObject) : Object(InObject)
{
//TODO, об этом далее
}
inline TGCPointer(T* InObject, bool IsNew) : Object(InObject)
{
//TODO, об этом далее
}
inline TGCPointer(const TGCPointer& OtherGCPointer) :
Object(OtherGCPointer.Object)
{
//TODO, об этом далее
}
inline TGCPointer(TGCPointer&& OtherGCPointer) noexcept :
Object(OtherGCPointer.Object)
{
OtherGCPointer.Object = nullptr;
}
~TGCPointer()
{
//TODO, об этом далее
}
public:
operator bool()
{
return IsValid();
}
operator T*()
{
return Object;
}
inline T& operator*() const
{
return *Object;
}
inline T* operator->() const
{
return Object;
}
inline TGCPointer& operator=(const TGCPointer& InGCPointer)
{
if (InGCPointer.Object == Object) return *this;
//TODO, об этом далее
return *this;
}
inline TGCPointer& operator=(TGCPointer&& InGCPointer)
{
//TODO, об этом далее
return *this;
}
inline TGCPointer& operator=(T* Ptr)
{
if (Ptr == Object) return *this;
//TODO, об этом далее
return *this;
}
// операторы сравнения опустил, они очевидны
public:
inline bool IsValid() const noexcept
{
//TODO, об этом далее
}
inline T* Get() const noexcept
{
return Object;
}
inline T* GetChecked() const noexcept
{
if (!IsValid())
{
Object = nullptr;
}
return Object;
}
inline void Reset()
{
//TODO, об этом далее
Object = nullptr;
}
private:
/*
Owned object.
*/
T* Object = nullptr;
};
template<typename T, typename... Args>
TGCPointer<T> MakeGCPointer(...)
{
return TGCPointer<T>(new T(Args...));
}Здесь аналогичная ситуация. Наш указатель является оберткой над сишным указателем, но умеет говорить о валидности адреса (разумеется через сборщик мусора). Слабые ссылки в виде обычных указателей проверяются через сборщик мусора.
Из представленных интерфейсов пока не понятно, как это будет работать, но видна мечта - спрашивать систему о валидности адреса как числа.
2) Реализация
Для того, чтобы что-то сказать о валидности адреса, нужно сначала сохранить какую-то мета информацию о нем. В нашей системе эту информацию будет поставлять TGCPointer, но как ее хранить?
Для максимальной скорости динамической вставки в начало нам подходит односвязный список. Но как обеспечить максимальную скорость чтения? Обычный статический массив обладает этим свойством. Но ничего не бывает просто так. За скорость приходится платить памятью. Совместим статический массив и односвязный список. Так потребление памяти сборщиком будет равна const + число отслеживаемых объектов * размер информации об объекте.
Теперь обращение к элементу будет происходить не перебором всех элементов списка, а перебором некой его части. Хоть мы и не получили лучше асимптотику (все еще O(n)), но деленная на константу (2^k). Эту константу возьмем большой(65536 эквивалентно 64 KB или 1048576, что эквивалентно 1 MB) По замерам (о них в конце), другие значения сильного прироста не дают. Такое решения является оптимальным только в том случае, если наш сборщик рассчитан на работу менее с чем 2-3 миллионами объектов, но для игр этого оказывается достаточно + мы будем регулярно (но не очень часто) производить очистку.
Этот момент является ключевым, дальше будет производиться оптимизация.
3) Обмажемся абстракциями
FAddrHandler
Hidden text
/*
Helper struct to handle object references.
*/
struct FAddrHandler
{
public:
inline FAddrHandler() noexcept { }
inline FAddrHandler(size_t InAddr, unsigned int InCount) noexcept : Addr(InAddr), Count(InCount) { }
inline FAddrHandler(size_t InAddr) noexcept : Addr(InAddr) { }
inline FAddrHandler(const void* Ptr, unsigned int InCount) noexcept : Addr((size_t)Ptr), Count(InCount) { }
inline FAddrHandler(const void* Ptr) noexcept : Addr((size_t)Ptr) { }
public:
/*
Check that this handler represent any object.
*/
inline bool IsValid() const noexcept
{
return Addr != 0;
}
/*
Check that this object is a candidate to killing by any Garbage Collector.
@return true if this handler has object, but it has no references.
*/
inline bool IsPendingToKill() const noexcept
{
return Count == 0 && Addr != 0;
}
public:
/*
Object's memory address in integral type.
*/
size_t Addr = 0;
/*
Number of references to an object in the program.
*/
unsigned int Count = 0;
};
// операторы сравнения опустил, они очевидныТут ничего необычного. Как видно, мы реализуем сборщик мусора на основе подсчета ссылок.
FAnyPtrMap
Hidden text
/*
Helper struct for manage AddrHandlers.
@see FAddrHandler.
*/
struct FAnyPtrMap
{
public:
inline FAnyPtrMap() :
{
ItemMap = new std::forward_list<FAddrHandler>[BitsPackSize];
}
~FAnyPtrMap()
{
if (ItemMap != nullptr) delete[] ItemMap;
}
public:
FAddrHandler* AddPtr(const void* Ptr)
{
//if (Ptr == nullptr) return; //check
const size_t LAddr = (const size_t)Ptr;
std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
auto LItemsEnd = LItems.end();
auto LAddrHandler = std::find(LItems.begin(), LItemsEnd, LAddr);
if (LAddrHandler != LItemsEnd)
{
++LAddrHandler->Count;
return &LAddrHandler._Ptr->_Myval;
}
else
{
++TotalObjectsCount;
LItems.push_front(FAddrHandler(LAddr, 1));
return &LItems.front();
}
}
FAddrHandler* AddNewPtr(const void* Ptr)
{
//if (Ptr == nullptr) return; //check
const size_t LAddr = (const size_t)Ptr;
std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
++TotalObjectsCount;
LItems.push_front(FAddrHandler(LAddr, 1));
return &LItems.front();
}
FAddrHandler* RemovePtr(const void* Ptr)
{
//TODO, об этом далее
}
inline void RemovePtrByHandler(FAddrHandler* PtrHandler)
{
//TODO, об этом далее
}
void ClearInvalidPtrs()
{
//TODO, об этом далее
}
FAddrHandler* GetPtrHandler(const void* Ptr) const noexcept
{
//if(Ptr == nullptr); //check
const size_t LAddr = (const size_t)Ptr;
const std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
auto LItemsEnd = LItems.end();
auto LAddrHandler = std::find(LItems.begin(), LItemsEnd, LAddr);
if (LAddrHandler == LItemsEnd) return nullptr;
return &LAddrHandler._Ptr->_Myval;
}
inline unsigned int GetTotalObjectsCount() const noexcept
{
return TotalObjectsCount;
}
inline unsigned int GetLastGarbagedObjectsCount() const noexcept
{
return LastGarbagedObjectsCount;
}
inline int GetGarbageCollectionIndex() const noexcept
{
return GarbageCollectionIndex;
}
private:
inline unsigned int GetLocalAddr(size_t Addr) const noexcept
{
return Addr & BitsPackMask; // Addr % BitsPackSize
}
public:
const static unsigned int BitsPackSize = 1048576; //1 MB ~69MB in ram
const static int BitsPackMask = 0xfffff; // 20 bits 2^20 = 1048576
//const static unsigned int BitsPackSize = 65536; //64 KB ~4MB in ram
//const static int BitsPackMask = 0xffff; // 16 bits 2^16 = 65536
private:
std::forward_list<FAddrHandler>* ItemMap = nullptr;
/*
Total objects count who are under surveillance.
*/
unsigned int TotalObjectsCount = 0;
/*
The number of objects destroyed at the last iteration of ClearInvalidPtrs.
*/
unsigned int LastGarbagedObjectsCount = 0;
/*
Index of ClearInvalidPtrs iteration.
*/
int GarbageCollectionIndex = 0;
};Здесь и происходит вся основная работа. Замечу некоторые оптимизационные моменты:
Имеем два метода на добавление объекта. Один обычный (с проверкой на то, что он новый), второй без проверки. Это сильно экономит процессорное время в случае, если мы уверены, что объект точно новый.
Определение номера ячейки в статическом массиве является обычным взятием остатка от количества элементов. Но количество элементов кратно двойке, поэтому можем применить бинарную операцию (компилятор сам бы это сделал, но так спокойнее).
FGCPointerBase
Hidden text
/*
Base class for GC pointers.
*/
struct FGCPointerBase
{
public:
inline FGCPointerBase() {}
inline FGCPointerBase(const FGCPointerBase& OtherGCPointerBase) noexcept :
SyncAddrHandler(OtherGCPointerBase.SyncAddrHandler), SyncIndex(OtherGCPointerBase.SyncIndex)
{
}
inline FGCPointerBase(FGCPointerBase&& OtherGCPointerBase) noexcept:
SyncAddrHandler(OtherGCPointerBase.SyncAddrHandler), SyncIndex(OtherGCPointerBase.SyncIndex)
{
OtherGCPointerBase.SyncAddrHandler = nullptr;
}
protected:
/*
Initialize from other FGCPointerBase.
*/
inline void SyncInitFrom(const FGCPointerBase& Other) noexcept
{
SyncAddrHandler = Other.SyncAddrHandler;
SyncIndex = Other.SyncIndex;
}
/*
@param Ptr - Owned object to sync check.
@return true if this GCPointer synchronized with GC.
*/
inline bool IsSync(const void* Ptr) const noexcept
{
return SyncAddrHandler != nullptr && GGarbageCollector::Get()->GetGarbageCollectionIndex() == SyncIndex && *SyncAddrHandler == Ptr;
}
/*
Force synchronize this pointer with GC.
@return synchronization success.
*/
inline bool Sync(const void* Ptr) const noexcept
{
if (Ptr == nullptr)
{
SyncAddrHandler = nullptr;
return false;
}
GGarbageCollector* LGC = GGarbageCollector::Get();
if (SyncAddrHandler != nullptr && LGC->GetGarbageCollectionIndex() == SyncIndex && *SyncAddrHandler == Ptr) return true;
SyncAddrHandler = LGC->GetPtrHandler(Ptr);
SyncIndex = LGC->GetGarbageCollectionIndex();
return SyncAddrHandler != nullptr;
}
/*
@param Ptr - Owned object to synchronized register in GC.
*/
inline void SyncRegister(const void* Ptr)
{
if (Ptr == nullptr)
{
SyncAddrHandler = nullptr;
return;
}
GGarbageCollector* LGC = GGarbageCollector::Get();
if (SyncAddrHandler != nullptr && LGC->GetGarbageCollectionIndex() == SyncIndex && *SyncAddrHandler == Ptr)
{
++SyncAddrHandler->Count;
}
else
{
SyncAddrHandler = LGC->RegisterObjectRef(Ptr);
SyncIndex = LGC->GetGarbageCollectionIndex();
}
}
/*
@param Ptr - Owned object which is exactly new for GC.
*/
inline void SyncRegisterExactlyNew(const void* Ptr)
{
if (Ptr == nullptr)
{
SyncAddrHandler = nullptr;
return;
}
GGarbageCollector* LGC = GGarbageCollector::Get();
SyncAddrHandler = LGC->RegisterExactlyNewObjectRef(Ptr);
SyncIndex = LGC->GetGarbageCollectionIndex();
}
/*
@param Ptr - owned object to synchronized unregister in GC.
*/
inline void SyncUnregister(const void* Ptr)
{
if (Ptr == nullptr)
{
SyncAddrHandler = nullptr;
return;
}
GGarbageCollector* LGC = GGarbageCollector::Get();
if (SyncAddrHandler != nullptr && LGC->GetGarbageCollectionIndex() == SyncIndex && *SyncAddrHandler == Ptr)
{
LGC->UnregisterObjectRefByHandler(SyncAddrHandler);
}
else
{
//if Count == 0 SyncAddrHandler will be nullptr
SyncAddrHandler = LGC->UnregisterObjectRef(Ptr);
}
}
private:
mutable GarbageCollector_Private::FAddrHandler* SyncAddrHandler = nullptr;
mutable int SyncIndex = -1;
};Еще одна важная оптимизационная деталь, которая присуща "умным" указателям и мы хотим ее тоже иметь. А именно кеширование данных. В "умных" указателях инкремент количества ссылок происходит напрямую, так почему бы нам тоже так не делать. Ведь обращение к указателю происходит чаще очистки. Давайте один раз синхронизируемся со сборщиком о валидности, а далее только после очистки, да и то, только при обращении к указателю.
Вот во что превратились наши основные объекты:
GGarbageCollector
Hidden text
/*
Main garbage manager.
*/
class GGarbageCollector
{
friend struct FGCPointerBase;
public:
static inline GGarbageCollector* Get()
{
static GGarbageCollector GC;
return &GC;
}
private:
inline GGarbageCollector() {}
public:
/*
Force collect garbage.
*/
inline void ForceGC()
{
PtrMap.ClearInvalidPtrs();
}
/*
@return total objects count who are under surveillance.
*/
inline unsigned int GetTotalObjectsCount() const noexcept
{
return PtrMap.GetTotalObjectsCount();
}
/*
@return the number of objects destroyed at the last iteration of garbage collection.
*/
inline unsigned int GetLastGarbagedObjectsCount() const noexcept
{
return PtrMap.GetLastGarbagedObjectsCount();
}
/*
@return index of the garbage collection iteration.
*/
inline unsigned int GetGarbageCollectionIndex() const noexcept
{
return PtrMap.GetGarbageCollectionIndex();
}
/*
Check that object address is in GarbageCollector.
*/
inline bool IsGCObjectValid(const void* Object) const noexcept
{
return PtrMap.GetPtrHandler(Object) != nullptr;
}
/*
Check that object address is in GarbageCollector and hasn't got any refs.
*/
inline bool IsGCObjectPendingToKill(const void* Object) const noexcept
{
const GarbageCollector_Private::FAddrHandler* LAddrHandler = PtrMap.GetPtrHandler(Object);
return LAddrHandler != nullptr && LAddrHandler->IsPendingToKill();
}
//for FGCPointerBase
protected:
inline GarbageCollector_Private::FAddrHandler* RegisterObjectRef(const void* Object)
{
return PtrMap.AddPtr(Object);
}
inline GarbageCollector_Private::FAddrHandler* RegisterExactlyNewObjectRef(const void* Object)
{
return PtrMap.AddNewPtr(Object);
}
inline GarbageCollector_Private::FAddrHandler* UnregisterObjectRef(const void* Object)
{
return PtrMap.RemovePtr(Object);
}
inline void UnregisterObjectRefByHandler(GarbageCollector_Private::FAddrHandler* PtrHandler)
{
PtrMap.RemovePtrByHandler(PtrHandler);
}
inline GarbageCollector_Private::FAddrHandler* GetPtrHandler(const void* Object)
{
return PtrMap.GetPtrHandler(Object);
}
private:
/*
Storage of object ptrs.
*/
GarbageCollector_Private::FAnyPtrMap PtrMap;
};TGCPointer
Hidden text
template<typename T>
struct TGCPointer : public FGCPointerBase
{
public:
inline TGCPointer() {}
inline TGCPointer(T* InObject) : Object(InObject)
{
SyncRegister(InObject);
}
inline TGCPointer(T* InObject, bool IsNew) : Object(InObject)
{
if (IsNew)
{
SyncRegisterExactlyNew(InObject);
}
else
{
SyncRegister(InObject);
}
}
inline TGCPointer(const TGCPointer& OtherGCPointer) : FGCPointerBase(OtherGCPointer),
Object(OtherGCPointer.Object)
{
SyncRegister(Object);
}
inline TGCPointer(TGCPointer&& OtherGCPointer) noexcept : FGCPointerBase(OtherGCPointer),
Object(OtherGCPointer.Object)
{
OtherGCPointer.Object = nullptr;
}
~TGCPointer()
{
SyncUnregister(Object);
}
public:
operator bool()
{
return IsValid();
}
operator T*()
{
return Object;
}
inline T& operator*() const
{
return *Object;
}
inline T* operator->() const
{
return Object;
}
inline TGCPointer& operator=(const TGCPointer& InGCPointer)
{
if (InGCPointer.Object == Object) return *this;
SyncUnregister(Object);
Object = InGCPointer.Object;
SyncInitFrom(InGCPointer);
SyncRegister(Object);
return *this;
}
inline TGCPointer& operator=(TGCPointer&& InGCPointer)
{
SyncUnregister(Object);
SyncInitFrom(InGCPointer);
Object = InGCPointer.Object;
InGCPointer.Object = nullptr;
return *this;
}
inline TGCPointer& operator=(T* Ptr)
{
if (Ptr == Object) return *this;
SyncUnregister(Object);
Object = Ptr;
SyncRegister(Object);
return *this;
}
// операторы сравнения опустил
public:
inline bool IsValid() const noexcept
{
//if Object not in GC or Object == nullptr then we will be not sync
return Sync(Object);
}
inline T* Get() const noexcept
{
return Object;
}
inline T* GetChecked() const noexcept
{
if (!IsValid())
{
Object = nullptr;
}
return Object;
}
inline void Reset()
{
SyncUnregister(Object);
Object = nullptr;
}
private:
/*
Owned object.
*/
T* Object = nullptr;
};Как видно, создание нового объекта не вызывает перебор имеющихся, ибо мы точно знаем, что система выдаст новый адрес, не занятый.
Кроме того, благодаря синхронизации, работа с нашим указателем сравнима с работой обычного указателя, даже проверка на валидность не вызывает ни какой нагрузки. А это очень важно, так как это чуть ли не основная фича.
4) Последние оптимизационные штрихи
До этого мы не рассматривали сам процесс освобождения памяти. А это 50% успеха сборщика мусора. Пора это исправлять.
Очистка происходит в FAnyPtrMap. Лобовым решением было бы пройтись по всем ячейкам массива, проитерироваться по списку и удалить все PendingToKill объекты. Но это долго. По сути так мы теряем в скорости из-за большого размера статического массива, который обеспечивает нам скорость на добавление/чтение элементов.
Не беда! При удалении объекта (вызов метода RemovePtr или RemovePtrByHandler) будем записывать номер ячейки массива в отдельный "массив". При сборке мусора будем итерироваться уже по нему. Так мы точно не будем совершать холостых итераций.
Для определения того факта, что ячейка массива помечена как кандидат на итерирование очистки, заведем маску ячеек. По-простому - еще массив булов размером в количество ячеек нашего основного массива.
Как мы знаем, бул занимает 1 байт, т.е 7 бит лежат впустую. Исправим и это(мы и так кучу памяти пожрали).
TGarbageBoolMask
Hidden text
/*
Large bool mask for memory optimization in GC.
Each bit is 0/1 mask.
@param T - Container POD-type of the mask elements.
@param BitsPackSize - mask size.
*/
template<typename T, int BitsPackSize>
struct TGarbageBoolMask
{
public:
inline TGarbageBoolMask()
{
BoolMask = new T[BitsPackSize / MaskSize];
Clear();
}
~TGarbageBoolMask()
{
if (BoolMask != nullptr) delete[] BoolMask;
}
public:
/*
Set mask bit to 1.
@return bit set success.
*/
inline bool SetMaskBit(int Index) noexcept
{
const int LMaskIndex = Index / MaskSize;
// 1 << (Index % 8) - for char(1 byte)
const T LBitIndexMask = (T)1 << (Index & PackTypeRemainMask);
//BoolMask[Index / 8] & (1 << (Index % 8)) - for char(1 byte)
const bool IsSet = BoolMask[LMaskIndex] & LBitIndexMask;
if (IsSet) return false;
//BoolMask[Index / 8] |= (1 << (Index % 8)) - for char(1 byte)
BoolMask[LMaskIndex] |= LBitIndexMask;
return true;
}
/*
Set mask bit to 0.
*/
inline void ClearMaskBit(int Index) noexcept
{
//BoolMask[Index / 8] &= ~(1 << (Index % 8)) - for char(1 byte)
BoolMask[Index / MaskSize] &= ~((T)1 << (Index & PackTypeRemainMask));
}
/*
Set mask to 0.
*/
inline void Clear()
{
for (T* LMaskElem = BoolMask + BitsPackSize / MaskSize - 1; LMaskElem >= BoolMask; --LMaskElem)
{
*LMaskElem = 0;
}
}
private:
const static int MaskSize = sizeof(T) * 8;
const static int PackTypeRemainMask = sizeof(T) * 8 - 1;
T* BoolMask = nullptr;
};Вот так запакуем наши булы.
FGarbageListsToClearArray
Hidden text
/*
Helper struct to manage of garbage lists to be cleared.
*/
struct FGarbageListsToClearArray
{
public:
FGarbageListsToClearArray() = delete;
inline FGarbageListsToClearArray(int ListsCount) :
MaxListsCount(ListsCount)
{
IndexesToClean = new int[ListsCount];
}
~FGarbageListsToClearArray()
{
if (IndexesToClean != nullptr) delete[] IndexesToClean;
}
public:
inline int& operator[](int Index)
{
//check Index < CountOfListsToClean
return IndexesToClean[Index];
}
public:
/*
Add new list index to array.
*/
inline void Push(int Index)
{
//check CountOfListsToClean < MaxListsCount
IndexesToClean[CountOfListsToClean] = Index;
++CountOfListsToClean;
}
/*
@return count of lists to clear.
*/
inline int Num() const noexcept
{
return CountOfListsToClean;
}
/*
Remove all lists from array.
*/
inline void Clear() noexcept
{
CountOfListsToClean = 0;
}
/*
Check if any list has been pushed.
*/
inline bool IsEmpty() const noexcept
{
return CountOfListsToClean == 0;
}
private:
/*
Array of list indexes.
*/
int* IndexesToClean = nullptr;
/*
Count of pushed lists.
*/
int CountOfListsToClean = 0;
/*
Max count of lists indexes to contain.
*/
int MaxListsCount = 0;
};Тут реализован стек на базе статического массива. Этого нам достаточно. Максимальная скорость чтения/записи.
Вот во что превратился FAnyPtrMap
Hidden text
/*
Helper struct for manage AddrHandlers.
@see FAddrHandler.
*/
struct FAnyPtrMap
{
public:
inline FAnyPtrMap() :
ListsIndexesToClean(BitsPackSize)
{
ItemMap = new std::forward_list<FAddrHandler>[BitsPackSize];
}
~FAnyPtrMap()
{
if (ItemMap != nullptr) delete[] ItemMap;
}
public:
FAddrHandler* AddPtr(const void* Ptr)
{
//if (Ptr == nullptr) return; //check
const size_t LAddr = (const size_t)Ptr;
std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
auto LItemsEnd = LItems.end();
auto LAddrHandler = std::find(LItems.begin(), LItemsEnd, LAddr);
if (LAddrHandler != LItemsEnd)
{
++LAddrHandler->Count;
return &LAddrHandler._Ptr->_Myval;
}
else
{
++TotalObjectsCount;
LItems.push_front(FAddrHandler(LAddr, 1));
return &LItems.front();
}
}
FAddrHandler* AddNewPtr(const void* Ptr)
{
//if (Ptr == nullptr) return; //check
const size_t LAddr = (const size_t)Ptr;
std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
++TotalObjectsCount;
LItems.push_front(FAddrHandler(LAddr, 1));
return &LItems.front();
}
FAddrHandler* RemovePtr(const void* Ptr)
{
//if (Ptr == nullptr) return; //check
const size_t LAddr = (const size_t)Ptr;
const unsigned int LocalAddr = GetLocalAddr(LAddr);
std::forward_list<FAddrHandler>& LItems = ItemMap[LocalAddr];
auto LItemsEnd = LItems.end();
auto LAddrHandler = std::find(LItems.begin(), LItemsEnd, LAddr);
if (LAddrHandler == LItemsEnd || LAddrHandler->Count == 0) return nullptr;
if (--LAddrHandler->Count == 0)
{
if (ListsIndexesToCleanMask.SetMaskBit(LocalAddr))
{
ListsIndexesToClean.Push(LocalAddr);
}
}
return &LAddrHandler._Ptr->_Myval;
}
inline void RemovePtrByHandler(FAddrHandler* PtrHandler)
{
if (PtrHandler == nullptr || PtrHandler->Count == 0 || !PtrHandler->IsValid()) return;
if (--PtrHandler->Count == 0)
{
const unsigned int LocalAddr = GetLocalAddr(PtrHandler->Addr);
if (ListsIndexesToCleanMask.SetMaskBit(LocalAddr))
{
ListsIndexesToClean.Push(LocalAddr);
}
}
}
void ClearInvalidPtrs()
{
LastGarbagedObjectsCount = 0;
if (ListsIndexesToClean.IsEmpty()) return;
++GarbageCollectionIndex;
for (int i = 0; i < ListsIndexesToClean.Num(); ++i)
{
ItemMap[ListsIndexesToClean[i]].remove_if([this](FAddrHandler& LAddrHandler)
{
if (!LAddrHandler.IsPendingToKill()) return false;
delete (void*)LAddrHandler.Addr;
++LastGarbagedObjectsCount;
return true;
});
ListsIndexesToCleanMask.ClearMaskBit(ListsIndexesToClean[i]);
}
TotalObjectsCount -= LastGarbagedObjectsCount;
ListsIndexesToClean.Clear();
}
FAddrHandler* GetPtrHandler(const void* Ptr) const noexcept
{
//if(Ptr == nullptr); //check
const size_t LAddr = (const size_t)Ptr;
const std::forward_list<FAddrHandler>& LItems = ItemMap[GetLocalAddr(LAddr)];
auto LItemsEnd = LItems.end();
auto LAddrHandler = std::find(LItems.begin(), LItemsEnd, LAddr);
if (LAddrHandler == LItemsEnd) return nullptr;
return &LAddrHandler._Ptr->_Myval;
}
inline unsigned int GetTotalObjectsCount() const noexcept
{
return TotalObjectsCount;
}
inline unsigned int GetLastGarbagedObjectsCount() const noexcept
{
return LastGarbagedObjectsCount;
}
inline int GetGarbageCollectionIndex() const noexcept
{
return GarbageCollectionIndex;
}
private:
inline unsigned int GetLocalAddr(size_t Addr) const noexcept
{
return Addr & BitsPackMask; // Addr % BitsPackSize
}
public:
const static unsigned int BitsPackSize = 1048576; //1 MB ~69MB in ram
const static int BitsPackMask = 0xfffff; // 20 bits 2^20 = 1048576
//const static unsigned int BitsPackSize = 65536; //64 KB ~4MB in ram
//const static int BitsPackMask = 0xffff; // 16 bits 2^16 = 65536
private:
std::forward_list<FAddrHandler>* ItemMap = nullptr;
FGarbageListsToClearArray ListsIndexesToClean;
TGarbageBoolMask<size_t, BitsPackSize> ListsIndexesToCleanMask;
/*
Total objects count who are under surveillance.
*/
unsigned int TotalObjectsCount = 0;
/*
The number of objects destroyed at the last iteration of ClearInvalidPtrs.
*/
unsigned int LastGarbagedObjectsCount = 0;
/*
Index of ClearInvalidPtrs iteration.
*/
int GarbageCollectionIndex = 0;
};Замечу, что тип запаковки булов в TGarbageBoolMask выбран size_t. Это самый большой тип в системе, благодаря чему физическое количество элементов массива под кусочки маски будет меньше. А это более быстрое создание/удаление статического массива. Мелочь, а приятно.
Ну и вишенкой на торте станет многопоточная сборка мусора. Сыграем на том, что все необходимые нам массивы статические, а сам размер массива большой (создание тредов окупает их производительность).
Метод ClearInvalidPtrs
Hidden text
void ClearInvalidPtrs()
{
LastGarbagedObjectsCount = 0;
if (ListsIndexesToClean.IsEmpty()) return;
++GarbageCollectionIndex;
if (GarbageCleaningThreadsCount > 1 && ListsIndexesToClean.Num() > GarbageCleaningThreadsCount)
{
std::thread* LThreads = new std::thread[GarbageCleaningThreadsCount];
int* LThreadGarabagedObjectsCount = new int[GarbageCleaningThreadsCount];
const int LStep = ListsIndexesToClean.Num() / GarbageCleaningThreadsCount + 1;
int L = 0;
int R = LStep;
int LThreadIndex = 0;
for (LThreadIndex; LThreadIndex < GarbageCleaningThreadsCount; ++LThreadIndex)
{
if (R > ListsIndexesToClean.Num()) R = ListsIndexesToClean.Num();
if (L == R)
{
break;
}
LThreads[LThreadIndex] = std::thread([this, L, R, LThreadIndex, LThreadGarabagedObjectsCount]()
{
int LGarbagedObjectsCount = 0;
for (int i = L; i < R; ++i)
{
ItemMap[ListsIndexesToClean[i]].remove_if([this, &LGarbagedObjectsCount](FAddrHandler& LAddrHandler)
{
if (!LAddrHandler.IsPendingToKill()) return false;
delete (void*)LAddrHandler.Addr;
++LGarbagedObjectsCount;
return true;
});
}
LThreadGarabagedObjectsCount[LThreadIndex] = LGarbagedObjectsCount;
});
L = R;
R += LStep;
}
for (int i = 0; i < LThreadIndex; ++i)
{
LThreads[i].join();
LastGarbagedObjectsCount += LThreadGarabagedObjectsCount[i];
}
ListsIndexesToCleanMask.Clear();
delete[] LThreads;
delete[] LThreadGarabagedObjectsCount;
}
else
{
for (int i = 0; i < ListsIndexesToClean.Num(); ++i)
{
ItemMap[ListsIndexesToClean[i]].remove_if([this](FAddrHandler& LAddrHandler)
{
if (!LAddrHandler.IsPendingToKill()) return false;
delete (void*)LAddrHandler.Addr;
++LastGarbagedObjectsCount;
return true;
});
ListsIndexesToCleanMask.ClearMaskBit(ListsIndexesToClean[i]);
}
}
TotalObjectsCount -= LastGarbagedObjectsCount;
ListsIndexesToClean.Clear();
}Все потоки не конкурируют и обрабатывают примерно одинаковый объем данных.
Тесты
Замеры производились на одной машине, поэтому конкретные числа времени работы программ очень частные. Лучше смотреть на отношения производительности.
Потребление памяти зависит тоже от архитектуры.
Платформа: x86-64
Процессор: Intel Core i5-11400F
Операционная система: Windows 10
Среда разработки и замеров: Visual studio 2022 community
В тестах используется структура типа:
struct TestStruct
{
int A = 5;
int B = 3;
};Выбран нестандартный тип.
Количество элементов в тесте = 1 миллион.
1) Потребление памяти
Сборщик мусора предусматривает 2 режима работы:
С меньшими затратами памяти, но "медленнее".
С максимально разумными затратами памяти.
потребление памяти = базовый размер сборщика + количество элементов участвующих в сборке * размер контейнера мета информации + количество используемых указателей * размер указателя
Размер нашего указателя(TGCPointer) = 24 байт
Размер std::shared_ptr = 16 байт
Размер обычного указателя = 8 байт
Размер мета информации(FAddrHandler) = 16 байт
Размер мета информации(std::shared_ptr) = 8 байт
Размер мета информации(обычный указатель) = 0 байт
Базовый размер сборщика при размере статического массива 65536 ~= 4MB
Базовый размер сборщика при размере статического массива 1048576 ~= 69MB
2) Производительность
Тест производительности заключается в создании и удалении 1 миллиона объектов максимально быстрым способом.
Тест обычного указателя:
TestStruct** Arr = new TestStruct*[IterationsCount];
for (int i = 0; i < IterationsCount; ++i)
{
Arr[i] = new TestStruct();
}
for (int i = 0; i < IterationsCount; ++i)
{
delete Arr[i];
}
delete[] Arr;Тест std:shared_ptr:
for (int i = 0; i < IterationsCount; ++i)
{
auto A = std::shared_ptr<TestStruct>((new TestStruct()));
}Тест сборщика мусора:
for (int i = 0; i < IterationsCount; ++i)
{
TGCPointer<TestStruct> A(new TestStruct(), true);
}
GGarbageCollector::Get()->ForceGC();В многопоточном режиме сборки мусора используется 8 потоков.
Все числа указаны в микросекундах(ну и округлены в силу погрешности).
Development build | Release build | |||||
Создание | Удаление | Сумма | Создание | Удаление | Сумма | |
Original | 82000 | 72000 | 155000 | 27000 | 17000 | 45000 |
std::shared_ptr | ? | ? | 380000 | ? | ? | 73000 |
single thread 64KB | 390000 | 280000 | 670000 | 60000 | 80000 | 140000 |
multi thread 64KB | 390000 | 870000 | 1,3M | 60000 | 30000 | 90000 |
single thread 1MB | 550000 | 260000 | 800000 | 67000 | 46000 | 115000 |
multi thread 1MB | 550000 | 780000 | 1,3M | 67000 | 18000 | 85000 |
Отношение производительности(для Release build)
Original | std::shared_ptr | |
single thread 64KB | 3,11 | 1,91 |
multi thread 64KB | 2 | 1,23 |
single thread 1MB | 2,56 | 1,57 |
multi thread 1MB | 1,89 | 1,16 |
std::shared_ptr | 1,62 | 1 |
Выводы
Скорость сборки мусора в многопоточной версии максимально близка к стандартной очистке памяти. Это победа!
Общая производительность в критической ситуации в 2 раза медленнее стандартных указателей.
Как видно, объем затраченной памяти сильно влияет на однопоточную версию.
В играх обычно объекты создаются (большая часть) в начале и живут долгое время, поэтому, учитывая, что очистку не придется производить слишком часто, то работа с нашими указателями практически полностью превращается в работу как с обычными указателями. Но плюшки в виде точного ответа на вопрос о валидности объекта и спокойствие за то, что память с большей вероятностью не утечет, позволяет закрыть глаза на повышенный расход памяти.
Я считаю, что получаемый выхлоп в виде автоматической очистки памяти + большая лояльность к фрагментации кучи + дружелюбный интерфейс - оправдывает себя.
Или нет?
Что касается использования этого сборщика. Его место в геймплейной логике, где важна читаемость, скорость разработки и меньше возни с технической частью. Чтобы было проще погрузиться в творческий процесс. Очевидно, в коровых системах подойдут либо "умные" указатели, либо стандартные указатели, без них ни куда.
И еще раз отмечу. Сборщик мусора нельзя отождествлять с "умными" указателями. Хоть они и решают одну задачу, но "умные" указатели очищают память сиюминутно, не задумываясь "об окружающих", а сборщик молотит в подходящий момент (например, при загрузке уровня).
Что можно улучшить?
Думаю, что было бы хорошо не просто удалять объекты, а перемещать невалидные объекты в один линейный кусок памяти и очищать его, а используемые объекты держать в другом. Так мы поможем системе в выделении новой памяти.
P.S. Хоть и можно использовать обычные указатели как слабые ссылки, но лучше создать отдельный указатель, который будет заниматься кешированием по аналогии с представленным в статье умным указателем.
