Информация об изменениях

Сообщение Re: Порядок создания и удаления в графе (StackAllocator) от 31.12.2019 12:24

Изменено 31.12.2019 14:53 Erop

Старый текст
Новый текст
Разница

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

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

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

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

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

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

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

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

Re: Порядок создания и удаления в графе (StackAllocator)

#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;
}