Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.
Хочется сделать GC для С++ и показать, что он вполне возможен. Вопрос: "а почему же GC не используется в С++?" за пределами данной темы.
Задача 1: свести оверхед по синтаксису к минимуму
Хочется писать нормально, без специальных наследований и функций, т.е. использовать обычные классы и встроенные типы, со стандартизированной аллокацией памяти, без необходимости её индивидуальной отчистки.
Задача 2: свести оверхед по перфомансу к минимуму
Хотелось бы, чтобы всё работало более-менее быстро и чётко. Т.е. GC не должен пробегать всю память в поисках всего, а проверть только то что нужно.
Буду использовать следующие названия:
P<Type> — обозначение gc указателя. Пример:
P<int>, P<CMySuperClass>
gc_array<Type> — обозначение gc массива, аналогичного стандартному сишному. Пример:
gc_array<int>, gc_array<Node>
gc_new<Type> — функция аллокации gc блока. Пример:
P<CMySuperClass> super_object = gc_new<CMySuperClass>( param1, param2, param3 );
gc_new_array<Type> — функция аллокации массива. Пример:
gc_array<P<Node> > node = gc_new_array<P<Node> >( 10 ); node[1] = gc_new<Node>();
gc_this, GC_NULL — думаю понятно.
Эти названия не преследуют никаких религиозных целей, просто первые что пришли в голову.
Деструкторы объектов превращаются в финализаторы. Следовательно, внутри GC-объектов можно хранить данные аллокированные обычным путём.
Пример который должен корректно работать:
#include "rtl_gc.h"
struct A {
float m_f;
virtual ~A() {}
};
struct B : public A {
int m_i;
P<A> m_a;
P<B> m_b;
};
struct C : public A {
std::vector<int> vec;
};
P<A> MakeA()
{
P<C> c = gc_new<C>();
c->vec.resize(10);
return c;
};
void Test()
{
P<A> a1;
{
P<B> b1 = gc_new<B>();
b1->m_a = MakeA();
b1->m_b = b1;
a1 = b1->m_b;
}
Pool::Instance().GC();
// Всё что мы создали - ещё живо
a1 = GC_NULL;
// Недоступно, но ещё живо
Pool::Instance().GC();
// Всё убито
}
Важная особенность системы на данный момент:
GC-указатели могут храниться только в статической памяти, в стеке и в gc-объектах
Т.е. пока нельзя делать так:
std::vector<P<Node> >
или так:
void Func()
{
static P<Node> node;
}
После некоторых размышлений решил, что первое ограничение вполне допустимо — так как оно спасает от возникновения циклических ссылок, а следовательно от утечек памяти. Второе ограничение, в будущем, можно разрешить.
Ещё важное, на данный момент, ограничение — указатель всегда должен указывать на начало блока памяти выделенной для объекта. Т.е. ситуации со сложным наследованием, указатели на агрегированные мемберы объектов или элементы массивов — недопустимы. При необходимости эту фичу можно реализовать (хотя такой фичи нет под явой и шарпом).
Так же:
О стиле оформления кода пока совершенно не заботился. Многие мемберы почём зря в паблик секции и т.п. Пока это не важно.
Так же целенаправленно не заботился о низкоуровневой оптимизации, в частности о работе внутренних контейнеров.
Совершенно не заботился об оптимальности алгоритма отчиски и выделения памяти, корректной работе с потоками и о множестве других важных вещей, которые счёл второстепенными на данном этапе, но решаемыми в будущем.
Для предоставления аллокатору всей необходимой информации об объекте был использован один старый вспомогательный класс:
class variant_type
{
public:
typedef void (*TFCopyConstructor)(void* /*dst*/, const void* /*src*/);
typedef void (*TFDestructor)(void* obj);
typedef std::vector<std::pair<ptrdiff_t, const variant_type*> > TSubPointers;
const char* m_Name;
size_t m_Size;
size_t m_AlignSize;
TFCopyConstructor m_CopyCnstr;
TFDestructor m_Destructor;
bool m_Initialized;
TSubPointers m_Pointers;
template<class T>
static variant_type* type_id()
{
static variant_type static_type( *(T const*)0 );
return &static_type;
}
private:
...
};
Надеюсь, тут всё понятно из контекста.
Все мемберы кроме m_Pointers заполняются в конструкторе данного класса который вызывается внутри функции variant_type::type_id. Примеры допустимого использования:
const variant_type* vt = variant_type::type_id<CMySuperClass>();
std::cout << vt->m_Name << " " << vt->m_Size;
CMySuperClass my_super_class;
byte* buf = new byte[vt->m_AlignSize];
vt->m_CopyCnstr( buf, &my_super_class );
CMySuperClass* object = reinterpret_cast<CMySuperClass*>( buf );
AnyUse( object );
vt->m_Destructor( buf );
delete[] buf;
m_Pointers (которых не было раньше) — инициализируются внутри функций аллокации gc памяти только один раз, контролируется это флажком m_Initialized. m_Pointers хранит смещение субуказателя от начала блока памяти объекта. Т.е. для класса:
class Foo
{
P<int> i;
int fake;
P<CMySuperClass> m;
};
значение type_id<Foo>->m_Pointers, после первого вызова gc_new<Foo>, будет примерно такое: [0, 8]
Данный класс поможет нам:
1. обходить граф объектов без оверхеда по скорости.
2. перемещать объекты из одного куска памяти, в другой. Естественно у них должны быть корректные копирующие конструкторы.
3. корректно уничтожать объект в ходе отчистки мусора.
Конечному пользователю знать про данный класс не обязательно, хотя его можно выгодно использовать в variant'e, для которого он и был изначально разработан.
class Pool — синглетон, содержит следующие функции:
template<class T> void ProcessPointer(void** ppointer);
Функция проверяет, что указатель попадает в аллокируемый блок памяти, а следовательно, что он является мембером нового объекта. Иначе — он считается корневым и попадает в стек корневых указателей.
template<class T> void FreePointer(void** ppointer);
Функция проверяет — является ли данный указатель корневым. Если он корневой — его удаляют из стека.
void GC();
Чистка памяти. Обходится граф объектов, помечаются используемые, после чего используемые копируются в новый блок памяти, а неиспользуемые — удаляются. Все существующие указатели правятся автоматически.
static Pool& Instance();
Возвращает глобальный пул.
template<class T, class Arg1, ...> P<T> gc_new(const Arg1& arg1, ...)
Функции аллокации памяти.
Пул содержит следующие данные:
Блок памяти в котором распределяются все объекты. Эта часть пока очень примитивна — выделяется мегабайт в std::vector. В памяти последовательно располагаются блоки под объект(ы), каждый блок содержит шапку: variant_type* и unsigned int. В первых 30 битах инта хранится количество объектов в блоке памяти (для массивов), в 2 битах — флаги. Флаг пока один — Marked, отметка о том, что до данного блока можно дойти от корневых указателей. Выглядит всё как-то так:
[variant_type*][30 бит — count of objects][2 бита — флаги][(variant_type::m_Size * Count + 3) & (~3) байт под объект(ы)]][следующий объект]
Стек корневых указателей. Предполагается, что все корневые указатели выделяются в глобальной памяти или на стеке — а следовательно создаются и уничтожаются в режиме FIFO (c одним исключением).
Стек конструкторов. После выделения памяти, но перед созданием объекта — в этот стек добавляется описание нового блока. Это нужно для работы следующего псевдокода:
- Для каждого конструктора объекта-указателя:
- Если я пересекаюсь с верхним элементом стека конструкторов то:
- Следовательно я мембер нового объекта и должен попытаються
отметиться в соответствующем variant_type если флажок m_Initialized == false
- Иначе:
- Я корневой указатель и должен добавиться в стек корневых указателей.
После конструирования объекта описание блока удаляется из стека.
Очень простой класс, регистрирующий и разрегистрирующий объект-указатель в пуле и лишающий возможности совершать над указателем арифметические действия. gc_array — сделан строго аналогично, разве что операторы * и -> не определяет, но взамен есть оператор [].
template<class T>
class P
{
public:
P() { Pool::Instance().ProcessPointer( (void**)this ); }
P(const P<T>& ) { Pool::Instance().ProcessPointer( (void**)this ); }
~P() { Pool::Instance().FreePointer( (void**)this ); }
template<class U>
P(const P<U>& ) { Pool::Instance().ProcessPointer( (void**)this ); }
T* operator->() { return p; }
// функции сравнения, разыменования, работы с GC_NULL и т.п.
...
private:
T* p;
};
Работает примерно так:
template<class T>
P<T> Pool::gc_new()
{
// Получаем рантайм тип.
variant_type* vt = variant_type::type_id<T>();
// Получаем блок памяти для объекта
// Очень дешёвая операция, просто увелчиваем счётчик размера выделенной памяти на (sizeof(TMemBlock) + sizeof(T))
P<T> p; p.p = (T*)GetMemory( vt );
// проверяем иницилизированность рантайм типа и если нет - начинаем инициализацию:
if ( !vt->m_Initialized )
vt->m_Pointers.resize( 0 );
// добавляем в стек конструкторов информацию об обрабатываемом блоке памяти:
m_builder.push_back( Pool::TAllocatingBlock( (byte*)p.p, vt) );
// конструируем объект
new (p.p) T;
// все указатели-мемберы уже отмечены
m_builder.pop_back();
// и рантаймтип в любом случае уже инициализирован
vt->m_Initialized = true;
return p;
}
P<T> gc_new()
{
return Pool::Instance().gc_new<T>();
}
Остальные gc_new и gc_new_array сделаны по аналогии.
После работы с объектами у нас, в едином блоке памяти, существует сформированный граф объектов и список корневых указателей. Алгоритм отчитки очень прост:
void Pool::GC()
{
//Рекурсивно, начиная с корневых указателей, обходим доступный граф и помечаем заголовки блоков как доступные.
MarkUsedBlocks();
// Выделяем новый кусок памяти.
std::vector<uint8_t> window( m_buffer.size() );
// Последовательно проходим по всем блокам.
// Если они отмечены - копируем соответствующий объект с помощью variant_type::m_CopyCnstr
// в новый блок, и в заголовок старого блока (вместо variant_type) происываем diffptr_t между новым и старым блоком.
// Если блок не был отмечен - он удаляется с помощью функции: variant_type::m_Destructor
MoveUsedBlocks( &window[0], m_allocated );
// делаем актуальным новый блок
window.swap( m_buffer );
// Последовательно проходим по всем блокам и обновляем им указатели используя diffptr_t записанный в старой памяти
UpdatePointersInNewBlocks( &m_buffer[0], &m_buffer[0] + m_allocated );
// Проходим по всем корневым указателям и обновляем их тоже
UpdateRootPointers();
В качестве проверки минимальной работоспособности я написал простой аналог stl::list — gc_list. Его можно посмотреть в примере.
В примере же продемонстрировны базовые возможности.
Нельзя создавать указатели указывающие не на начало блока.
Данная возможность по понятным причинам не предусмотренна ни в шарпе ни в яве. В данной системе её тоже хотелось бы избежать, но если очень нужно в класс-указатель можно внест ещё один мембер — diffptr_t, который будет хранить разницу между данным указателем и началом блока объекта. Это чревато увеличением размера указателя в 2 раза.
Нельзя создавать корневые указатели в качестве статических объектов в функциях.
Пока решение видится только путём введения ещё одного специализированного типа-указателя, например: StaticP. Это плохое решение. Надо думать.
Метод аллокации и отчитки нужно разрабатывать, то что существует сейчас — исключительно в первородном состоянии.
Пока аллокатор не работает в рамках нескольких модулей (exe и dll)
Эта проблема решается сравнительно легко — путём введения кроссмодульного синглетона который отвечает за синхронизацию внутримодульных синглетонов (variant_type и Pool).
На данный момент может существовать только один аллокатор памяти, нельзя делать отдельные пулы.
По этому поводу есть мысли, надо развивать. Например, внутри основного пула можно сделать несколько внутрених и выделять память в них, и при необходимости чистить только только их, а не всю память.
Почти не думал на тему многопоточности и exception safe
Возвращаемые из функций переменные живут не в режиме FIFO.
Для исправления этого сделано некрасивое решение — при удалении из стека корневых указателей рассматриваются последние 2 элемента, а не один как то положено для нормального стека.
Выравнивание сделано очень криво.
Предусмотрено выравнивание по 4 байта, но этого едостаточно.
Про вопрос применимости всей этой системы — вообще молчу 8-)
Код и примеры тут:
http://www.dr-gucho.com/downloads/TestGC.zip