Порядок создания и удаления в графе
От: SuhanovSergey  
Дата: 27.12.19 16:18
Оценка:
Порядок создания и удаления в графе

Между объектами есть отношение зависимости. A зависит от B. B должен быть создан до A и жить дольше A. A имеет ссылку на B, возможно отягощённую владением. Граф зависимости всех объектов формирует DAG.

Вопрос, как организовать код так, чтобы компилятор проверял, что объекты создаются в топологическом порядке, и удаляются соотвественно в обратном, так что никто никогда не имеет протухших ссылок?

Желательно зависимость выражать как аргумент конструктора. Порядок созданния внутри одного скопа выражается естественным образом

struct A {
    A(unique_ptr<B> b, unique_ptr<C> c): c_(move(c)), b_(move(b)) {}
    unique_ptr<C> c_;
    unique_ptr<B> b_;
}

struct B {
    B(C* c): c_(c) {}
    C* c_;
}

auto c = make_unique<C>();
auto b = make_unique<B>(c.get());
auto a = make_unique<A>(move(b), move(c));


Но порядок удаления легко поломать поменяв порядок членов в A.

Подсчёт ссылок (shared_ptr) решил бы проблему. Но он привносит другие проблемы, и по ряду причин переписывание на shared_ptr не является опцией.
Нужно чтобы зависимости приходили классам снаружи, ибо DI.
Re: Порядок создания и удаления в графе
От: rg45 СССР  
Дата: 27.12.19 22:38
Оценка: 1 (1)
Здравствуйте, SuhanovSergey, Вы писали:

SS>Между объектами есть отношение зависимости. A зависит от B. B должен быть создан до A и жить дольше A. A имеет ссылку на B, возможно отягощённую владением. Граф зависимости всех объектов формирует DAG.


SS>Вопрос, как организовать код так, чтобы компилятор проверял, что объекты создаются в топологическом порядке, и удаляются соотвественно в обратном, так что никто никогда не имеет протухших ссылок?


SS>Желательно зависимость выражать как аргумент конструктора. Порядок созданния внутри одного скопа выражается естественным образом

  ccode
SS>
SS>struct A {
SS>    A(unique_ptr<B> b, unique_ptr<C> c): c_(move(c)), b_(move(b)) {}
SS>    unique_ptr<C> c_;
SS>    unique_ptr<B> b_;
SS>}

SS>struct B {
SS>    B(C* c): c_(c) {}
SS>    C* c_;
SS>}

SS>auto c = make_unique<C>();
SS>auto b = make_unique<B>(c.get());
SS>auto a = make_unique<A>(move(b), move(c));
SS>


SS>Но порядок удаления легко поломать поменяв порядок членов в A.


Я что-то не совсем понял, зависимость между какими объектами мы рассматриваем. Начинал ты с A и В, потом перешел на B и C.

Хотя, лично я не вижу проблемы ни там, ни там. Правильная последовательность создания/удаления A и B обеспечивается конструктором и деструктором класса A и монопольным владением. От изменения порядка членов b_ и c_ также ничего страшного произойти не должно. Ведь B не владеет C, а значит и в деструкоре у него, по идее, не должно возникать никакого интереса, жив ли еще C или уже нет.

Ну а вообще, зависимости между объектами, конечно же, существуют на практике и правильная последовательность создания/удаления обычно достигается продуманным дизайном объектной модели.
--
Отредактировано 27.12.2019 22:42 rg45 . Предыдущая версия .
Re: Порядок создания и удаления в графе
От: sergii.p  
Дата: 28.12.19 07:32
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>
SS>struct A {
SS>    A(unique_ptr<B> b, unique_ptr<C> c): c_(move(c)), b_(move(b)) {}
SS>    unique_ptr<C> c_;
SS>    unique_ptr<B> b_;
SS>}

SS>struct B {
SS>    B(C* c): c_(c) {}
SS>    C* c_;
SS>}

SS>auto c = make_unique<C>();
SS>auto b = make_unique<B>(c.get());
SS>auto a = make_unique<A>(move(b), move(c));
SS>


SS>Но порядок удаления легко поломать поменяв порядок членов в A.


на данном конкретном примере я бы сделал так, что B владеет C, а А получает доступ к С через B, но не управляет его временем жизни.
В более общем случае, наверное, универсального рецепта нет.
Re: Порядок создания и удаления в графе
От: Слава  
Дата: 28.12.19 08:49
Оценка: -1 :))
Здравствуйте, SuhanovSergey, Вы писали:

SS>Порядок создания и удаления в графе


Перепишите на Rust.
Re: Порядок создания и удаления в графе
От: RedApe Беларусь  
Дата: 30.12.19 06:58
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>
SS>auto c = make_unique<C>();
SS>auto b = make_unique<B>(c.get());
SS>auto a = make_unique<A>(move(b), move(c));
SS>


