Benutzerdefinierter Allokator -> Absturz



  • Hallo,

    zwecks Performanceoptimierung benötige ich eine std::list mit einem benutzerdefinierten Allocator, der einen Memory-Pool verwaltet, damit nicht für jedes einzelne Element new/delete aufgerufen wird. Probiert habe ich sowohl eine eigene Implementation, als auch schon zwei Allokatoren mit demselben Zweck, die ich im Internet finden konnte (https://github.com/cacay/MemoryPool und https://github.com/moya-lang/Allocator). Die gewünschte Performanceverbesserung tritt auch tatsächlich ein, allerdings zeigen sich spätestens im Debugmodus Abstürze, die anscheinend davon kommen, dass die std::list<> nicht nur einen, sondern offenbar mehrere Allokatoren erzeugt (neben dem, den ich bei der Instanziierung übergebe) und wieder zerstört; wobei bei der Destruktion natürlich der Speicher auch freigegeben wird. Sowohl meine primitive Implementation, als auch die beiden anderen Implementation zeigen dasselbe Problem.

    Hier ein Verwendungsbeispiel für den allocator, dass zum Absturz führt (beim pop_back()):

    #include <list>
    #include <vector>
    #include <cstdlib>
    
    template <class T>
    class allocator
    {
    	size_t count = 0;
    	std::vector<T*> chunks;
    
    public:
    	using value_type = T;
    
    	allocator() noexcept {}
    	template <class U> allocator(allocator<U> const&) noexcept { }
    
    	~allocator() {
    		for (size_t i = 0; i < chunks.size(); i++)
    		{
    			char* buffer = (char*)chunks[i];
    			delete[] buffer;
    		}
    		chunks.clear();
    	}
    	value_type* allocate(std::size_t n)
    	{
    		if (n != 1)
    			throw std::bad_alloc();
    
    		size_t i = count;
    		count++;
    		if (count > chunks.size() * 1024)
    		{
    			chunks.push_back((value_type*) new char[sizeof(value_type) * 1024]);
    		}
    		return &chunks[i / 1024][i % 1024];
    	}
    
    	void deallocate(value_type* p, std::size_t) noexcept
    	{
    	}
    };
    
    int main()
    {
    	allocator<int> alloc;
    	std::list<int, allocator<int>> l(alloc);
    	l.push_back(1);
    	l.pop_back();
    	system("PAUSE");
    }
    

    Das gleiche Problem tritt, wie gesagt, auch bei Verwendung anderer Allokatoren auf (jedenfalls sofern diese statefull sind - ein Allokator, der wie std::allocator einfach nur new/delete für jedes Objekt macht, funktioniert). Hat jemand eine Idee, was da vor sich geht, bzw. was genau ich da falsch mache?


  • Mod

    Mr X schrieb:

    jedenfalls sofern diese statefull sind

    Das ist dein Hauptproblem (neben Anderen).

    N4727 herunterladen. Kapitel 20.5.3.5. lesen und vollständig implementieren.

    Kurzes Überfliegen der verlinkten Projekte zeigt, dass diese zumindest
    die Postcondition von
    X u(a);
    X u = a;
    verletzen:
    nämlich, dass ein durch a alloktierter Zeiger via u freigegeben werden kann - und zwar auch dann noch, falls a später zerstört wird.

    Das absturzverursachende Problem mit deinem Allokator bei diesem simplen Beispiel sehe ich nicht unmittelbar, allerdings reagiert dieser Allokator offensichtlich sehr allergisch auf Kopieraktionen.


  • Mod

    Man braucht doch gar nichts herunterzuladen. eel.is/c++draft! Edit: Die genannte section befindet sich hier: http://eel.is/c++draft/allocator.requirements


  • Mod

    int main()
    {
        using alloc_type = allocator<int>;
        using list_type = std::list<int, alloc_type>;
        alloc_type alloc;
        auto p = std::make_unique<list_type>(alloc);
        p->push_back(1);
        auto q = std::make_unique<list_type>(*p); // allocate and construct copied element using the copied allocator
        auto r = std::make_unique<list_type>();   // allocator might not be equal to others
        assert(p->get_allocator() == q->get_allocator());
        q->splice(q->end(), *p);
        p.release();
        r->swap(*q); // must swap allocator if allocator objects might not be equal 
                     // and alloc_type::propagate_on_container_swap must be true in that case
        q.release();
        r->pop_back(); // releases element through a copy of the original allocator, the latter having been destroyed already
        r->pop_back();
    }
    

    schaut beim Testen ein bisschen genauer hin.

    Kurz gefasst: das verlinkte Design, bei dem ein privater Pool ein direktes Element eines Allokators ist, kann nie die Allokatorvoraussetzungen des Standards erfüllen, weil Allokatorobjekte, die durch Copy-/Move entstehen, gleich sein müssen (i.S.d. operator==, d.h. Blöcke, die durch ein Allokatorobjekt allokiert wurden, durch ein beliebieges Anderes, Gleiches freigegeben werden können).
    Es wird entweder
    1. ein shared state zwischen äquivalenten Allokatorobjekten gebraucht, oder
    2. der Zustandsinformation eines Allokatorsobjekts muss leben, solange noch Blöcke existieren, die die durch dieses Allokatorobjekt allokiert wurden, und andere Allokatorobjekte müssen auf diese Information zugreifen können (globaler Manager o.ä.), oder,
    3. deallocate und der Destruktor des Allokators tun nichts.


  • Mod

    Kleine Ergänzung: Obiges ist der Grund dafür, dass alle Allokatoren, die bspw. von festgelegten Blöcken auf dem Stack allozieren, eine "Arena" verwenden, auf die die Allokatoren einen Verweis halten, und die selbst als automatisches Objekt deklariert wird.

    Edit: Siehe Howard Hinnant's short_alloc.h.


  • Mod

    Arcoth schrieb:

    Edit: Siehe Howard Hinnant's short_alloc.h.

    Mir scheint auch dieser Code muss noch am swap arbeiten (und move-Zuweisung).

    int main()
    {
        arena<1024> arena1, arena2;
        using alloc_type = short_alloc<int, 1024>;
        using list_type = std::list<int, alloc_type>;
        alloc_type alloc(arena1);
        auto p = std::make_unique<list_type>(alloc);
        p->push_back(1);
        auto q = std::make_unique<list_type>(*p);
        auto r = std::make_unique<list_type>(arena2);
        assert(p->get_allocator() == q->get_allocator());
        q->splice(q->end(), *p, p->begin(), p->end());
        p.release();
        r->swap(*q);
        q.release();
        r->pop_back();
        r->pop_back();
    }
    

    *** Error in `./a.out': free(): invalid pointer: 0x00007ffdbdae24c0 ***


  • Mod

    ... was einfach zu fixen ist:

    template <class T, std::size_t N, std::size_t Align = alignof(std::max_align_t)>
    class short_alloc
    {
    public:
        using value_type = T;
        static auto constexpr alignment = Align;
        static auto constexpr size = N;
        using arena_type = arena<size, alignment>;
    
    private:
        arena_type* a_;
    
    public:
        short_alloc(const short_alloc&) noexcept = default;
        short_alloc(short_alloc&&) noexcept = default;
        short_alloc& operator=(const short_alloc&) noexcept = default;
        short_alloc& operator=(short_alloc&&) noexcept = default;
    
        short_alloc(arena_type& a) noexcept : a_(&a)
        {
            static_assert(size % alignment == 0,
                          "size N needs to be a multiple of alignment Align");
        }
        template <class U>
            short_alloc(const short_alloc<U, N, alignment>& a) noexcept
                : a_(a.a_) {}
    
        template <class _Up> struct rebind {using other = short_alloc<_Up, N, alignment>;};
    
        T* allocate(std::size_t n)
        {
            return reinterpret_cast<T*>(a_->template allocate<alignof(T)>(n*sizeof(T)));
        }
        void deallocate(T* p, std::size_t n) noexcept
        {
            a_->deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
        }
    
        template <class T1, std::size_t N1, std::size_t A1, 
                  class U, std::size_t M, std::size_t A2>
        friend
        bool
        operator==(const short_alloc<T1, N1, A1>& x, const short_alloc<U, M, A2>& y) noexcept;
    
        template <class U, std::size_t M, std::size_t A> friend class short_alloc;
    
        using propagate_on_container_copy_assignment = std::false_type;
        using propagate_on_container_move_assignment = std::false_type;
        using propagate_on_container_swap = std::true_type;
    };
    
    template <class T, std::size_t N, std::size_t A1, class U, std::size_t M, std::size_t A2>
    inline
    bool
    operator==(const short_alloc<T, N, A1>& x, const short_alloc<U, M, A2>& y) noexcept
    {
        return N == M && A1 == A2 && x.a_ == y.a_;
    }
    

    propagate_on_container_copy_assignment ist nicht zwingend erforderlich. Allerdings würde es als Überraschend ansehen, wenn nach einer Zuweisung nicht zwischen Orginal und Kopie hin und her gespliced werden kann.

    hm... andererseits:

    void f(list& out) {
        arena a; list_t x(a); // do something
        out = x;
    }
    void g() {
        arena b; list_t y(b);
        f(y);
    }
    

    ... Meinung dazu?


  • Mod

    Offensichtlich müssen sowohl move- als auch copy-assignments in die ursprüngliche Arena gemacht werden.

    Edit: splicen kann man doch immer. Das hängt nicht von den Arenen ab, in denen sich die Nodes befinden. Ob die Arenen übernommen werden sollen, ist eine Frage von Lebenszeiten.


  • Mod

    Arcoth schrieb:

    Offensichtlich müssen sowohl move- als auch copy-assignments in die ursprüngliche Arena gemacht werden.

    Stimmt, ich war in der Tabelle mit den Containerrequirements verrutscht.

    Arcoth schrieb:

    Edit: splicen kann man doch immer.

    Nicht ganz eel.is/c++draft/list.ops#2. Etwas anderes wäre mit der verlangten konstanten Komplexität und der Tatsache, dass Referenzen und Zeiger auf gesplicete Elemente gültig bleiben, auch nicht vereinbar.



  • Vielen Dank für eure Antworten!

    Dass der Pool nicht in der Allokatorklasse liegen darf, war mir so nicht bewusst, erscheint mir aber jetzt logisch. Habe das geändert, der Absturz in dem kleinen Beispiel ist damit behoben, und auch in meinem realen Beispiel funktioniert das Ding nun wunderbar. Im Ergebnis ist der Algorithmus, den es zu beschleunigen galt, jetzt mehr als doppelt so schnell.


Log in to reply