Пример GC для С++
От: NikeByNike Россия  
Дата: 18.06.08 19:08
Оценка: 26 (2)
Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.

Задача

Хочется сделать 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;
    };



    gc_new

    Работает примерно так:
    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
  • Нужно разобрать угил.
    Re: Пример GC для С++
    От: Аноним  
    Дата: 18.06.08 21:39
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    Реализовать GC не проблема библиотекой, проблема только в том что очень много соглашений о которых нужно помнить и нужно им следовать. А что бы все было прозрачно для пользования нужно его делать на уровне языка, что бы и базовые типы были managed по необходимости конечно типа опцией компилера или сделать блоки кода __managed{ int i=0; i++; }; __unmanaged{ int j=0; j++; }; Вот тогда будет
    Re: Пример GC для С++
    От: Сергей Мухин Россия  
    Дата: 18.06.08 22:53
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    NBN>Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.


    очень много букв. Идеи не видно.

    Простой вопрос консервативный GC предлагается? Поддержка на уровне языка или администритивно?
    ---
    С уважением,
    Сергей Мухин
    Re[2]: Пример GC для С++
    От: remark Россия http://www.1024cores.net/
    Дата: 18.06.08 22:58
    Оценка:
    Здравствуйте, Сергей Мухин, Вы писали:

    СМ>Здравствуйте, NikeByNike, Вы писали:


    NBN>>Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.


    СМ>очень много букв. Идеи не видно.


    СМ>Простой вопрос консервативный GC предлагается? Поддержка на уровне языка или администритивно?


    На первый взгляд, GC точный, а вся поддержка в присоединенном архиве


    1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
    Re: Пример GC для С++
    От: Odi$$ey Россия http://malgarr.blogspot.com/
    Дата: 19.06.08 02:57
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    NBN>Хочется сделать GC для С++ и показать, что он вполне возможен.


    http://rsdn.ru/article/cpp/GCcpp.xml
    Автор(ы): Михаил Чащин
    Дата: 18.11.2002
    ... << RSDN@Home 1.2.0 alpha 4 rev. 1090>>
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 19.06.08 08:25
    Оценка:
    Здравствуйте, Аноним, Вы писали:

    А>Реализовать GC не проблема библиотекой, проблема только в том что очень много соглашений о которых нужно помнить и нужно им следовать.

    Есть такое. Но при разработке в С++ при любом подходе есть очень много соглашений. В частности при использовании shared_ptr. Сейчас в первом приближении эта система совершенно никак не защищена, но над этим нужно просто поработать.

    А>А что бы все было прозрачно для пользования нужно его делать на уровне языка, что бы и базовые типы были managed по необходимости конечно типа опцией компилера или сделать блоки кода __managed{ int i=0; i++; }; __unmanaged{ int j=0; j++; }; Вот тогда будет

    Спорно ИМХО. Это какие-то сильно конкретные частности. Сахара бы хотелось, но более обобщённого Например, сильно угнетает, что нужно много писать:
    P<MyClass> p = gc_new<MySuperClass>();
    Хотелось бы:
    MyClass^ p = gc_new MySuperClass();

    И т.п. вещи.
    Нужно разобрать угил.
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 19.06.08 08:33
    Оценка:
    Здравствуйте, Сергей Мухин, Вы писали:

    СМ>очень много букв. Идеи не видно.

    Всю идею постарался изложить в начале, примерно до "Основа"

    СМ>Простой вопрос консервативный GC предлагается?

    Тип сборщика видимо:

    Copying (Копировщики): При этом хранилище памяти делится на две части и данные существуют только на одной из них. Периодически, производится копирование данных из одной части в другую начиная с "базовых" элементов. Теперь новая занятая секция памяти становится активной, а все оставшееся на другой части считается мусором. Так же, когда происходит это копирование, все указатели обновляют свое значение и указывают на новое положение памяти.

    Т.е. не консервативный.

    СМ>Поддержка на уровне языка или администритивно?

    Смешанно. Пока, явно, преобладает поддержка административная, но если буду развивать эту систему — то постараюсь её уменьшить за счёт средств языка.
    Нужно разобрать угил.
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 19.06.08 08:46
    Оценка:
    Здравствуйте, Odi$$ey, Вы писали:

    NBN>>Хочется сделать GC для С++ и показать, что он вполне возможен.


    OE>http://rsdn.ru/article/cpp/GCcpp.xml
    Автор(ы): Михаил Чащин
    Дата: 18.11.2002


    Эту статью видел, правда довольно давно. На мой взгляд эта система малоюзабельна — слишком много писанины. В качестве первоочередной задачи я ставил минимизацию размера кода с сохраненим эффективности сборки мусора.

    Например:
    http://www.hpl.hp.com/personal/Hans_Boehm/gc/
    Штука интересная — но явно слишком тормозная и чреватая ошибками, хотя и неопасными.

    http://hnxgc.harnixworld.com/prog_b01.htm
    Тоже, интересно, хотя подробно я ещё не изучал. Но там нужно описывать метаинформацию для всех используемых классов. Это не супер.
    Нужно разобрать угил.
    Re: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 10:30
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    Получается какое-то половинчатое решение — с одной стороны рассматриваются голые указатели, с другой стороны вводится иерархия объектов, с ограничениями и т.п. По моему, нужно что-то одно — или никаких ограничений на голые указатели или никаких голых указателей, зато любые ограничения на иерархию объектов. В принципе, shared_ptr идет по второму пути — нельзя взять указатель из одного shared_ptr и свободно передать его в другой. Так как многие пользуются shared_ptr и аналогами и никаких затруднений нет, то я бы отталкивался от них, просто надо решить проблему циклических ссылок.

    Вообще, вводя ограничения, можно существенно упростить задачу. Например, все gc-классы должны наследоваться от некоторого общего предка, gc-объект можно создать только в (логической) gc-куче — на стеке нельзя, внутри gc объекта может быть только gc-ссылка на другой gc объект, снаружи можно держать gc и не-gc (корневые) ссылки на gc-объекты, то задача становится уже не такой сложной. Потом, сами объекты вполне можно размещать в обычной куче, в всякую компактификацию делать на указателях, в этом случае можно хранить указатель внутрь объекта, если у тебя есть корневая ссылка на него.

    Вот такие соображения :)
    Re[2]: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 10:41
    Оценка:
    Да, доступ к gc объектам можно делать только через корневые указатели — т.е. как в паре shared/week_ptr. В корневом указателе, вполне можно хранить непосредственный указатель на объект, в этом случае обеспечивается быстрый доступ — без лишнего уровня косвенности.
    Re[3]: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 10:53
    Оценка:
    Кстати, так как весь доступ идет через корневые указатели, то преобразование gc_ptr -> root_ptr, вполне естественное место, для приостановки потока при сборке мусора — там просто ставится критическая секция. Сборка мусора, это просто проход по массиву (или списку) промежуточных указателей — на которые ссылаются gc_ptr, и последовательное копирование. Тут проблема как определить, на какие gc-объекты есть ссылка из другого объекта, можно для каждого gc-объекта хранить список gc-указателей, это можно делать прямо в конструкторе gc_ptr(gc_object* parent).
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 19.06.08 10:59
    Оценка:
    Здравствуйте, COFF, Вы писали:

    COF>Получается какое-то половинчатое решение — с одной стороны рассматриваются голые указатели, с другой стороны вводится иерархия объектов, с ограничениями и т.п.

    Не понял...
    Где рассматриваются голые указатели? Если ты имеешь в виду публичный P::p — то это просто недоделка, они должны быть закрытые и пользователь не будет иметь к ним доступ write, да и read тоже (в будущем, если буду развивать эту тему).

    COF>В принципе, shared_ptr идет по второму пути — нельзя взять указатель из одного shared_ptr и свободно передать его в другой.

    Проблема у него как раз в том, что это сделать легко и если shard_ptr не интрузивный — это приведёт к фатальным последствиям.

    COF>Так как многие пользуются shared_ptr и аналогами и никаких затруднений нет, то я бы отталкивался от них, просто надо решить проблему циклических ссылок.

    Ну вот gc это и решает...

    COF>Вообще, вводя ограничения, можно существенно упростить задачу. Например, все gc-классы должны наследоваться от некоторого общего предка

    ИМХО это радикально снизит универсальность...

    COF>gc-объект можно создать только в (логической) gc-куче — на стеке нельзя

    А в чём смысл этого запрета? Создав в стеке объект класса предназначенного для аллокации в gc — ты ничем не рискуешь, получить gc указатель на него нельзя (если не считать недоделанный this, но это поправимо — можно вставить проверку). Т.е. это снижение универсальности без особой необходимости.

    COF>внутри gc объекта может быть только gc-ссылка на другой gc объект

    ИМХО это на усмотрение кодингстандарта и, возможно, стратегий.

    COF>снаружи можно держать gc и не-gc (корневые) ссылки на gc-объекты

    Вобщем-то нельзя держать не-gc указатели на gc объекты. Есть, кстати, большая проблема с this — который не меняется при перемещении объекта и не является корневым указателем — т.е. не держит объект
    Нужно разобрать угил.
    Re[3]: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 11:54
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    COF>>Вообще, вводя ограничения, можно существенно упростить задачу. Например, все gc-классы должны наследоваться от некоторого общего предка

    NBN>ИМХО это радикально снизит универсальность...

    Ну, жертвуя одним, мы можем резко выиграть в другом. Так, снизив универсальность, мы упрощаем реализацию. Ну и так далее. Потом, если ты не знаешь базового класса объекта, как ты будешь звать деструктор? Ты получаешь все проблемы, связанные с финализаторами. Память чистится, а за вызовом деструкторов все-равно надо следить. В моей схеме, деструкторы будут вызываться.

    COF>>gc-объект можно создать только в (логической) gc-куче — на стеке нельзя

    NBN>А в чём смысл этого запрета? Создав в стеке объект класса предназначенного для аллокации в gc — ты ничем не рискуешь, получить gc указатель на него нельзя (если не считать недоделанный this, но это поправимо — можно вставить проверку). Т.е. это снижение универсальности без особой необходимости.

    Сразу упрощается реализация. Что такое gc_ptr тогда получится? Это указатель на некий вспомогательный объект (структуру), этот вспомогательный объект сам в свою очередь держит gc-объект в обычной куче. Вся информация, которая нужна gc — это массив (список) вот этих вспомогательных объектов. Компактификацию можно проводить над ним — не надо копировать объекты. Т.е. получается такая схема: gc_ptr -> gc_data -> gc_object.

    COF>>снаружи можно держать gc и не-gc (корневые) ссылки на gc-объекты

    NBN>Вобщем-то нельзя держать не-gc указатели на gc объекты. Есть, кстати, большая проблема с this — который не меняется при перемещении объекта и не является корневым указателем — т.е. не держит объект :(

    Так у меня это решается таким образом. gc_data содержит счетчик ссылок. Счетчик ссылок изменяется при изменении root_ptr, которые ссылаются на эту gc_data. Доступ к gc_object возможен только через root_ptr. Т.е. если у тебя есть gc_ptr, ты должен преобразовать его предварительно в root_ptr (положив скорее всего на стек) — это решает проблему с this и многопоточностью. Потом, снаружи ты держишь gc_object только через root_ptr (ну и может быть weak_root_ptr, который на самом деле почти полный аналог gc_ptr). При компактификации мы блокируемся, создаем новый массив gc_data, сразу копируем те из них, у которых счетчик ссылок ненулевой — это будут корневые объекты, потом по графу зависимостей копируем достижимые объекты, потом удаляем все недостижимые. Даже можно не создавать новый массив, а просто обнулять слоты в существующем. Тут, кстати, никаких проблем с исключениями быть практически не может, так как мы не копируем сами объекты. И все это будет работать очень быстро. То есть вот такая примерно схема, что пришла в голову и я бы, наверное, так и сделал.

    Более того, очевидно, что root_ptr должен хранить и ссылку на gc_data, тогда внутри себя он вообще может хранить любой указатель внутрь объекта.
    Re[4]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 19.06.08 12:12
    Оценка:
    Здравствуйте, COFF, Вы писали:

    COF>Ну, жертвуя одним, мы можем резко выиграть в другом. Так, снизив универсальность, мы упрощаем реализацию. Ну и так далее. Потом, если ты не знаешь базового класса объекта, как ты будешь звать деструктор? Ты получаешь все проблемы, связанные с финализаторами. Память чистится, а за вызовом деструкторов все-равно надо следить. В моей схеме, деструкторы будут вызываться.

    Деструкторы и так вызываются, демонстрация этого есть в примере. Деструктор определяется при создании объекта и хранится в variant_type::m_Destructor. Указатель на variant_type хранится в том же блоке памяти что и сам объект.

    COF>>>gc-объект можно создать только в (логической) gc-куче — на стеке нельзя

    NBN>>А в чём смысл этого запрета? Создав в стеке объект класса предназначенного для аллокации в gc — ты ничем не рискуешь, получить gc указатель на него нельзя (если не считать недоделанный this, но это поправимо — можно вставить проверку). Т.е. это снижение универсальности без особой необходимости.

    COF>Сразу упрощается реализация. Что такое gc_ptr тогда получится?

    В данном случае — это простой указатель на объект, завёрнутый в хелпер. Проще некуда

    COF>Это указатель на некий вспомогательный объект (структуру), этот вспомогательный объект сам в свою очередь держит gc-объект в обычной куче. Вся информация, которая нужна gc — это массив (список) вот этих вспомогательных объектов. Компактификацию можно проводить над ним — не надо копировать объекты. Т.е. получается такая схема: gc_ptr -> gc_data -> gc_object.

    Да вобщем-то копировать объекты и так не особо нужно, это было проще всего, поэтому пока так.

    COF>Так у меня это решается таким образом. gc_data содержит счетчик ссылок. Счетчик ссылок изменяется при изменении root_ptr, которые ссылаются на эту gc_data. Доступ к gc_object возможен только через root_ptr. Т.е. если у тебя есть gc_ptr, ты должен преобразовать его предварительно в root_ptr (положив скорее всего на стек) — это решает проблему с this и многопоточностью.

    По моему структур уже многовато, это усложняет библиотеку. А по поводу this...
    С многопоточностью это ничего особо не решит — так как пока ты преобразуешь указатель в root_ptr — сборщик мусора может успеть отработать раз 10 и this станет заведомо невалидным. После чего всё красиво упадёт.

    COF>Более того, очевидно, что root_ptr должен хранить и ссылку на gc_data, тогда внутри себя он вообще может хранить любой указатель внутрь объекта.

    Дело в том, что для корректной работы с указателями на внутренности объекта — двойной размер нужен не только рутовым указателям, но и обычным указателям мемберам. Кроме того ИМХО в качестве параметра логичнее хранить разницу между указателем и данными, а не два указателя.
    Нужно разобрать угил.
    Re[4]: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 12:20
    Оценка:
    Т.е. структура данных примерно такая

    
    class gc_object;
    class gc_ptr;
    
    struct gc_data: public noncopyable
    {
      int root_count;
      gc_object* obj;
      gc_data* next;
    };
    
    class gc_ptr: public noncopyable
    {
    public:
      gc_ptr(gc_object* parent): { next = parent->child; parent->child = this; }
    
    private:
      gc_data* data;
      gc_ptr* next;
    };
    
    class gc_object: public noncopyable
    {
    public:
      gc_object(): child(0) {}
      virtual ~gc_object() {}
    
    private:
      gc_ptr* children;
    };
    
    template <class T>
    class root_ptr
    {
    private:
      gc_data* data;
      T* p;
    };
    
    class gc: public noncopyable
    {
    private:
      gc_data* active_blocks;
      gc_data* free_blocks;
    };
    Re[5]: Пример GC для С++
    От: COFF  
    Дата: 19.06.08 12:27
    Оценка:
    COF>>Так у меня это решается таким образом. gc_data содержит счетчик ссылок. Счетчик ссылок изменяется при изменении root_ptr, которые ссылаются на эту gc_data. Доступ к gc_object возможен только через root_ptr. Т.е. если у тебя есть gc_ptr, ты должен преобразовать его предварительно в root_ptr (положив скорее всего на стек) — это решает проблему с this и многопоточностью.
    NBN>По моему структур уже многовато, это усложняет библиотеку. А по поводу this...
    NBN>С многопоточностью это ничего особо не решит — так как пока ты преобразуешь указатель в root_ptr — сборщик мусора может успеть отработать раз 10 и this станет заведомо невалидным. После чего всё красиво упадёт.

    Если грамотно написать, то не упадет. Достаточно атомарной операцией увеличить счетчик ссылок в gc_data в первую очередь и все — никакой сборщик мусора уже не страшен. Кстати, в начале любой цепочки вызовов по любому будет стоят root_ptr и this не нужно никуда преобразовывать.

    COF>>Более того, очевидно, что root_ptr должен хранить и ссылку на gc_data, тогда внутри себя он вообще может хранить любой указатель внутрь объекта.

    NBN>Дело в том, что для корректной работы с указателями на внутренности объекта — двойной размер нужен не только рутовым указателям, но и обычным указателям мемберам. Кроме того ИМХО в качестве параметра логичнее хранить разницу между указателем и данными, а не два указателя.

    Ну, это необходимые издержки. Вообще, я сразу скажу, что не спорю с тобой, а просто предлагаю свой взгляд на проблему. Причем, конечно, мой подход можно и улучшить — это просто соображения на ходу :)
    Re[3]: Пример GC для С++
    От: remark Россия http://www.1024cores.net/
    Дата: 19.06.08 22:33
    Оценка:
    Здравствуйте, NikeByNike, Вы писали:

    NBN>http://hnxgc.harnixworld.com/prog_b01.htm

    NBN>Тоже, интересно, хотя подробно я ещё не изучал. Но там нужно описывать метаинформацию для всех используемых классов. Это не супер.


    Там интересным смешанным образом производится обнаружение мусора. Основная часть (не рекурсивный мусор) обнаруживается с помощью подсчёта ссылок, что как бы в духе С++ и соотв. ожиданиям программистов о реактивном вызове деструктора и освобождении памяти. Рекурсивный мусор обнаруживается уже с помощью традиционного исследования графа досягаемости объектов. Можно предположить, что во многих программах большая часть будет собираться с помощью подсчета ссылок, т.е. анализ графа досягаемости можно запускать очень редко. В программах, которые не производят рекурсивного мусора, вообще анализ графа не будет запускаться. Но тем не менее, он будет "там" на всякий случай.

    Так же, насколько помню, он параллельный и одновременный.



    1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
    Re: Пример GC для С++
    От: Tilir Россия http://tilir.livejournal.com
    Дата: 20.06.08 10:43
    Оценка: 8 (1)
    Здравствуйте, NikeByNike, Вы писали:

    NBN>Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.


    Ну почему же... Опциональный GC -- вещь вполне хорошая и полезная. Вроде как даже в новом стандарте будет. GC плох когда навязывается без вариантов и контроля.

    NBN>

    Задача

    NBN>Хочется сделать GC для С++ и показать, что он вполне возможен. Вопрос: "а почему же GC не используется в С++?" за пределами данной темы.

    Используется. Это примерно как калькулятор математических выражений -- каждый сам себе это метро копает и сам себя в этом метро катает пока не рухнет и сверху не придавит. Поверхностное рассмотрение ваших идей наводит на мысль, что вы ещё не прочитали вторую главу вот этой замечательной книжки: http://www.infanata.org/2007/08/17/iskusstvo_programmirovanija_na_s.html. Для подобного велосипедостроения очень рекомендую.
    Re[2]: Пример GC для С++
    От: COFF  
    Дата: 20.06.08 11:18
    Оценка:
    Здравствуйте, Tilir, Вы писали:

    T>Используется. Это примерно как калькулятор математических выражений -- каждый сам себе это метро копает и сам себя в этом метро катает пока не рухнет и сверху не придавит. Поверхностное рассмотрение ваших идей наводит на мысль, что вы ещё не прочитали вторую главу вот этой замечательной книжки: http://www.infanata.org/2007/08/17/iskusstvo_programmirovanija_na_s.html. Для подобного велосипедостроения очень рекомендую.


    Скачал и бегло просмотрел. Мне понравилось решение проблемы циклических ссылок :) Забавно, хотя от Шилдта я большего и не ожидал — видел пару его книжек до этого
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 20.06.08 12:21
    Оценка:
    Здравствуйте, Tilir, Вы писали:

    NBN>>Мысли в слух и по сути бесполезная вещь, убеждённым практикам — не читать.

    T>Ну почему же...
    Это я про данную конкретную заметку
    Сильно обрадовался когда нашёл способ сделать GC без лишней писанины и проблем со скоростью, решил об этом сообщить. Но так как ничего кроме демонстрации этих возможностей заметка не предлгает — сообщил, что по сути она бесполезная — голая теория.

    T>Опциональный GC -- вещь вполне хорошая и полезная.

    Сложно сказать. Если программеры не профи — они не смогут беспроблемно использовать gc в С++ (в отличии от явы и шарпа). А если профи — то gc не нужен.

    T>Вроде как даже в новом стандарте будет.

    Насколько я понял, там будет несколько хелперов для облегчения разработки либных gc на подобии сабжевого. Т.е. без оверхеда по синтаксису и скорости.

    T>GC плох когда навязывается без вариантов и контроля.

    Без контроля точно плохо, а вот без вариантов? Ява и шарп живут и здравствуют.

    T>Используется. Это примерно как калькулятор математических выражений -- каждый сам себе это метро копает и сам себя в этом метро катает пока не рухнет и сверху не придавит.

    Реальных применений я пока не видел, несмотря на довольно большую базу наблюдений. Кто-то конечно использует, но это не мейнстрим и даже не тенденция.

    T>Поверхностное рассмотрение ваших идей наводит на мысль, что вы ещё не прочитали вторую главу вот этой замечательной книжки: T>http://www.infanata.org/2007/08/17/iskusstvo_programmirovanija_na_s.html. Для подобного велосипедостроения очень рекомендую.

    Книжку не видел, почитаю. Спасибо за рекомендацию
    Нужно разобрать угил.
    Re[2]: Пример GC для С++
    От: NikeByNike Россия  
    Дата: 22.06.08 12:13
    Оценка: 1 (1)
    Здравствуйте, Tilir, Вы писали:

    T>Используется. Это примерно как калькулятор математических выражений -- каждый сам себе это метро копает и сам себя в этом метро катает пока не рухнет и сверху не придавит. Поверхностное рассмотрение ваших идей наводит на мысль, что вы ещё не прочитали вторую главу вот этой замечательной книжки: http://www.infanata.org/2007/08/17/iskusstvo_programmirovanija_na_s.html. Для подобного велосипедостроения очень рекомендую.


    Прочитал... Очень разочарован... Описан по сути простой shared_ptr со всеми его проблемами и сделана извращённая реализация. Чего-то полезного не нашёл
    Нужно разобрать угил.
     
    Подождите ...
    Wait...
    Пока на собственное сообщение не было ответов, его можно удалить.