Т.е. типа указатель на C должен быть и у А, и у B, но удаляться он должен только после того, как удалён А?

Ну тогда, наверное, разделить стоит передачу указателей и передачу владения.

Может быть, какой-нибудь set_parent сделать, по аналогии с QObject::SetParent из Qt.

И работать не с unique_ptr, а с голыми указателями.

auto c = new C;
auto b = new B(c);
auto a = new A(b,c);
b->set_parent(a);
c->set_parent(a);


А если хочется автоматизма, то колдовать придётся в конструкторах.
--
RedApe
Отредактировано 30.12.2019 7:55 RedApe . Предыдущая версия .
Re: Порядок создания и удаления в графе
От: AleksandrN Россия  
Дата: 30.12.19 09:01
Оценка: +1
Здравствуйте, SuhanovSergey, Вы писали:

SS>Между объектами есть отношение зависимости. A зависит от B. B должен быть создан до A и жить дольше A. A имеет ссылку на B, возможно отягощённую владением. Граф зависимости всех объектов формирует DAG.


SS>Вопрос, как организовать код так, чтобы компилятор проверял, что объекты создаются в топологическом порядке, и удаляются соотвественно в обратном, так что никто никогда не имеет протухших ссылок?



Cделай класс, задающий граф в виде матрицы и владеющий всеми объектами графа.
Указатели на объекты храни в векторе.
В матрице связей храни индексы объектов.
Создание и удаление объектов и работу с ними делай через эту обёртку.


SS>Подсчёт ссылок (shared_ptr) решил бы проблему. Но он привносит другие проблемы, и по ряду причин переписывание на shared_ptr не является опцией.

SS>Нужно чтобы зависимости приходили классам снаружи, ибо DI.

А shared_ptr + weak_ptr может решить проблему?
Re: Порядок создания и удаления в графе (StackAllocator)
От: Erop Россия  
Дата: 31.12.19 12:24
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>Подсчёт ссылок (shared_ptr) решил бы проблему. Но он привносит другие проблемы, и по ряду причин переписывание на shared_ptr не является опцией.

SS>Нужно чтобы зависимости приходили классам снаружи, ибо DI.

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

Например, у меня есть какой-то граф объектов. Скажем дерево перебора игры из позиций и всяких гипотез и стратегий, и наборов ходов, ассоциированных с ними.
Когда я или противник делаем ход, надо профильтровать это дерево, оставив в нём только то, что ещё актуально.
Ну я фильтрую это всё простым обходом, помещая объекты в очередь на удаление. А потом удаляю всю очередь.
Можно, кстати, ещё обойти перед этим дерево и вымарать из множества все те объекты, которые ещё нужны.
При этом, конкретно в вопросе фильтрации, можно удалять то, что ещё нужно, во время возвратов в рекурсивном обходе, то есть с O(1) оверхедом...
Это будет работать примерно так же, как GC, только без тормозов.

Или, раз уж речь идёт о DI и каком-то внешнем создании объектов и имущества. Можно в том же менеджере объектов, который их создаёт, регистрировать связи между объектами. И им же и решать, что и когда удалять.

