Allokatoren und die NUMA-Problematik

Swordfish

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.

hustbaer

@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

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

*john 0

@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.

*john 0

@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?

hustbaer

@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.

*john 0

@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

hustbaer

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

*john 0

@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.

hustbaer

@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.

*john 0

@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.

hustbaer

@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.

*john 0

@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.

hustbaer

@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.

*john 0

@hustbaer sagte in Allokatoren und die NUMA-Problematik:

Ich habe deine Frage beantwortet.

Du bist der Meinung, Du hättest sie beantwortet. Das ist ein wesentlicher Unterschied. Meine Frage zielte darauf, ob man mit den für Container definierten Konstrukturen einen Container konstruieren kann, wenn T die geforderten Konzepte nicht unterstützt. Das ist offensichtlich nicht der Fall.

Und was bitte sollen "unvollständige Typen (in Sinne der Container Definition)" sein?

Es geht darum, ob ein T alle Konzepte unterstützt, die ein Container benötigt, um den vollen Funktionsumfang des Containers auch unterstützen zu können. Bei dem hier besprochenem ist das offensichtlich nicht der Fall. Dazu erfordert Container<T>.emplace(p.args) bei vector und deque neben dem Konzept EmplaceConstructible auch noch MoveInsertable und MoveAssignable.

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 ...

Der wesentliche Punkt ist, wenn ein T ein Konzept, welches für eine bestimmte Funktionalität des Containers notwendig ist, nicht unterstützt, lässt sich der Programmcode nicht übersetzen. Außer wenn wir über Allocator::POCS::value==std::false_type reden, dann geht das auf einmal doch. Es gibt nun einmal keinerlei sinnvollen Grund, weshalb das noch compilieren soll und UB ergibt. D.h. wenn man Allocator::POCS::value==std::false_type hat, dann darf man eben kein Container<T,Allocator<T>>.swap nutzen. Das wäre mit den neuen Möglichkeiten von C++17 auch kein Problem, und wird an anderer Stelle auch getestet.

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.

Vergessen wir bitte nicht den Ausgangspunkt. Am Anfang stand die Frage, ob es möglich sei eine Matrixklasse mit vector als low level Speicher zu verwenden. Wie man nun sieht, bekommt man Probleme, wenn man einen Allokator nutzt, der POCS als false_type definiert. Gerade an diesem Punkt wird eine eigene Matrixklasse bei HPC aber interessant. Es geht nicht darum sich überlegen zu fühlen, sondern um konkrete Lösungsansätze für konkrete Probleme. Das Fazit daraus, es gibt auch weiterhin gute Gründe low level Speicherverwaltung zu machen, und auf vector mit einem speziellem Allokator zu verzichten. Man kann nun länger darüber diskutieren, ob man bei der angesprochenen Matrixklasse direkt low level Funktionen verwendet, oder ob man diese Klassee AllocatorAware schreibt. Das geht nämlich sehr wohl, so dass POCS trotzdem richtig ausgewertet wird und diese Klasse kein UB hat. Man hat dann nur nicht das O(1) Verhalten von Standard Containern bei swap.

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.

Bei C++2003 war das auch kein Problem, weil es keine Allokatoren mit Zustand geben konnte. D.h. die Definition von Allokatoren und Container waren konsistent. Grundsätzlich spricht nichts dagegen dieses Verhalten unter den gleichen Umständen zu erhalten. Aber weshalb definiert man in den allocator_traits::POCS, wenn die Standard Library offensichtlich davon keinerlei Gebrauch macht? Nur zur Nutzung in eigenem Code? Das ist wirklich dünn.

Wie, übersetzt nicht? Das Beispiel übersetzt wunderbar.

Du hast ein Beispiel gebracht, dass das Konzept EmplaceConstructible fordert, und eine Klasse übergeben, die das erfüllt. Was passiert, wenn die Klasse nicht EmplaceConstructible ist?

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.

Nein, genau das würde nicht passieren. D.h. wenn man in Container<T>.swap()

static_assert(std::allocator_traits<Allocator>::is_always_equal() ||
		std::allocator_traits<Allocator>::propagate_on_container_swap(), "Container Swap is UB");

einfügen würde. Wäre das Problem gelöst, und existierenden Code würde weiterhin genau so funktionieren wie man es bisher kannte. Nur würde der Versuch swapmit dem falschen Allokator zu verwenden vom Compiler abgefangen.

hustbaer

@john-0 Sorry, aber mir wirds echt zu blöd auf dein Geschwurbel weiter einzugehen.

*john 0

@hustbaer sagte in Allokatoren und die NUMA-Problematik:

@john-0 Sorry, aber mir wirds echt zu blöd auf dein Geschwurbel weiter einzugehen.

Mit Verlaub, die Funktion emplace wurde erst mit C++2017 eingeführt. statefull allocators bereits mit C++2011. Deine ganze Argumentation funktioniert nicht. Wenn man denn nicht weiter diskutieren will, kann man das auch anders tun als sich über die Beiträge anderer dispektierlich zu äußern.