Allokatoren und die NUMA-Problematik



  • Wir hatten von einigen Tagen die Diskussion wie man möglichst sinnvoll im aktuellen C++ eine Matrixklasse implementiert. Es wurde wiederholt darauf verwiesen, dass man als LowLevel Speicher einen std::vector benutzen sollte. Das Problem hierbei war allerdings, dass der std::allocator der die Vorgabe für std::vector ist, die Speicherverwaltung auf NUMA Systemen nicht beherrscht. Wunderbarerweise unterstützt C++ seit C++2011 Allokatoren mit Zustand, so dass es im Prinzip möglich ist einen Allokator zu schreiben, der auch für die vorhandenen Container der Standard Library eine NUMA-Unterstützung implementiert. Leider finden sich im Netz oder der Standardliterator (z.B. Stroustrup) nur bedingt Hinweise wie man einen korrekten Allokator nicht trivialer Art zu implementieren hat bzw. die Beispiele aus Vorgängen weisen einige unschöne Fehler auf, die einem das Leben deutlich erschweren.

    Gesagt getan, ich hatte mich als in die Arbeit gestürzt und einen NUMA-Allokator implementiert. Dabei ist die ISO Norm auch keine wirkliche Hilfe, weil das angeblich ausreichende Beispiel aus der Norm nicht wirklich sinnvoll ist. Ich habe den Draft N4791 verwendet, der einige Abweichungen von der ISO Norm 2017 aufweist, trotzdem beziehe ich nachfolgend, wenn nicht anders erwähnt, auf diese Revision.

    Nachfolgend der Programmcode für den SimpleAllocator aus dem Draft N4791:

    template<class Tp>
    struct SimpleAllocator {
        typedef Tp value_type;
        SimpleAllocator(ctor args );
    
        template<class T> SimpleAllocator(const SimpleAllocator<T>& other);
    
        [[nodiscard]] Tp* allocate(std::size_t n);
        void deallocate(Tp* p, std::size_t n);
    };
    
    template<class T, class U>
    bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&);
    template<class T, class U>
    bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&);
    

    Wichtig ist N4791 Kapitel 15.5.3.5 Cpp17Allocator requirements, hier werden in Tabelle 34 die Anforderungen an einen Allokator definiert sowie die durch allocator_traits zur Verfügung gestellten Vorgaben benannt. Alle Klassen, die einen Allocator nutzen, werden gegen die allocator_traits entwickelt, d.h. insbesondere alle Containerklassen der Standard Library.

    Noch einmal zurück zur Motivation. Es ging darum, dass man Matrizen auf einem NUMA-System effizient speicher können sollte und mit ihnen maximal schnell rechen zu können. Das impliziert bei einem NUMA-System, dass man in der Lage ist den Speicherort bestimmen und kontrollieren zu können. Der Standardallokator fordert auf nicht näher bestimmte Art und Weise vom System Speicher an. Dank des üblichen Memory Overcommitments werden die Speicherseiten zuerst nicht physikalischen angelegt sondern nur rein virtuell. Beim ersten Schreiben auf diesen virtuellen Speicher werden dann physikalische Speicherseiten angelegt. Hier ist entscheidend von welchen Hardwarethread dies aus erfolgt. Dies entscheidet darüber auf welchem NUMA-Knoten der Speicher physikalisch angelegt wird. Unter anderem wegen dieser Problematik nutzt man beim HPC Thread Pinning, um die logischen Threads des Programm an physikalische Threads (Cores) zu binden.

    Interessant wird es nun, wenn man Container auf unterschiedlichen NUMA-Knoten hat. Die Empfehlung hier im Forum war es für Matrizen als rohen Speicher einen std::vector zu nutzen. Betrachten wir hier erstmal mit Pseudocode (der Rest der Klasse interessiert zuerst nicht) wie sich das Programm idealerweise verhalten sollte.

    template <typename T>
    class NUMA-Allocator  {
        int node_;
        …
    public:
        using value-type T;
        NUMA-Allocator (int node) : node_ {…}
        …
    };
    
    int main () {
        NUMA-Allocator<double> na(0), na1(1);
        std::vector<double,NUMA-Allocator> v1(100,0,na0), v2(100,0,na1);
    
        …
        v1 = v2;
        …
    }
    

    Das wirklich interessante findet in Zeile 15 statt. Was soll passieren bei der Kopierzuweisung in dieser Zeile?

    Natürlich soll anschließen in v1 die Daten aus v2 enthalten sein, aber entscheidend ist die Frage, wo die Daten wirklich liegen sollen: auf NUMA-Knoten 1 wie zuvor bei v2 oder auf NUMA-Knoten 0 sowie der Allokator na0 die Daten alloziert?

    Die allocator_traits erlauben dieses Verhalten mittels des Typedefs X::propagate_on_container_copy_assigment zu beeinflussen. Die allocator_traits definieren als Vorgabe std::false_type was in konkreten Fall des NUMA-Allocator zutreffend ist, aber in vielen anderen Fällen eben nicht. Deshalb ist das Beispiel eines Allokatoren aus der Norm unvollständig und unbrauchbar. Es gibt noch einige weitere Traits aus der betreffenden Klasse, die man sinnvoller Weise explizit definieren sollte. Damit ändert sich der Rumpf des NUMA-Allokatoren schon zu folgenden Code

    template <typename T>
    class NUMA-Allocator {
    	int node_;
    public:
    	using value_type 		= T;
    
    	using propagate_on_container_copy_assignment	= std::false_type;
    	using propagate_on_container_move_assignment	= std::false_type;
    	using propagate_on_container_swap		= std::false_type;
    	using is_always_equal				= std::false_type;
    
    	~NUMA-Allocator() = default;
    	NUMA-Allocator (const int node) noexcept : node_(node) {numa_available();}
    	…
    };
    

    Wenn man nun noch die fehlenden Bestandteile der Klasse implementieren würde, wäre man fertig, wenn es da nicht ein Problem gäbe. Wichtig ist die Zeile 9 propagate_on_container_swap. An Containerklassen werden beim Swap spezielle Anforderungen gestellt, die dazu führen, dass man undefiniertes Verhalten erhält, wenn man propagate_on_container_swap = std::false_type definiert. Nachlesen kann man diese Anforderungen an die Containerklassen in N4791 Kapitel 21.2.1 Absätze 8 und 9. In Absatz 9 heißt es: »The expression a.swap(b), for containers a and b of a standard container type other than array, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements.« Auf diese Problematik wurde ich dank eines Blog-Eintrages aufmerksam. Das Problem existiert auch in der aktuellen ISO Norm, somit auch den Drafts N3797, N4659 und auch den neueren Drafts.

    Damit das ein jeder nachvollziehen kann, habe ich einen TestAllocator geschrieben (der Code lässt sich nun auch übersetzen und ist kein Pseudocode mehr) der NUMA-Knoten simuliert. Der Speicherverwaltung ist alles andere als perfekt, es fragmentiert noch und std::list ist ineffizient. Das kann man sicherlich alles verbessern, aber das sollte nicht das Hauptthema sein.

    /*
     * TestAllocator.h
     */
    
    #ifndef TESTALLOCATOR_H_
    #define TESTALLOCATOR_H_
    
    #include <cstddef>
    #include <memory>
    #include <list>
    #include <vector>
    #include <algorithm>
    #include <iostream>
    
    struct Chunk {
    	size_t size_;
    	void* p_;
    	bool operator< (const Chunk& rhs) {
    		return (this->size_ < rhs.size_);
    	}
    };
    
    struct Node {
    	std::list<Chunk> free_;
    	std::list<Chunk> used_;
    	size_t size_;
    	void* p_;
    
    	~Node() {
    		free(p_);
    	}
    	Node (size_t s) : size_(s), p_(malloc(s)) {
    		Chunk ck = {s, this->p_};
    		this->free_.push_back(ck);
    	}
    	Node(Node&) = delete;
    	Node(Node&&) = delete;
    	Node& operator=(Node&) = delete;
    	Node& operator=(Node&&) = delete;
    
    	void recycle() {
    		///todo search for continues memory and merge chunks to larger chunks
    	}
    };
    
    class MemoryPool {
    	int		n_nodes_;
    	Node*	nodes_;
    public:
    	using IT = std::list<Chunk>::iterator;
    
    	~MemoryPool () {
    		// because of placement new in constructor, we have to use here explicit destructor calls
    		for (int i = 0; i < n_nodes_; ++i) {
    			nodes_[i].~Node();
    		}
    	}
    	// This is the only way of constructing Node without temporaries. Therefore no chance to avoid placement new
    	MemoryPool (int nodes, const size_t s) : n_nodes_(nodes), nodes_(static_cast<Node*>(::operator new[](sizeof(Node)*nodes))) {
    		for (int i = 0; i < n_nodes_; ++i) {
    			::new(nodes_+i) Node(s);
    		}
    	}
    	MemoryPool(MemoryPool&) = delete;
    	MemoryPool(MemoryPool&&) = delete;
    	MemoryPool& operator= (MemoryPool&) = delete;
    	MemoryPool& operator= (MemoryPool&&) = delete;
    
    	void* pas (void* p, const size_t s) {
    		char* q = static_cast<char*>(p);
    		q += s;
    		return static_cast<void*>(q);
    	}
    
    	[[nodiscard]] void* allocate (const size_t s, int node) {
    		if (node >= n_nodes_) throw std::runtime_error ("allocate wrong too large node supplied");
    
    		void* p = nullptr;
    		IT old;
    		bool found = false;
    		bool del = false;
    
    		for (IT i = nodes_[node].free_.begin(); i != nodes_[node].free_.end(); ++i) {
    			if (i->size_ >= s) {
    				found = true;
    				p = i->p_;
    				Chunk ck;
    				ck.size_	= s;
    				ck.p_		= p;
    				//i->p_ += s;
    				i->p_ = pas (i->p_, s);
    				// set return value;
    				nodes_[node].used_.push_back(ck);
    
    				if (0 == ck.size_) {
    					del = true;
    					old = i;
    				} else {
    					i->size_  -= s;
    				}
    
    				nodes_[node].used_.sort();
    				break;
    			}
    		}
    
    		if (del) {
    			nodes_[node].free_.erase(old);
    		}
    		if (! found) {
    			throw std::runtime_error ("no chunk found");
    		}
    
    		std::cout << "MemoryPool::allocate   node=" << node << " size=" << s << " p=" << p << std::endl;
    
    		return p;
    	}
    
    	void deallocate (void * p, const size_t n, int node) {
    		std::cout << "MemoryPool::deallocate node=" << node << " size=" << n << " p=" << p << std::endl;
    		//testing
    		IT it = nodes_[node].used_.begin(), en = nodes_[node].used_.end();
    
    		while (it != en) {
    			if (it->p_ == p) break;
    			++it;
    		}
    
    		if (it == en) {
    			std::cerr << "fatal error can't recover\n";
    			std::cerr << "didn't find p=" << p << std::endl;
    			abort(); //
    		}
    
    		Chunk ck = *it;
    		nodes_[node].used_.erase(it);
    		nodes_[node].free_.push_front(ck);
    		nodes_[node].recycle();
    	}
    };
    
    template <typename T>
    class TestAllocator {
    		int node_;
    		MemoryPool* smp_;
    	public:
    		using value_type 		= T;
    
    		using propagate_on_container_copy_assignment	= std::false_type;
    		using propagate_on_container_move_assignment	= std::false_type;
    		using propagate_on_container_swap				= std::false_type;
    		using is_always_equal							= std::false_type;
    
    		~TestAllocator() = default;
    		TestAllocator (const int node, MemoryPool* smp) noexcept : node_(node), smp_(smp) {}
    		TestAllocator () noexcept : node_(0), smp_(nullptr) {}
    		TestAllocator (const TestAllocator& rhs) noexcept = default;
    		template <class U> TestAllocator (const TestAllocator& rhs) noexcept;
    		TestAllocator (TestAllocator&&) = default;
    		TestAllocator& operator= (const TestAllocator&) = default;
    		TestAllocator& operator= (TestAllocator&&) = default;
    
    		[[nodiscard]] inline T* allocate (const size_t n) {
    			return static_cast<T*> (this->smp_->allocate(sizeof(T)*n, this->node_));
    		}
    		inline void deallocate (T* p, const size_t n) {
    			this->smp_->deallocate(p, n*sizeof(T), this->node_);
    		}
    		template <typename U> friend const bool ::operator== (const TestAllocator<U>&, const TestAllocator<U>&);
    		template <typename U> friend const bool ::operator!= (const TestAllocator<U>&, const TestAllocator<U>&);
    		template <typename U, typename V> friend constexpr bool ::operator== (const TestAllocator<U>& lhs, const TestAllocator<V>& rhs);
    		template <typename U, typename V> friend constexpr bool ::operator!= (const TestAllocator<U>& lhs, const TestAllocator<V>& rhs);
    };
    
    template <typename U>
    const bool operator== (const TestAllocator<U>& lhs, const TestAllocator<U>& rhs) {
    	return (lhs.node_ == rhs.node_);
    }
    
    template <typename U>
    const bool operator!= (const TestAllocator<U>& lhs, const TestAllocator<U>& rhs) {
    	return (lhs.node_ != rhs.node_);
    }
    
    template <class U, class V>
    constexpr bool operator== (const TestAllocator<U>& lhs, const TestAllocator<V>& rhs) {
    	return false;
    }
    
    template <class U, class V>
    constexpr bool operator!= (const TestAllocator<U>& lhs, const TestAllocator<V>& rhs) {
    	return true;
    }
    #endif /* TESTALLOCATOR_H_ */
    

    Und das kleine Testprogramm dazu

    /*
     * vector_test.cc
     */
    
    #include "TestAllocator.h"
    #include <vector>
    #include <iostream>
    
    int main () {
    	using Allocator = TestAllocator<double>;
    	constexpr size_t size = 1024*1024*1024;
    	MemoryPool smp(2, size);
    
    	size_t s = 100;
    
    	Allocator ac1(0, &smp), ac2(1, &smp);
    	std::vector<double,Allocator> v1(s,0.0,ac1), v2{ac2}, v3(s,0.0,ac2);
    
    	std::cout << "Is allocator ac1 equal ac2? ";
    	if (ac1 == ac2) {
    		std::cout << "yes\n";
    	} else {
    		std::cout << "no\n";
    	}
    
    	double d = 1.0;
    	for (size_t i = 0; i < s; ++i) {
    		v1[i] = d;
    		v3[i] = d;
    		d += 1.0;
    	}
    
    	v2 = v3;
    
    	swap(v1, v2);
    
    	for (size_t i = 0; i < s; ++i) {
    		v2[i] += d;
    		d += 1.0;
    	}
    }
    

    Das gibt bei mir den folgenden Output

    MemoryPool::allocate   node=0 size=800 p=0x7f8e2de3c010
    MemoryPool::allocate   node=1 size=800 p=0x7f8dede3b010
    Is allocator ac1 equal ac2? no
    MemoryPool::allocate   node=1 size=800 p=0x7f8dede3b330
    MemoryPool::deallocate node=1 size=800 p=0x7f8dede3b010
    MemoryPool::deallocate node=1 size=800 p=0x7f8e2de3c010
    fatal error can't recover
    didn't find p=0x7f8e2de3c010
    Abgebrochen (Speicherabzug geschrieben)
    

    Wie man hier sieht, wird der Status des Allokatoren ignoriert und der Speicher radikal über den falschen Allokatoren freigegeben. Was nicht passieren dürfte. Dazu wurden ja, die Operatoren in TestAllocator entsprechend definiert.

    Ich hoffe auf einen angeregte Diskussion.

    Nachtrag:
    Links auf die betreffenden Drafts ergänzt, der neuste ist übrigens N4800.



  • tl;dr *Was* will er?



  • @Swordfish sagte in Allokatoren und die NUMA-Problematik:

    tl;dr *Was* will er?

    "tl;dr" das ist das Problem. Es steht ja alles da.

    • Die ISO Norm ist kaputt, denn die Definition der Allocatoren und der Container sind inkompatibel, wenn so etwas wie einen NUMA-Allokator verwendet, was für einen Allokator explizit erlaubt ist.
    • std::vector als Basis für eine Matriz ist nicht wirklich hilfreich.


  • @john-0
    Ich fürchte swap() mit propagate_on_container_swap = std::false_type ist ein Problem. Liesse sich IMO in Standard fixen, aber so lange da "undefined behavior" drinnen steht...

    Was nicht passieren dürfte. Dazu wurden ja, die Operatoren in TestAllocator entsprechend definiert.

    Doch, darf leider schon. Im Standard steht ja dass propagate_on_container_swap = std::false_type + Einsatz von swap = UB.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    Doch, darf leider schon. Im Standard steht ja dass propagate_on_container_swap = std::false_type + Einsatz von swap = UB.

    Da hast Du mich falsch verstanden. Natürlich steht das so in der Norm, aber die Norm selbst ist defekt, weil hier sich zwei widersprechende Regelungen festgelegt wurden. Denn ein Allokator darf eindeutig sich so verhalten, aber eben nicht in Zusammenhang mit einem Container der Standard Library. Was zum nächsten Punkt führt. Es gibt gute Gründe eine Matrixklasse mit rohem Speicher, der über einen Allokator o.ä. alloziert wird, zu implementieren. Ein std::vector bietet sich wegen dieser Problematik nicht an – jedenfalls nicht automatisch.



  • @john-0 sagte in Allokatoren und die NUMA-Problematik:

    Da hast Du mich falsch verstanden. Natürlich steht das so in der Norm, aber die Norm selbst ist defekt, weil hier sich zwei widersprechende Regelungen festgelegt wurden. Denn ein Allokator darf eindeutig sich so verhalten, aber eben nicht in Zusammenhang mit einem Container der Standard Library.

    Doch, auch im Zusammenhang mit STL Containern. Bloss nicht wenn man diese Container dann noch mit swap() tauscht.

    Ich finde es nur halbwegs "feig" dass der Standard das ganze einfach UB macht. Wäre ja nix dabei wenigstens zu verlangen dass ein Programm das solche Container swappen möchte einfach nicht compiliert.

    Oder, noch praktischer: Dass in dem Fall swap() halt nimmer O(1) ist.

    Ob man das "defekt" nennen kann weiss ich nicht. Sehr ärgerlich und unpraktisch ist es aber auf jeden Fall.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    Oder, noch praktischer: Dass in dem Fall swap() halt nimmer O(1) ist.

    Genau darum geht es. Wenn man Allokatoren mit propagate_on_container_swap == std::false_type erlaubt, dann muss man auch so konsequent sein, dass O(1) nicht mehr möglich ist und O(N) notwendig ist. Das fehlt hier.

    Ob man das "defekt" nennen kann weiss ich nicht. Sehr ärgerlich und unpraktisch ist es aber auf jeden Fall.
    Weshalb darf man dann Allokatoren so definieren und diese dann auch noch mit Container nutzen?



  • Für den nachvolgenden Verkehr wäre es nett gewesen wenn einer der sowieso nachgeschaut hat die betreffenden Stellen zitiert und/oder verlinkt hätte. Just sayin.



  • @Swordfish
    Ich hab das ehrlich gesagt nicht im Standard direkt nachgesehen sondern auf cppreference nachgelesen: https://en.cppreference.com/w/cpp/named_req/Allocator

    Dort steht zu A::propagate_on_container_swap:

    true if the allocators of type A need to be swapped when two containers that use them are swapped. If this member is false and the allocators of the two containers do not compare equal, the behavior of container swap is undefined.


    @john-0 Mir fällt gerade auf... das "and the allocators of the two containers do not compare equal" ist vermutlich auch der Grund warum es im Standard so komisch geregelt ist.

    Denn damit swap() so funktioniert wie wir es uns vorstellen/wünschen, müssen die Elemente copy-constructible oder nothrow-move-constructible sein. Für Container wie set oder map ist das aber keine Anforderung.

    swap() ganz wegzunehmen wäre aber auch irgendwie doof, weil's ja trotzdem erlaubt ist, falls die Allokatoren kompatibel sind ("equal" vergleichen).

    Wobei es vermutlich möglich wäre zu sagen

    1. Wenn die Allokatoren "equal" vergleichen werden einfach die Zeiger getauscht und swap ist O(1).
    2. Wenn die Allokatoren "not-equal" vergleichen und die Elemente copy-constructible und/oder nothrow-move-constructible sind wird swap O(N) und kopiert/moved.
    3. Wenn die Allokatoren "not-equal" vergleichen und die Elemente weder copy-constructible noch nothrow-move-constructible sind ist es UB.


  • @Swordfish sagte in Allokatoren und die NUMA-Problematik:

    Für den nachfolgenden Verkehr wäre es nett gewesen wenn einer der sowieso nachgeschaut hat die betreffenden Stellen zitiert und/oder verlinkt hätte. Just sayin.

    Die Stellen sind referenziert bzw. kurze Zitate eingefügt. Ich habe die Links auf die Drafts ergänzt, allerdings gehe ich hier Forum davon aus, dass man weiß wie man an die Drafts kommt bzw. im Forum sollte sich ein Artikel damit befassen.

    P.S. Dir war der Beitrag ohnehin schon zu lang, wenn ich da z.B. die Tabelle 34 mit den allocator requirements ergänzt hätte, wäre er mehr als doppelt so lang geworden.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    Denn damit swap() so funktioniert wie wir es uns vorstellen/wünschen, müssen die Elemente copy-constructible oder nothrow-move-constructible sein. Für Container wie set oder map ist das aber keine Anforderung.

    Das ist aber allgemein eine Voraussetzung für Elemente in Container z.B. bei einem vector<>::resize müssen die Elemente ebenfalls so verschoben werden. Wie will man das verhindern das kopiert wird?



  • @john-0
    Vielleicht wennst den nächsten Satz auch noch gelesen hättest... map, set... list...
    Also nein, das ist ganz sicher keine allgemeine Voraussetzung für Container.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    @john-0
    Vielleicht wennst den nächsten Satz auch noch gelesen hättest... map, set... list...
    Also nein, das ist ganz sicher keine allgemeine Voraussetzung für Container.

    Alle Container (AllocatorAwareContainer) bis auf array (der einzige Container, der nicht AllocatorAware ist) müssen nach N4791 Tabelle 65 (in N3797 ist es noch Tabelle 99) folgende Eigenschaften aufweisen.

    • Cpp17DefaultConstructible
    • Cpp17CopyInsertable
    • Cpp17MoveInsertable
    • Cpp17CopyAssignable
    • Cpp17MoveAssignable


  • @john-0
    Die Container schon aber nicht deren Elemente. Ich rede von den Elementen. Ist das so schwer zu verstehen?



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    @john-0
    Die Container schon aber nicht deren Elemente. Ich rede von den Elementen. Ist das so schwer zu verstehen?

    Entschuldigung, da fehlte etwas: Diese Eigenschaften sind für die Elemente in den Container eingefordert.



  • @john-0
    Wenn du die Elemente meinst, dann liegst du schlicht und einfach falsch.

    Wenn ich eine map<T>* habe, und diese kopieren will, dann muss T natürlich kopierbar sein.
    Wenn ich einfach nur T-s da rein-emplacen und wieder raussuchen möchte, dann musst T weder kopierbar noch movebar sein.

    Bei vector ist es anders, da vector zum wachsen halt moven bzw. kopieren muss.

    In der von dir genannten Tabelle 65 steht auch nichts anderes. Links steht was man mit dem Container macht und rechts dann was der Allocator bzw. das Element dafür können muss.

    Alleine dass es diese Tabelle überhaupt gibt sollte schon klar machen dass nicht immer alle Anforderungen an den Allokator/die Elemente gelten. Wenn immer alles gelten würde täte es auch eine einzige Liste von Anforderungen.

    EDIT:
    *: Ich meine natürlich eine map<K, T> oder map<T, U>. Oder ein set<T>. War hoffentlich trotz dem Quatsch mit map<T> klar.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    Wenn ich eine map<T>* habe, und diese kopieren will, dann muss T natürlich kopierbar sein.
    Wenn ich einfach nur T-s da rein-emplacen und wieder raussuchen möchte, dann musst T weder kopierbar noch movebar sein.

    Aha, und wie soll das funktionieren? Alle Standard Container folgen der Wertsemantik! Damit man ein Objekt vom Typ T in einem Container ablegen kann, muss man das Objekt entweder außerhalb konstruieren und dann in den Container kopieren, oder man bewegt es in den Container. Und da es unterschiedliche Möglichkeiten Move(Copy gibt, gibt es die Auswahl an Assignable und Insertable. Wenn der Container auch noch Einträge ohne Vorlagen konstruieren können soll, muss DefaultConstructible erfüllt sein. Damit hat man alles zusammen, um im Falle eines Swaps der Inhalt entsprechend kopieren zu können, sofern der Allokator das erzwingt. Der Punkt ist nur, dass der Text der Norm das nicht erlaubt. Eine Mikrooptimierung die UB erzeugt und das ohne Not.



  • @john-0 sagte in Allokatoren und die NUMA-Problematik:

    Aha, und wie soll das funktionieren?

    Puh, ja, schwierige frage. Vielleicht könnte man die Funktion emplace nehmen die genau dafür gemacht wurde?

    #include <map>
    #include <tuple>
    #include <iostream>
     
    class NixeCopy {
    public:
        NixeCopy(NixeCopy const&) = delete;
        NixeCopy(NixeCopy&&) = delete;
        NixeCopy& operator =(NixeCopy const&) = delete;
        NixeCopy& operator =(NixeCopy&&) = delete;
     
        NixeCopy(int a, int b) : a(a), b(b) {}
     
        int dings() const { return a + b; }
     
    private:
        int a;
        int b;
    };
     
    int main() {
        std::map<int, NixeCopy> m;
        m.emplace( // Woo-hoo, beware, what happens here is se spooky magic
            std::piecewise_construct,
            std::make_tuple(42),
            std::make_tuple(222, 444));
     
        auto const it = m.find(42);
        if (it != m.end()) {
            std::cout << "found: " << it->second.dings() << "\n";
        } else {
            std::cout << "not found :(\n";
        }
    }
    

    https://ideone.com/nfCN4C

    Auf deine restlichen Bemerkungen (von denen auch einige nicht richtig sind) einzugehen erübrigt sich denke ich, da sie auf falschen Annahmen beruhen.



  • @hustbaer sagte in Allokatoren und die NUMA-Problematik:

    @john-0 sagte in Allokatoren und die NUMA-Problematik:

    Aha, und wie soll das funktionieren?

    Puh, ja, schwierige frage. Vielleicht könnte man die Funktion emplace nehmen die genau dafür gemacht wurde?

    Jetzt hast Du gezeigt, dass man unvollständige Typen (in Sinne der Container Definition) in Container ablegen kann – toll. Die Frage war aber gar nicht gestellt. Wenn man sich auf diesem Niveau bewegt, dann kann man einfach sagen, nutze halt swap nicht, wenn Allocator::propagate_on_container_swap::value == std::false_type. Noch einmal, das Problem ist, dass selbst für Ts die alle Eigenschaften für Container erfüllt Container<T>.swap bei einem solchen Allokatoren UB ist.

    Ok, einen wesentlichen Unterschied gibt es bei einem unvollständigen Typen und der Sache mit Allocator::POCS ersteres übersetzt nicht, letzteres gibt UB. Da hätte man doch wenigstens in die Norm hineinschreiben können, dass das nicht übersetzen soll. Im Sinne von static_assert.



  • @john-0 sagte in Allokatoren und die NUMA-Problematik:

    Jetzt hast Du gezeigt, dass man unvollständige Typen (in Sinne der Container Definition) in Container ablegen kann – toll.

    Ich habe deine Frage beantwortet. Und was bitte sollen "unvollständige Typen (in Sinne der Container Definition)" sein? Du erfindest hier Begriffe die es im Standard einfach nicht gibt. Was ein Element-Typ für einen Container können muss ist abhängig davon was man mit dem Container machen möchte. So zu tun als müssten immer alle Typen alles können weil ... "einfach so", ist einfach nur quatsch.

    Die Frage war aber gar nicht gestellt.

    Doch. Von dir. Unmisverständlich:

    Aha, und wie soll das funktionieren?

    Dass sie rhetorisch war weil du der Meinung warst dass es nicht geht ist mir auch klar.

    Wenn man sich auf diesem Niveau bewegt, dann kann man einfach sagen, nutze halt swap nicht, wenn Allocator::propagate_on_container_swap::value == std::false_type.

    Das ist das Niveau des Standards. Finde ich auch nicht gut, aber ich verstehe jetzt wieso es so gemacht wurde. Du willst es anscheinend nicht verstehen. Vermutlich damit du dich schlau fühlen und die Standard-Leute für doof halten kannst.

    Noch einmal, das Problem ist, dass selbst für Ts die alle Eigenschaften für Container erfüllt Container<T>.swap bei einem solchen Allokatoren UB ist.

    Ja, weiss ich. Mir ging es darum Gründe aufzuzeigen warum es mehr oder weniger Sinn macht dass das so definiert wurde. BTW: Ein weiterer Grund: selbst vor C++11 wurde von swap() schon garantiert dass die Adressen der Elemente nach swap() gleich bleiben. Und diese Garantie wollte man vermutlich nicht einfach so einschränken.

    Ok, einen wesentlichen Unterschied gibt es bei einem unvollständigen Typen und der Sache mit Allocator::POCS ersteres übersetzt nicht, letzteres gibt UB.

    Wie, übersetzt nicht? Das Beispiel übersetzt wunderbar. Auch wenn man noch ein swap dazubastelt. Und sogar mit Allocator::POCS = true und swap, und es läuft dann sogar ohne UB, vorausgesetzt dass die beiden Allocator-Instanzen kompatibel sind ("equal" vergleichen).

    Davon abgesehen bedeutet "unvollständiger Typ" etwas ganz anderes als wie du es hier verwendest.

    Da hätte man doch wenigstens in die Norm hineinschreiben können, dass das nicht übersetzen soll. Im Sinne von static_assert.

    Damit würde man allerdings valide Anwendungsfälle verhindern die jetzt möglich (und wohldefiniert) sind. Ob diese wichtig genug sind kann man natürlich hinterfragen.