Но у меня сложилось впечатление, что речь идёт о таком паттерне, что у нас есть какой-то стек. То есть идёт, например, рекурсивный перебор гипотез, мы по ходу пьесы, создаём какие-то объекты, причём внешним по отношению к объектам и перебору менеджером, и что-то там такое делаем, а потом откатываемся по стеку, и всё разрушаем, что насоздавали.
Кроме, быть может, каких-то избранных, которые мы возвращаем из перебора наверх или куда-то во внешний объект сливаем.
Тогда их можно складывать в список-стек, и при откате стек чистить. А если хотим разрушение объекта отложить, вынимать объект из этого стека или перекладывать подальше (например сразу после объекта, которому мы передали имущество.

Кстати, если объекты такие, что ничем не владеют, и наверх отдаются редко, то можно аллокировать их на особом отдельном стековом аллокаторе, а если объект надо вернуть, то копировать объекты на другой аллокатор. И при рекурсивном откате, можно просто отматывать аллокатор к соответствующему состоянию.
Будет работать очень быстро и просто.

---------------------------
p. s.
Если опустить всякие нудные подробности, вроде выравнивания, ограничения общего объёма аллокаций, подсчёта уже аллокированной памяти и степени фрагментации, то я имею в виду что-то вроде:
#include <iostream>
#include <list>
#include <assert.h>
using namespace std;

template<size_t TChunkSize=1024*1024, typename TItem=void> class StackAllocator;
template<size_t TChunkSize, typename TItem> class StackAllocator {
    class Chunk {
        TItem data[TChunkSize];
        TItem* cur;
        const TItem* end() const { return this->data+TChunkSize; }
    public:
        size_t UsedSize() const { return this->cur - this->data; }
        size_t FreeSize() const { return this->end() - this->cur; }        
        TItem* Alloc( size_t sz ) {
            if( sz > this->FreeSize() ) {
                return 0;
            }
            TItem* res = this->cur;
            this->cur += sz;
            assert( this->cur <= this->end() );
            return res;
        }
        void setAllocatedSize( size_t new_allocated_size ) {
            assert( new_allocated_size <= TChunkSize );
            this->cur = this->data + new_allocated_size;
        }
    };
    typedef std::list<Chunk> TChunks;
    typedef typename TChunks::iterator TChunksItr;
    TChunks chunks; 
    TChunksItr cur_chunk;
    
    void get_free_chunk() {
        TChunksItr next = this->cur_chunk;
        if( this->cur_chunk == this->chunks.end() || ++next == this->chunks.end() ) {
            this->chunks.emplace_back();
            next == this->chunks.end();
            --next;
        }
        assert( this->chunks.end() != next );
        this->cur_chunk = next;
        next->setAllocatedSize( 0 );
    }
    TChunksItr find_chunk(const Chunk* chunkPtr ) {
        for( typename std::list<Chunk>::reverse_iterator cur = this->chunks.rbegin();
                cur != this->chunks.rend(); ++cur ){
            if( &*cur == chunkPtr ) {
                TChunksItr res = cur.base();
                return --res;
            }
        }
        return this->chunks.end();
    }
public :
    struct State {
        const Chunk* chunkPtr;
        size_t usedSize;
        
        // Число, полезное для отладки. Обычно в рамках одной сессии программы оно 
        // однозначно соответствует состоянию аллокатора.
        intptr_t debug_int() const { return this->usedSize + (intptr_t)this->chunkPtr; }
    };

    StackAllocator() { 
        this->cur_chunk = this->chunks.end();
        this->get_free_chunk(); 
    }
    TItem* Alloc( size_t sz ) {
        assert( sz <= TChunkSize );
        TItem* res = this->cur_chunk->Alloc( sz );
        if( res == 0 ) {
            this->get_free_chunk();
            res = this->cur_chunk->Alloc( sz );
        }
        assert( res != 0 );
        return res;
    }
    bool IsValidState( const State& st ) const {
        TChunksItr pos = const_cast<StackAllocator*>(this)->find_chunk( st.chunkPtr );
        return pos != this->chunks.end() && st.usedSize <= pos->UsedSize();
    }
    State GetState() const {
        State res = { &*this->cur_chunk, this->cur_chunk->UsedSize() };
        return res;
    }
    void Rewind( const State& st ) {
        TChunksItr pos = this->find_chunk( st.chunkPtr );
        assert( pos != this->chunks.end() && st.usedSize <= pos->UsedSize() ); 
        pos->setAllocatedSize(st.usedSize);
        this->cur_chunk = pos;
    }
    
//private:
    template<typename TCompatibleItem> class compatibleAllocator {
        typedef StackAllocator<TChunkSize, TItem> TAllocator;
        TAllocator allocator;
    public:    
        typedef TAllocator::State State;
        TCompatibleItem* Alloc( size_t sz ) 
            { return static_cast<TCompatibleItem*>( this->allocator.Alloc( sz )); }
        State GetState() const { return this->allocator.GetState(); }
        void Rewind( State st ) { this->allocator.Rewind( st ); }
    };
};

template<size_t TChunkSize, typename TItem> 
    class StackAllocator<TChunkSize, const TItem> : 
        public StackAllocator<TChunkSize, TItem>::template compatibleAllocator<const TItem> {};

template<size_t TChunkSize, typename TItem> 
    class StackAllocator<TChunkSize, volatile TItem> : 
        public StackAllocator<TChunkSize, TItem>::template compatibleAllocator<volatile TItem> {};

template<size_t TChunkSize, typename TItem> 
    class StackAllocator<TChunkSize, const volatile TItem> : 
        public StackAllocator<TChunkSize, TItem>::template compatibleAllocator<const volatile TItem> {};

template<size_t TChunkSize> 
    class StackAllocator<TChunkSize, void> : 
        public StackAllocator<TChunkSize, char>::template compatibleAllocator<void> {};

/////////////////////////////////////////////////////////////
// TEST IT
////////////////////////////////////////////////////////////

StackAllocator<500, char> a;
void test_it( int n, int max_n=5 ) {
    if( n <= 0 ) {
        return;
    }
    std::string title( std::max(max_n-n, 0), '\t' );
    std::cout << title << "n:" << n << "+State:" << (size_t)a.GetState().debug_int() << std::endl;
    StackAllocator<500>::State st = a.GetState();
    
    // Тут что-то рекурсивно аллокируем:
    for( int i = 0; i < 5; i++ ) {
        a.Alloc(64);
        test_it( n-1, max_n );
        a.Alloc(64);
    }
    // Теперь отматываем стек, как было, тем самым освобождая всё аллокированное
    a.Rewind( st );
    std::cout << title << "n:" << n << "-State:" << (size_t)a.GetState().debug_int() << std::endl;
}

int main() {
    test_it( 3 );
    // your code goes here
    return 0;
}
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Отредактировано 31.12.2019 14:53 Erop . Предыдущая версия .
Re[2]: Порядок создания и удаления в графе (StackAllocator)
От: SuhanovSergey  
Дата: 02.01.20 12:28
Оценка:
> Ведь B не владеет C, а значит и в деструкоре у него, по идее, не должно возникать никакого интереса, жив ли еще C или уже нет.

В общем случае интерес есть. В общем-то, это и есть основная проблема.

> ... правильная последовательность создания/удаления обычно достигается продуманным дизайном объектной модели


Что подразумевается под продуманным дизайном?
Сейчас по факту, продуманность заключется в том, что некоторые объекты (A) "знают" о зависимостях других (B->C). В реальном большом графе это проблема дизайна, так как класс, типа A, вынужден знать о зависимостях других классов, о которых он и слышать не слышал. Хотелось бы иметь некие локальные принципы, чтобы класс знал только о публичных контрактах своих непосредственных зависимостей, но не их детали реализации, включая транзитивные зависимости.


> на данном конкретном примере я бы сделал так, что B владеет C, а А получает доступ к С через B, но не управляет его временем жизни.


В этом примере зависимость B->C является деталью реализации B. "Предоставлять доступ к C" не является частью публичного контракта B.

> Может быть, какой-нибудь set_parent сделать, по аналогии с QObject::SetParent из Qt.


Пока не понятно, как это отличается от построения дерева владения с unique_ptr.
QObject с setParent()/children() формирует дерево, в котором всё очевидно. Имеет ли Qt решение для ситуации, когда нужен DAG, т.е. когда siblings ссылаются друг на друга без циклов?


> Cделай класс, задающий граф в виде матрицы и владеющий всеми объектами графа.


Ок, т.е. предлагается повторить знание о всех зависимостях в одном месте, и делегировать ему создание/удаление. Это подход, наверное, можно назвать custom DI framework.


> А shared_ptr + weak_ptr может решить проблему?

Для этой задачи weak_ptr не нужен, подсчёта ссылок достаточно.
Но корпоративные стандарты не рекомендуют совместное владение, если можно обойтись уникальным владением. Я в общем соглашаюсь с этой рекомендацией.

> ... Вместо того, что бы тратить время на разборки с тем, кого за кем удалять, я просто всё, что хочу удалить, помещаю в множество владеющих указателей (hash_map указателей). А в какой-то момент операции, когда я уверен, что множество конситентное, грохать всё множество скопом?


Ок, это решение предполагает передачу некоего контекста, которому можно передать владение на объекты и который их убъёт в конце некой транзакции. Во время удаления объекты не могут обращаться друг к другу.
Кажется, это чуть более общий подход, чем двухфазное удаление, когда мы сначала my_root_object->Dispose(), а потом my_root_object.reset().

> Но у меня сложилось впечатление, что речь идёт о таком паттерне, что у нас есть какой-то стек.


Какой-то особый паттерн не имелся в виду. Просто граф объектов, который по идее есть в любой программе в том или ином виде.

Ок, ещё одно решение, если я правильно понял, предлагает как-то запоминать порядок создания (который форсится во время компиляции декларацией зависимостей аргументами конструкторов), а потом проигрывать его в обратном порядке для удаления.
Re[3]: Порядок создания и удаления в графе (StackAllocator)
От: rg45 СССР  
Дата: 02.01.20 17:17
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

>> Ведь B не владеет C, а значит и в деструкоре у него, по идее, не должно возникать никакого интереса, жив ли еще C или уже нет.

SS>В общем случае интерес есть. В общем-то, это и есть основная проблема.

SS>Что подразумевается под продуманным дизайном?


Это такой дизайн, при котором не возникают странные зависимости, вроде той, что между В и C в твоем примере. Ни владение, ни знание, а не пойми что.
--
Re[4]: Порядок создания и удаления в графе (StackAllocator)
От: SuhanovSergey  
Дата: 02.01.20 20:02
Оценка:
Здравствуйте, rg45, Вы писали:

R>Здравствуйте, SuhanovSergey, Вы писали:


>>> Ведь B не владеет C, а значит и в деструкоре у него, по идее, не должно возникать никакого интереса, жив ли еще C или уже нет.

SS>>В общем случае интерес есть. В общем-то, это и есть основная проблема.

SS>>Что подразумевается под продуманным дизайном?


R>Это такой дизайн, при котором не возникают странные зависимости, вроде той, что между В и C в твоем примере. Ни владение, ни знание, а не пойми что.



Между В и C зависимость как раз типа "знание", без владения, например как между lock_guard и mutex.

Не могли бы вы общих чертах описать, как же всё таки делать продуманный дизайн системы с DI?
Re[5]: Порядок создания и удаления в графе (StackAllocator)
От: rg45 СССР  
Дата: 02.01.20 21:38
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

R>>Это такой дизайн, при котором не возникают странные зависимости, вроде той, что между В и C в твоем примере. Ни владение, ни знание, а не пойми что.


SS>Между В и C зависимость как раз типа "знание", без владения, например как между lock_guard и mutex.


Если В нельзя удалить, игнорируя время жизни C, то это уже не просто знание. Но и не владение. А, вот именно, не пойми что. Для таких случаев есть weak_ptr и aware_ptr. Но когда их в объекной модели слишком много, это уже само по себе симптоматично. Своего рода индикаторы паразитных зависимостей.

SS>Не могли бы вы общих чертах описать, как же всё таки делать продуманный дизайн системы с DI?


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

P.S. Часто при проектировании сложных систем оказывается востребованной инверсия зависимостей (тоже DI, только inversion). Спосбов имплементации в современном C++ вагон и маленькая тележка — это и классические абстракиные интерфейсы, и сигналы, и коллбеки, теперь вот и лямбды еще. Умелое сочетание динамического полиморфизма со статическим также способно дать выигрыш.
--
Отредактировано 02.01.2020 22:06 rg45 . Предыдущая версия . Еще …
Отредактировано 02.01.2020 21:51 rg45 . Предыдущая версия .
Отредактировано 02.01.2020 21:49 rg45 . Предыдущая версия .
Отредактировано 02.01.2020 21:48 rg45 . Предыдущая версия .
Отредактировано 02.01.2020 21:42 rg45 . Предыдущая версия .
Re[6]: Порядок создания и удаления в графе (StackAllocator)
От: SuhanovSergey  
Дата: 03.01.20 16:52
Оценка:
Здравствуйте, rg45, Вы писали:

R>Здравствуйте, SuhanovSergey, Вы писали:


R>>>Это такой дизайн, при котором не возникают странные зависимости, вроде той, что между В и C в твоем примере. Ни владение, ни знание, а не пойми что.


SS>>Между В и C зависимость как раз типа "знание", без владения, например как между lock_guard и mutex.


R>Если В нельзя удалить, игнорируя время жизни C, то это уже не просто знание. Но и не владение. А, вот именно, не пойми что. Для таких случаев есть weak_ptr и aware_ptr. Но когда их в объекной модели слишком много, это уже само по себе симптоматично. Своего рода индикаторы паразитных зависимостей.


SS>>Не могли бы вы общих чертах описать, как же всё таки делать продуманный дизайн системы с DI?


R>В общих чертах я уже сказал — завсимости между классами должны быть четкими, ясными и минимальными. Но без фанатизма. Иногда бывает дешевле смириться с лишней зависимостью, чем устранить ее. Это хоть с DI, хоть без. Большей конкретики, для общего случая, я дать не смогу.


R>P.S. Часто при проектировании сложных систем оказывается востребованной инверсия зависимостей (тоже DI, только inversion). Спосбов имплементации в современном C++ вагон и маленькая тележка — это и классические абстракиные интерфейсы, и сигналы, и коллбеки, теперь вот и лямбды еще. Умелое сочетание динамического полиморфизма со статическим также способно дать выигрыш.


Ок, значит, ваше решение — совместное владение aka подсчёт ссылок aka shared_ptr+weak_ptr.

Кстати, как я уже говорил в другом коментарии, в решении с совместным владением weak_ptr не требуется в B. По условию, C должен жить дольше B.

Всё же, дизайн, когда некий класс (B) принимает ссылку/указатель на зависимость (C), предполагая, что создатель гарантирует время жизни C дольше чем B, это вполне себе идиоматичный C++, а не "не пойми что". Из стандартного, примеры могут быть string_view, lock_guard, function. Рассмотренный изолированно, B не делает ничего противозаконного. Если B приходит из некой библиотеки, то авторов библиотеки не в чем обвинить.

Подсчёт ссылок перекладывает решение о том, когда удалять, в рантайм. Иногда это единственно возможное решение. Но поинт осходной задачи в том, что известно, что решение без подсчёта существует. Наверное, можно даже утверждать, что большинство практических задач имеет решение без подсчёта ссылок, но это уже другой разговор.
Хотелось бы иметь набор локальных правил, следуя которым можно разрабатывать части, типа A, B, C, которые потом можно комбинировать и масштабировать систему. При этом хочеться не навязывать совместное владение.

Совместное владение не рекомендуется правилами моей компании. Собственно, они частично публичны — https://google.github.io/styleguide/cppguide.html#Ownership_and_Smart_Pointers. От себя добавлю, что подсчёт ссылок расслабляет, и он заразен. Когда он масштабируется на достаточно большую часть системы, он делает её недетерминированной, как со сборкой мусора, и более сложной для анализа. Система без совместного владения более строгая, позволяет меньше, но не прощает ошибок, и крэшится рашьне.
Re[7]: Порядок создания и удаления в графе (StackAllocator)
От: rg45 СССР  
Дата: 03.01.20 16:57
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:


SS>Ок, значит, ваше решение — совместное владение aka подсчёт ссылок aka shared_ptr+weak_ptr.


Ну не настолько все прямолинейно. Арсенал подходов к проектированию велик. В каждом отдельном случае нужно смотреть отдельно. В этом, собственно, и заключается процесс продумывания дизайна.
--
Re[6]: [offtop] aware_ptr?
От: Alexey F  
Дата: 03.01.20 20:04
Оценка:
Здравствуйте, rg45, Вы писали:

R>Если В нельзя удалить, игнорируя время жизни C, то это уже не просто знание. Но и не владение. А, вот именно, не пойми что. Для таких случаев есть weak_ptr и aware_ptr. Но когда их в объекной модели слишком много, это уже само по себе симптоматично. Своего рода индикаторы паразитных зависимостей.

А что такое aware_ptr и с чем его едят? Поиск выплёвывает только твой старый пост
Автор: rg45
Дата: 19.10.10
с коротким описанием
Re[7]: [offtop] aware_ptr?
От: rg45 СССР  
Дата: 03.01.20 20:54
Оценка: 2 (1) +1
Здравствуйте, Alexey F, Вы писали:

AF>А что такое aware_ptr и с чем его едят? Поиск выплёвывает только твой старый пост
Автор: rg45
Дата: 19.10.10
с коротким описанием


Да я сам удивляюсь, что не находится ничего. Мне его уже несколько раз приходилось имплементить за мою карьеру. Ну не сам же я его придумал! Полезная штуковина. Это чудо-указатель — мечта всех идиотов — "обнуляется" автоматически, при окончании времени жизни объекта. Концептуально близок к weak_ptr, но с тем отличием, что никак не привязан ни к shared_ptr, ни к какому другому умному указателю. Вообще не накладывает ни каких ограничений ни на область памяти, в которой размещается объект, ни на способ владения. Это запросто может быть объект, расположенный в куче, с владением через любой из умных указателей, подобъект другого объекта (член), или просто локальный объект в скопе функции или блока. Недостаток один — имплементация интрузивная (другой я не придумал).


P.S. Я пошарил по закоулкам памяти, а ведь действительно, aware_ptr мог быть нашим локальным изобретением. Ведь самую первую имплементацию aware_ptr я с делал еще в те времена, когда сам термин "smart pointer" был еще новым и прогрессивным. Очень может быть, что один из моих коллег просто попутал слова "smart" и "aware". Ну а потом объяснил так, как понимал. Ну а я в свою очередь заимплементил так, как понял его. Впрочем, я не уверен, что все было именно так. Давненько это было, год эдак 98-й, наверное.
--
Отредактировано 03.01.2020 21:29 rg45 . Предыдущая версия .
Re: Порядок создания и удаления в графе
От: SuhanovSergey  
Дата: 21.01.20 21:13
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>Порядок создания и удаления в графе


Попробовал разные опции. Обнаружил, что другие команды в компании сталкивались с теми же проблемами и изобрели легковесный DI framework для решения. Вполне вероятно полноценные публичные framework-и тоже решают это проблему. Для своего случая никакой framework использовать не буду. Его работа легко делается вручную.
Идея в том, что в бизнес-классах нужно предпочитать получать зависимости по голому указателю/ссылке, предполагая, что создатель гарантирует время жизни зависимости дольше, чем время жизни создаваемого объекта. В некоторых ситуациях класс может получать зависимость с владением (по unique_ptr), если эта зависимость является неотъемлемой частью класса, на которую никто больше не ссылается. Например, если некий класс A слишком распух, и их него вынесли часть ответсвенности в B, и A нужно знать о B, но никто другой о B не знает, то A может принять unique_ptr<B>.

Далее, место в программе, которое всё создаёт (aka composition root https://stackoverflow.com/questions/6277771/what-is-a-composition-root-in-the-context-of-dependency-injection), создаёт объекты в топологическом порядке DAG-а зависимостей, складывает в некий контейнер, который объектами владеет и удаляет в обратном порядке.

При использовании DI framework-а определение порядка и генерация этого контейнера автоматизировано. Если делать руками, то можно объявить класс контейнера, владеемые объекты положить в поля, создавать всё в списке инициализации. Исходный пример будет

class Container {
    unique_ptr<C> c;
    unique_ptr<B> b;
    unique_ptr<A> a;
    Container():
        c(make_unique<C>()),
        b(make_unique<B>(c.get())),
        a(make_unique<A>(b.get(), c.get()))
    {}
}


Порядок создания определяется порядком полей. Порядок полей — топологический и проверяется компилятором. Если поменять поля местами, компилятор выдаст, например, "field 'b' is uninitialized when used here [-Wuninitialized]" при попытке передать b.get() как зависимость другому объекту. В нашем toolchain-е эта warning всегда включена и is treated as error.

Одна проблема, что теперь этот Container нужно кому-то удалять. Если всё происходит в main(), то нет проблем. Но если это некая библиотека, и раньше можно было отдать A наружу как точку входа в объектную модель, то теперь это не так просто. В моём случае точка входа уже отдаётся как shared_ptr, и shared_ptr удобно имеет aliasing constructor. Т.е. можно сказать, хей shared_ptr<A>, раздавай указатель p1 (&container->a), но когда нужно удалить, удаляй p2 (container). С unique_ptr<A> такое не прокатит https://stackoverflow.com/questions/34668918/why-doesnt-stdunique-ptr-have-an-aliasing-constructor-like-stdshared-ptr-ha. Можно отдавать unique_ptr<A, A_CustomeDeleter>. Наверное, можно что-то ещё придумать.
Re[8]: [offtop] aware_ptr?
От: SuhanovSergey  
Дата: 21.01.20 21:30
Оценка:
Здравствуйте, rg45, Вы писали:

R>Здравствуйте, Alexey F, Вы писали:


AF>>А что такое aware_ptr и с чем его едят? Поиск выплёвывает только твой старый пост
Автор: rg45
Дата: 19.10.10
с коротким описанием


R>Да я сам удивляюсь, что не находится ничего. Мне его уже несколько раз приходилось имплементить за мою карьеру. Ну не сам же я его придумал! Полезная штуковина. Это чудо-указатель — мечта всех идиотов — "обнуляется" автоматически, при окончании времени жизни объекта.


А какой run-time cost обнуления у вас? O(1) или пропорционально количеству инстансов aware_ptr? Какие требования по многопоточности?

Вот версия от chromium: https://chromium.googlesource.com/chromium/src/+/master/base/memory/weak_ptr.h
Re[9]: [offtop] aware_ptr?
От: rg45 СССР  
Дата: 21.01.20 21:42
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

SS>А какой run-time cost обнуления у вас? O(1) или пропорционально количеству инстансов aware_ptr? Какие требования по многопоточности?


Сдожность О(1). Потокобозопасность, в последнем варианте, выделена в стратегию. В качестве стратегии по умолчанию используется однопоточная стратегия (потоко-небезопасная).
--
Re[8]: [offtop] aware_ptr?
От: B0FEE664  
Дата: 22.01.20 13:24
Оценка:
Здравствуйте, rg45, Вы писали:

AF>>А что такое aware_ptr и с чем его едят? Поиск выплёвывает только твой старый пост
Автор: rg45
Дата: 19.10.10
с коротким описанием

R> Давненько это было, год эдак 98-й, наверное.

В 98-ом я писал аналогичный указатель, только называл его MirrorPtr.
И каждый день — без права на ошибку...
Re[9]: [offtop] aware_ptr?
От: rg45 СССР  
Дата: 22.01.20 13:26
Оценка: :)
Здравствуйте, B0FEE664, Вы писали:

BFE>В 98-ом я писал аналогичный указатель, только называл его MirrorPtr.


А почему "mirror"? Чтоб никто не догадался?
--
Re[10]: [offtop] aware_ptr?
От: B0FEE664  
Дата: 22.01.20 14:10
Оценка:
Здравствуйте, rg45, Вы писали:

BFE>>В 98-ом я писал аналогичный указатель, только называл его MirrorPtr.

R>А почему "mirror"? Чтоб никто не догадался?
(точнее TMirrorPtr)
Потому, что это указатель на зеркало объекта. А вот зеркало объекта, TMirrorObj, хранило указатель на сам объект.
Если не станет объекта, то и в зеркале его видно не будет. Вот такое вот образное название. Я хотел назвать его TProxyPtr, но такой класс уже был для кэширования задействован (ЕМНИП).

В современных стандартных классах это, наверное, что-то вроде конструкции:
std::shared_ptr< std::weak_ptr<T> >


Только ключевой момент был в переопределении оператра ->
// Не указатель!
TMirrorObj& MirrorPtr::operator ->()
{
  assert(NULL != pointer_to_MirrorObj);
  return *pointer_to_MirrorObj;
}

T* TMirrorObj::operator ->()
{
  assert(NULL != pointer_to_object);
  return pointer_to_object;
}
И каждый день — без права на ошибку...
Re[11]: [offtop] aware_ptr?
От: rg45 СССР  
Дата: 22.01.20 14:16
Оценка:
Здравствуйте, B0FEE664, Вы писали:

R>>А почему "mirror"? Чтоб никто не догадался?

BFE>(точнее TMirrorPtr)
BFE>Потому, что это указатель на зеркало объекта. А вот зеркало объекта, TMirrorObj, хранило указатель на сам объект.

Да я догадался У меня то же самое практически, здесь простор для креатива не так велик. Но все же, это деталь реализации, а не главная функциональность, предоставляемая умным указателем. Класть деталь реализации в основу имени не есть хорошо, имхо. Хотя, для 90-х вполне простительно.
--
Re[12]: [offtop] aware_ptr?
От: B0FEE664  
Дата: 22.01.20 14:29
Оценка:
Здравствуйте, rg45, Вы писали:

R>>>А почему "mirror"? Чтоб никто не догадался?

BFE>>Потому, что это указатель на зеркало объекта. А вот зеркало объекта, TMirrorObj, хранило указатель на сам объект.
R>Да я догадался

Вот! Значит можно догадаться. Не то что с weak_ptr. Вот если есть weak_ptr, значит где-то должен быть strong_ptr! Но нет.
И каждый день — без права на ошибку...
Re[13]: [offtop] aware_ptr?
От: rg45 СССР  
Дата: 22.01.20 14:29
Оценка:
Здравствуйте, B0FEE664, Вы писали:

R>>Да я догадался


BFE>Вот! Значит можно догадаться. Не то что с weak_ptr. Вот если есть weak_ptr, значит где-то должен быть strong_ptr! Но нет.


Я — плохой ориентир
--
Re[2]: Порядок создания и удаления в графе (StackAllocator)
От: Mr.Delphist  
Дата: 23.01.20 11:56
Оценка:
Здравствуйте, Erop, Вы писали:


E>Но у меня сложилось впечатление, что речь идёт о таком паттерне, что у нас есть какой-то стек.


Не-не, тут в общем случае не стек, а дерево, т.к. левая и правая ветви могут создаваться независимо друг от друга. В случае со стеком у нас получится, что ветви должны удаляться в порядке, обратном созданию, что далеко не всегда будет верно семантически.
Re[3]: Порядок создания и удаления в графе (StackAllocator)
От: Erop Россия  
Дата: 27.01.20 06:47
Оценка:
Здравствуйте, Mr.Delphist, Вы писали:

E>>Но у меня сложилось впечатление, что речь идёт о таком паттерне, что у нас есть какой-то стек.


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


Так обычно перебор дерева в глубину с откатами и откладываемыми на потом кандидатам и порождает стек. Мы в каждой вершине запоминаем state и ныряем по очереди в детей. Если находим где-то в листе, например, что-то перспективное, то
1) переносим этот вариант на другой аллокатор
2) Рассматриваем вариант, а не отсечься ли нам (просто сразу большое поддерево не рассматривать)

