Немного теории
Не буду долго рассусоливать о том, что такое сборщик мусора и для чего он нужен (на эту тему уже есть достаточно статей). Но хочу отметить несколько важных деталей.
Сборщик мусора - один из способов решения проблемы контроля памяти.
Основное отличие от "умных" указателей с++ заключается в том, что подсчет ссылок на объекты и дальнейшее решение о высвобождении памяти происходит не в самом указателе, а в неком одном глобальном объекте. Очистка происходит не одного объекта, а всех, или порции невалидных.
Сборщик мусора - не аллокатор. Хоть проблема выделения/освобождения памяти затрагивает вопрос о фрагментации/дефрагментации кучи, но сборщик мусора не призван ее решать. Он может работать в связке со своим аллокатором, но основное его преимущество заключается в том, что память очищается не хаотично и не "лавинообразно".
Что хотим получить?
При написании игрового движка появилась потребность в автоматическом контроле памяти (удивительно, не правда ли?). Поэтому было решено написать свой сборщик мусора и заодно попытаться выжать из него максимум производительности.
Основные требования:
Скорость по выделению и освобождению памяти должна быть сравнима с обычными 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. Хоть и можно использовать обычные указатели как слабые ссылки, но лучше создать отдельный указатель, который будет заниматься кешированием по аналогии с представленным в статье умным указателем.
Комментарии (73)
alex_ter
25.07.2022 01:19Наверное такой подход имеет место быть в определенных ситуациях. Но, лично для меня, сильнейшая сторона C++ - это возможность размещать объекты в стеке, это мало где есть удобно и "из коробки". Ну а сборщик мусора (подобный вашему) можно реализовать практически на любом ЯП, тут не обязателен C++.
DistortNeo
25.07.2022 01:53+4Одно из преимуществ языков со сборкой мусора — это сверхбыстрое выделение памяти (говорят, что в C# память выделяется быстрее, чем в C++) плюс фоновое освобождение (не расходуется время на
deleteв основном потоке). То есть сборка мусора при правильном применении повышает производительность.Быстрое выделение памяти же достигается за счёт простого аллокатора: память выделяется последовательно, в некоторых реализациях вообще у каждого потока куча своя — минус накладные расходы на межпоточную синхронизацию. Автор же использует стандартный
new.
ptr128
26.07.2022 00:24+4Скорость выделения памяти от сборки мусора не зависит. Использовать несколько пулов для оптимизации скорости выделения памяти можно и без сборщика мусора.
А вот случаи, когда система уходила в задумчивость из-за того, что программист понадеялся на сборщик мусора, а тот просто не успевал освобождать память, я встречал неоднократно. Например, в системе сбора данных при пиковых нагрузках.
Я ни в коем случае не утверждаю, что сборщик мусора есть плохо. Я утверждаю, что есть случаи, когда производительность системы выше без него и эффективней освобождение памяти вручную.
mbait
25.07.2022 04:08+2Тесты производительности - огонь! =) Советую почитать про выделение пулов под объекты одного класса (не класса в мысле "class", а в смысле схожего цикла жизни), переиспользование памяти и алгоритмы без удаления памяти (выделил один раз и до конца жизни программы).
IntActment
25.07.2022 04:21+7А что насчёт циклических ссылок и островов памяти? Признаюсь, код смотрел по диагонали, но в тексте упоминания решения данной проблемы не нашел.
paluke
25.07.2022 05:31+1А в С++ в общем случае проблему циклических ссылок никак не решить. Если у вас два произвольных объекта ссылаются друг на друга, вы не можете удалить сначала один из них, а потом другой. Потому что нет гарантии, что второй не обращается в деструкторе к первому.
IntActment
25.07.2022 06:16+1Ну, даже если отложить попытки решить данную проблему, нужно хотя бы иметь возможность отслеживать существование островов хотя бы в debug-сборке, ведь случайно создать острова очень просто, а память не бесконечная. Иначе выйдет так, что сборщик добавит новый класс проблем, куда посерьёзнее чем те, которые он призван решить.
Upd: Еще есть проблема с многопоточностью - если объект передаётся в другой поток, то освобождение может произойти в неподконтрольном потоке, что еще сильнее все усложняет. Деструкторы и неконтролируемое время уничтожения - само по себе создаёт проблему. Как способ решения - все вызовы деструкторов умных указателей должны происходить в определённый этап цикла потока. Да, очерёдность вызовов деструкторов не гарантируется, но зато гарантируется, что это не произойдёт случайно в неподходящий момент. В своём движке у меня был самописный таск-менеджер как класс-обёртка над потоком, и он работал в паре с объектными пулами. Чтобы избежать синхронизации, пулы были thread_local. И постоянно возникал кейс, когда объекты передавались в другой поток. После использования в другом потоке объекты нужно было уничтожать, но утилизировать в пул чужого потока - не вариант, иначе пул первого потока будет аллоцировать всё новые и новые, а поток-получатель только собирать "перебежчиков". То есть, в качестве механизма "департации" в родной поток объекты помещались в специальный список, отдельный список на каждый поток. И тут на помощь приходит тот самый кастомный таск-менеджер: в конце цикла он проверяет все списки "депортируемых" и пачками за один заход возвращает все объекты в их родной поток через специальный таск. Родной поток же в свою очередь в начале цикла подбирал всех "депортированных" и вызывал деструкторы. Звучит сумбурно, прошу простить. Может моя идея реализации кому-то чем-то поможет.
Deosis
25.07.2022 06:53Возможно, будет проще создавать копию объекта, пришедшего из другого потока. Таким образом каждый поток владеет своими объектами.
Стоит сравнить накладные расходы на копирование и расходы на ловлю перебежчиков.
IntActment
25.07.2022 07:25Учитывая, что перебежчики сами добавляют себя в список на депортацию, предложенное решение происходит за O(n) и выглядит универсальным. При копировании же могут возникать частные случаи - копирование может быть дорогим (не POD?), проблема передачи владения объектов в полях скопированного объекта, копирование объекта запрещено или чёрт знает что ещё. В любом случае перемещение указателя внутри умного указателя будет быстрее. Если же объект легковесный, то и пул для него заводить смысла нет.
Kelbon
25.07.2022 08:24+6shared_ptr / weak_ptr.
Как то очень глупо говорить, что в С++ не решить подобное, если все гц в других языках написаны на С++
paluke
25.07.2022 15:56weak_prt используют, чтобы избежать циклических ссылок. Организуется иерархия владения, и соответственно определенный порядок удаления.
Для gc надо либо как-то ограничивать классы, на которые может ссылаться gc-pointer (например, требовать только тривиальный деструктор), либо делать какие-то хинты, кого удалять первым — фактически аналог weak_prt (а зачем тогда gc?)
DistortNeo
25.07.2022 18:05shared_ptr / weak_ptr.
К слову, оверхэд при использовании shared_ptr и weak_ptr довольно большой из-за использования атомарных операций. Поэтому код на GC-языке с активным использованием указателей будет работать быстрее.
0xd34df00d
25.07.2022 18:24+3Потому что умные указатели надо передавать по значению только тогда, когда вам нужно на самом деле разделить владение, а это довольно редкая ситуация. В прочих случаях нормально использовать сырые указатели или ссылки.
0xd34df00d
25.07.2022 18:23+2Не глупо, потому что в случае описания других языках C++ выступает метаязыком, а при описании себя — просто языком. Это ничем не отличается от невозможности доказать консистентность какой-нибудь логики изнутри этой логики, но возможности сформулировать аксиомы другой логики и доказать их консистетность.
Или, говоря конструктивно, стандартным C++ абсолютно все
newв абсолютно всех TU вам перехватить не получится.Kelbon
25.07.2022 18:28перегрузка глобального new
не было задачи перехватить всё, только то что нуждается в таком менеджменте
0xd34df00d
25.07.2022 18:31перегрузка глобального new
Как вы её сделаете видимой во всех TU?
Если через замену соответствующих символов — начнётся веселье в том случае, если две разных библиотеки/модуля/етц используют разные варианты глобального
new.не было задачи перехватить всё, только то что нуждается в таком менеджменте
Ну это уже вопрос того, как определять «подобное».
Kelbon
25.07.2022 18:33Как вы её сделаете видимой во всех TU?
сделаю её в мейне выше всех инклудов. До модулей в С++20 это будет работать.
0xd34df00d
25.07.2022 18:34+1А я в своей библиотеке тоже свой GC наваял подобным образом, а вы хотите с ней слинковаться. Ваши действия?
Kelbon
25.07.2022 18:54-1запретить перегрузку new, забыть про гц в С++ как ужасную идею
IntActment
25.07.2022 19:09Я считаю, делать гц "универсальным аллокатором" для всех new смысла нет (тогда лучше выбрать другой язык), но имеет смысл создавать определенные высокоуровневые категории объектов через гц (например, игровые сущности). При этом созданные через гц-аллокатор объекты не должны торчать наружу указателями вообще - а иметь свой умный указатель, позволяющий отгородить внешнюю логику от доступа по висячей ссылке. В c++/cli похожая схема, где можно создавать объекты как через new, так и через gcnew.
0xd34df00d
25.07.2022 19:47+4Как то очень глупо говорить, что в С++ не решить подобное, если все гц в других языках написаны на С+
…проходит 5 минут…
запретить перегрузку new, забыть про гц в С++ как ужасную идею
Люблю такие решения.
Kelbon
25.07.2022 19:52если бы я делал ГЦ это был бы синглтон с методом
static T& create<T>(Args&&...); или нечто подобноеОператор new я бы и правда запретил перегружать.
playermet
25.07.2022 10:53+1Потому что нет гарантии, что второй не обращается в деструкторе к первому.
Так и пусть обращается.
1) Находим граф связанных указателей, подлежащий удалению.
2) Вызываем дестукторы у всех указателей этого графа.
3) Освобождаем память всех указателей этого графа.
DistortNeo
25.07.2022 11:31+4Так это будет лютый UB: сначала вызываем деструктор первого объекта, затем из деструктора второго к нему обращаемся. Сам первый объект в памяти ещё висит, но его поля могут быть в совсем невалидном состоянии. Собственно, поэтому в языках с GC логика работы деструкторов другая, и называются они "финализаторами".
playermet
25.07.2022 13:03+1Да, но эту же проблему можно и без GC устроить. Берем два объекта, в деструкторе первого трогаем второй, в деструкторе второго трогаем первый. Какой способ управления памяти тут не примени, UB никуда не пропадет, тут скорее вопрос корректной архитуктуры и дисциплины. Т.е. нужно запретить писать код в деструкторах который потенциально вызывает проблему.
IntActment
25.07.2022 13:24В своем проекте я решал эту проблему кастомным полуумным указателем: уничтожение вызывается только вручную вызовом метода destroy на самом указателе, но все копии этого указателя впоследствии разыменовываются в nullptr (избегаем висячих ссылок). Ну и, собственно, как и вызов delete на nullptr безопасен, так и destroy внутри другого destroy не будет делать ничего. А вообще, желательно избегать использование деструктора и по возможности создавать объекты через фабричный метод и задавать там функцию удаления. Таким образом решается проблема возможного вызова виртуальных методов в конструкторе и деструкторе.
DistortNeo
25.07.2022 13:27Т.е. нужно запретить писать код в деструкторах который потенциально вызывает проблему.
То есть выкинуть RAII и перейти к явному вызову методов типа Dispose.
playermet
25.07.2022 13:53+1Не обязательно. Однако не стоит ожидать что уже существующие классы будут работать из коробки без переписывания/оберток в GC-way.
paluke
25.07.2022 16:06weak_ptr решает проблему. Но тут программист должен решить, в каком порядке удаляются объекты. А gc как о правильном порядке удаления узнает, если программист об иерархии владения думать не хочет, а хочет чтобы оно само как-то решилось?
code_panik
25.07.2022 13:14Выше не упоминаются конкретные детали реализации, поэтому можно подобрать такие, чтобы обойтись без ub. Речь может идти о placement new с ручным вызовом деструкторов. Для простоты можем говорить о методах create/destroy (возможно, pimpl класса). Граф ссылок можно обойти поиском в глубину, вызывая destroy на каждом шаге назад.
Jian
25.07.2022 06:33Насколько C++ с коллектором, будет отличаться от C# такой коллектор уже имеющим?
GrosSlava Автор
25.07.2022 10:43+1Скорее это фича именно для геймплейной логики в с++, где хочется не думать о жизни объекта.
Думаю, что в с++ можно получить "2 в 1". Полный контроль на низком уровне и использование GC на высоком. Без него очень противно создавать объект не привязанный к миру(аналогия на UObject из UE).
Kelbon
25.07.2022 16:16корутина ответ на такой запрос(создание объекта не привязанного ни к чему кроме себя)
skygtr99113
25.07.2022 07:27+1По личному опыту: когда учился в ВУЗе, прогал на c++, на работе c# (уже больше 8 лет прогаю на c#). И чем больше читаю книг по управлению памятью в c# и о том, как написать производительное приложение, тем больше понимаю, что все эти навороты с автоуправлением памятью усложняют фреймворк до невозможности. На с++ человеку достаточно помнить о том когда нужно очистить память. На шарпе толстенная книга о том, как работает фреймворк с памятью. Любое "авто" приводит к ограничениям, которые нужно помнить, а когда забываешь о них, то теряешь в скорости или стреляешь в ногу. На мой взгляд c++ не тот язык, где это нужно.
playermet
25.07.2022 10:59+4На с++ человеку достаточно помнить о том когда нужно очистить память
В современном C++ это уже не совсем так, скорее нужно соблюдать иерархию владения, а все остальное делает RAII и стандартная библиотека.
DistortNeo
25.07.2022 11:35Вот с иерархией владения обычно сложности и вылезают. Во многих сценариях гораздо проще положиться на автоматическое управление памятью.
mbait
26.07.2022 02:16+1Работа с паматью не бывает простой. Начинаешь писать на Си, надоедают сегфолты - переходишь на С++, там те же сегфолты + стектрейс размером с Войну и Мир. Переходишь на языки с управляемой памятью, там всё круто, но медленно. Начинаешь настраивать сборщик мусора, понимаешь, что это всё капли в море. Начинаешь пытаться обмануть сборщик: out-of-heap, отказ от объектов в пользу примитивных типов, денормализация структур данных. Начинаешь понимать, что пишешь на Java в стиле С++, возвращаешься обратно на С++ с идеей добавить сборку мусора. Получаешь всё те же сегфолты + тормоза от сборки мусора. Плюёшь на всё и решаешь, что отныне не будет циклических зависимостей, используешь shared_ptr/weak_ptr. Понимаешь, что в многопоточном приложении блокировки съедают производительность. Уходишь в Тибет, просветляешься, там постигаешь пуллинг, переиспользование памяти, алгоритмы без использования кучи. Возвращяеся и одухотворённый пишешь программы, которые летают и не падают. Постепенно понимаешь, что даже hello-world в таком стиле это боль и унижение, ведь рядом коллеги пишут простой и понятный код на Java/C#. Завязываешь с программированием и уходишь в строители.
Kelbon
26.07.2022 08:41-2какие ещё блокировки в shared ptr???
Какие ещё алгоритмы без использования кучи? Очевидно что дорогостоящую операцию(выделение памяти), нужно использовать как можно реже, это называется просто нормальный алгоритм, а не алгоритм "без кучи"
Если писать код на современных плюсах, то никаких сегфолтов не будет, и если что все эти оптимизации по переиспользованию памяти и пулам находятся внутри malloc/operator new
DistortNeo
26.07.2022 10:53+2какие ещё блокировки в shared ptr???
Блокировки шины на атомарных операциях.
Kelbon
25.07.2022 08:10+12Вы с джавы пришли в С++? Почему у вас бесконечные выделения через new объектов, которые должны быть на стеке?
Почему бы не использовать bitset / vector<bool>, зачем писать свой велосипед?
Почему free list это опять какой то велосипед вместо std::vector?Почему везде инты? Вы знаете какой размер инта вообще?
почему вы кастуете поинтер сишным кастом к size_t и даже не uintptr_t? "тестирование" выглядит смешно если честно.
Нет ни намёка на синхронизацию, при том что многопоточный тест есть.
в make функции для поинера даже forward нет
Короче тут столько проблем, что их даже не перечислить
GrosSlava Автор
25.07.2022 10:191) Про использование new не понял вопроса. В общем случае количество объектов может быть большим, и мы не хотим переполнить стек. 1 лям, даже интов, класть на стек, что-то не хочется.
2) Согласен, можно использовать vector для bool, он тоже их пакует.
3) В статье представлен не финальный вариант. В движке большая часть интов заменены на беззнаковый вариант.4) Этот gc не будет работать в отдельном потоке, об этом речи и не шло. Многопоточная тут только сборка мусора на вызов ForceGC.
Kelbon
25.07.2022 10:50+1forward_list вы тоже на стек боитесь положить?
GrosSlava Автор
25.07.2022 11:03Размер forward_list 16 на 86-64. forward_list используется в мапе по структуре из пункта 2. Стек тоже не выдержит лям forward_list.)
Kelbon
25.07.2022 11:06+1у вас там ровно один std::forward_list<FAddrHandler>* ItemMap = nullptr;
Если не один, делаете контейнер явно.
В современном С++ семантика указателя не владеющее вью на 0 или 1 объект, всё. Более одного объекта - контейнер, не владеющее - вью(span или subrange), точно 1 - ссылка. Один или 0, но владеющее - optional
GrosSlava Автор
25.07.2022 11:09это сишный массив листов, возможно плохо акцентировал внимание.
Kelbon
25.07.2022 11:31что мешает вам сделать шаблон, где будет всё размешено на стеке, раз уж там всего лишь в конструкторе создаётся один раз массив(выделяется память), а потом уже снаружи этот тип выделить на куче ( в unique_ptr например), если вы так боитесь за стек?(хотя вы знаете на компиляции сколько там будет элементов)
Deranged
25.07.2022 12:05+5Ну, это не интересно. Ничего, что на уровне ниже еще есть C++ менеджер кучи? А там все ох как не просто. Раз уж взялись делать сборку мусора то менеджер кучи надо иметь свой. Так что только VirtualAlloc, только хардкор. По поводу адресов.
Для начала - все придумано до нас - см. как устроена структура адреса в винде (не знаю как там в Linux). Это не просто число, это иерархический идентификатор из частей - номер блока, номер страницы, смещение.
Потом - а что если по одному адресу сначала что-то освободится, а потом выделится другое? std::weak_ptr к такому устойчив.
Еще - а чем deleter'ы от std::shared_ptr не подходят? Зачем своя структура?
Основная фича GC - это нормальное съедание оторвавшихся подграфов объектов. А в С++ это не выйдет никак из-за кольцевых ссылок. Выехать можно только повторив всю "магию" из .NET-ного GC. Вот это к слову интересная идея - затащить часть .NET Core как .lib. Но не уверен, что оно так просто отчуждается.
Helltraitor
25.07.2022 18:52Я так и не понял, зачем нужен свой GC, если можно просто сохранить объекты как shared и освобождать все со значением 1 в нужное время
P.S. Имею в виду один класс с вектором shared указателей на объекты
GrosSlava Автор
25.07.2022 18:58Потому что с GC мы получаем возможность спрашивать валидность объекта не только сильной, но и слабой ссылки после удаления объекта. Тут не будет проблемы, если мы создадим случайно несколько разных "умных" указателей на один объект.
code_panik
25.07.2022 19:29+1Бросилось в глаза:
повторение inline в теле класса излишне, потому что метод, определенный в теле класса, по умолчанию inline;
лучше в GGarbageCollector* Get() возвращать (возможно const) ссылку, чтобы убрать ненужное разыменовывание указателя. Чтобы избежать неявных глобальных изменений данных, следует использовать глобальные const переменные. Синглтон - глобальный объект, поэтому лучше возвращать const ссылку и объявлять public методы const;
если служебный метод класса (напр. конструктор или деструктор) имеет поведение по умолчанию (пустое тело в коде), для наглядности лучше сделать его = default;
повторять несколько раз спецификаторы доступа к членам класса необязательно. Общий подход к размещению членов класса; https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Rl-order
аргумент IsNew конструктора TGCPointer(T* InObject, bool IsNew) не имеет прямого соотвествия полю класса, а участвует в скрытой логике реализации, вытаскивая её на поверхность. Наверное, следует пересмотреть дизайн класса;
get-методы, например TGCPointer::GetChecked, по названию, не должны менять состояния класса. GetChecked, вероятно, не get-метод, так как в теле выполняется несколько не связанных с получением данных действий. Следует переименовать, лучше разбить (или удалить, если не окажется полезным);
TGCPointer::operator=(T* Ptr) для произвольного адреса выглядит небезопасным;
в MakeGCPointer вместо аргументов выписаны типы аргументов, должно быть вроде new T{forward(args)...};
о замене size_t на uintptr_t и использовании reinterpret_cast вместо C-стиля; https://stackoverflow.com/questions/153065/converting-a-pointer-into-an-integer
delete допускает nullptr аргумент, проверка не нужна;
BitsPackSize и BitsPackMask следует связать через промежуточные вычисления, чтобы не вносить правки по отдельности руками;
функции, возвращающие FAddrHandler*, могут возвращать ссылку (const), чтобы не добавлять лишнего разыменовывания;
для получения данных, на которые указывает iterator в STL следует использовать разыменовывание; https://en.cppreference.com/w/cpp/named_req/Iterator
подход к реализации структуры данных с forward_list выглядит переусложненным. Можно было заменить внутренности реализации FAnyPtrMap на unordered_map;
Пока в целом код выглядит непродуманным - чересчур много ручной работы и частных случаев (напр. SyncRegisterExactlyNew, SyncRegister). В таком виде код не поддерживаемый и не расширяемый. После первых правок захочется всё выкинуть и написать заново.
Основная проблема - преждевременная оптимизация. Сначала следовало выделить интерфейс и выписать простую реализацию. Потом оценивать целевые показатели по времени (памяти) и оптимизировать по необходимости.GrosSlava Автор
25.07.2022 22:471) скорее да, но это часть код стайла движка. Там вообще используется свой FORCEINLINE по аналогии с UE4
2) согласен
3) возразить не могу, но это тоже часть стайла
4) стайл
5) часть оптимизации, если есть предложения, будет интересно почитать
6) возможно не нужен, но не очень страшно
7) все нормально, как раз фича этого GC, что мы устойчивы к возникновению в коде обычных с++ указателей
8) +
9) +
10) соглашение в проекте
11) +
12) +, даже ускорит
13) +
14) нужно проверить с тестами производительности, не уверен, что будет быстрее
15) супер расширяемый код тоже не есть хорошо. В данном месте ровно столько, сколько нужно.
qw1
25.07.2022 21:19+1Вообще не понимаю, какие тут плюсы перед shared_ptr.
GC вводят для решения двух проблем
1. Циклические ссылки
2. Проблема shared_ptr в многопоточной среде, когда для инкремента указателя надо поставить lock.
Здесь при создании/удалении умных указателей такой же++Count; ++TotalObjectsCount;
Просто автор не позаботился о корректности в многопоточной среде и не поставил блокировки.
То есть, обе проблемы не решены.
Есть ещё проблема с распихиванием указателей по бакетам:inline unsigned int GetLocalAddr(size_t Addr) const noexcept { return Addr & BitsPackMask; // Addr % BitsPackSize } const size_t LAddr = (const size_t)Ptr; auto& LItems = ItemMap[GetLocalAddr(LAddr)];
Все Ptr выравнены по границе 8 байт, а значит, в массиве ItemMap только каждый 8-й forward_list будет реально задействован, остальные будут созданы впустую.GrosSlava Автор
25.07.2022 22:27-1Верно, текущая версия не предусматривает использование GC в отдельном потоке. Сейчас он работает в основном по таймеру.
Про выравнивание указателей - спасибо, еще место для оптимизации памяти.
Про плюсы перед shared_ptr я в статье затрагивал, но GC, это другой подход к контролю памяти в принципе. Поэтому их некорректно сравнивать.qw1
25.07.2022 22:48текущая версия не предусматривает использование GC в отдельном потоке. Сейчас он работает в основном по таймеру
Тут вопрос не сколько в GC, сколько вообще в возможности работать в несколько потоков. Что будет, если запустить 8 потоков и в каждом аллоцировать? Ответ: forward_list сломаются, т.к. они на такое не расчитаны. А многопоточность в играх сейчас уже must-have.Про плюсы перед shared_ptr я в статье затрагивал
По перфомансу? Вы неверно используете его, вместо
надо использовать make_shared. Это удвоит производительность и вероятно сократит разрыв между ним и вашим GC.auto A = std::shared_ptr<TestStruct>((new TestStruct()));
Kelbon
26.07.2022 08:46какой лок? Там локфри
qw1
26.07.2022 09:40+2Лок не в смысле отдельного mutex-а, а хардварный лок на линию кеша в атомарном инкременте/декременте счётчика ссылок. По производительности это так же больно, как mutex/критическая секция, потому что под капотом всё тот же LOCK XADD или LOCK CMPXCHG
0xd34df00d
26.07.2022 16:54+1Так же больно, как мьютекс в оптимистичном сценарии на нормальной ОС. Так-то мьютекс может и в ядро уйти поспать-зарешедулить процесс.
iboltaev
26.07.2022 17:471) на кой ляд C++ сборщик мусора?? Автоматическая память - ваш бро.
2) boehm gc
thatsme
Ключевой вопрос: "Зачем нужен GC, когда код на C++?".
MagMagals
В том же Qt он есть, наверно не просто так его создали...
code_panik
В Qt нет gc. Есть объекты, владеющие ресурсами. Сборка мусора и владение ресурсом - разные коцепции.
F0iL
Бывают весьма специфичные случаи, как у Google, например.