Например, мы строим какие-то гипотезы и рекурсивно (перебор дерева вглубь) их перебираем. Ну предположим что то, потом ещё это, потом ещё и вот-это и т. д.
И по пути мы строим список из 10 лучших найденных вариантов, например. И ещё в каждом узле имеем оценку насколько, относительно того, что в узле, лучший вариант можно построить.
Ну и как только находим вариант, который лучше, чем самый плохой в нашем списке, мы создаём копию его уже на куче, и заталкиваем в наш список. И, за одно можем подняться по нашему перебору куда-то вверх, если уже не осталось шансов построить за остаток перебора из этого узла вариант лучше худшего в списке лучших.
Тогда, соответственно отсекаем целое поддерево перебора...

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

Пока что мой, основанный в основном на телепатии, совет состоит в том, что бы пойти на некоторый размен. Увеличить степень фрагментации памяти алгоритмом (не всё сразу разрушать, а управлять сразу пачками объектов), а те немногие объекты, кто в эту схему не вписывается, переносить на другой аллокатор.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[2]: Порядок создания и удаления в графе
От: SuhanovSergey  
Дата: 31.01.20 13:29
Оценка:
Здравствуйте, Слава, Вы писали:

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


SS>>Порядок создания и удаления в графе


С>Перепишите на Rust.


Не могли бы вы показать как пример с A, B, C выглядел бы на rust? После прочтения https://doc.rust-lang.org/nomicon/lifetimes.html не очень понятно как это обобщается на граф.
Re[3]: Порядок создания и удаления в графе
От: Слава  
Дата: 31.01.20 16:10
Оценка:
Здравствуйте, SuhanovSergey, Вы писали:

С>>Перепишите на Rust.

SS>Не могли бы вы показать как пример с A, B, C выглядел бы на rust? После прочтения https://doc.rust-lang.org/nomicon/lifetimes.html не очень понятно как это обобщается на граф.

Перепишите на Rust — это такой мем. Извините.
На граф оно не отображается, только на дерево.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.