std::vector vs. std::list bei mehreren Threads + Locking

[314159265358979]

Mit std::list kann man bei mehreren Threads in manchen Fällen viel Locking vermeiden. Locking ist eine komplizierte Sache und muss gut
durchdacht werden. Vor allem, da ich noch nicht viel damit gemacht habe, tue ich mir schwer, wirklich alle Fälle zu sehen, wo synchronisiert werden muss.

Vor 3 Tagen erst habe ich einen IRC Daemon angefangen (Neben meinen 50 anderen Projekten, die gerade alle rumgammeln ). Ich habe hier (für das Socket-Handling) 2 Threads. 1 Acceptor-Thread und 1 Read-/Write- Thread.

Hier schiebt also ein Thread hinten Clients in die list, der zweite läuft die Liste durch und bearbeitet Clients. Liege ich mit folgenden Vermutungen richtig?
- Der Zugriff auf den end()-Iterator muss synchronisiert werden, begin() verändert sich nie
- push_back muss ebenfalls synchronisiert werden, da es die Größe (und damit end()) verändert
- Die Iteration und das Einfügen kann ohne weiteres Locking problemlos parallel ablaufen

Die Zeit, in der hier gelockt werden muss ist ziemlich kurz. Bei vector müsste die komplette Iteration gelockt werden. Das kann dauern, vor allem, da in dem Thread nicht nur das Senden und Empfangen gemacht wird, sondern auch das Parsing und alles, was dazu gehört.

Und abschließend noch eine Frage: Ist es möglich (wahrscheinlich), dass das nicht benötigte Locking den Nachteil der langsameren Iteration (p = p->next vs. ++p) wettmacht?

Grüße,
PI

[gastgast]

Du muss alle schreibenden Zugriffe locken. Paralleles Lesen geht. Da Du bei einem Lesezugriff aber nie wissen kannst, ob kurze Zeit später ein Thread etwas schreiben will musst Du auch die Lesezugriffe locken.

Hierfür eignen sich read-write-locks, wie sie boost und Qt bereit stellen.

[314159265358979]

Im Moment verändert nur der Handle-Thread die Elemente, der Acceptor schiebt welche hinten in die list.

Mein Code ist (schematisch) etwa so aufgebaut:

void handle_clients()
{
    while(run) // Der irdc hat noch einen Konsolen-Thread, der diese Variable auf false setzt, wenn der Server beendet werden soll
    {
        {
            lock_my_client_mutex;
            while(clients.empty())
                my_client_cond_variable.wait(my_lock);
        }

        std::vector<client*> readable_sockets = select(clients.begin(), clients_end() /* spezielle gelockte funktion, die clients.end() zurückgibt */, 0, 250); // warte 250 ms

        handle_readablesockets;
    }
}

void acceptor()
{
    while(run)
    {
        try
        {
            client new_client = server->try_accept(some_timeout);

            {
                lock_clients;
                clients.push_back(new_client);
            }

            my_client_cond_variable.notify_one();
        }

        catch(my_sock_exeption)
        {}
    }
}

[Christoph]

Da der C++-Standard keinerlei Aussagen zu Locking und Multithreading macht, sind deine Annahmen nicht richtig. Nur weil du an zwei unterschiedlichen Enden der Liste operierst, heißt das nicht, dass es nicht zu Konflikten kommen kann.

Bei einer konkreten Implementierung, zum Beispiel der stdlib vom g++, könntest du aber richtig liegen. Aber das ist dann keine C++-Frage, sondern eine Frage zu einem bestimmten Compiler.

[314159265358979]

Christoph schrieb:

Da der C++-Standard keinerlei Aussagen zu Locking und Multithreading macht, sind deine Annahmen nicht richtig.

Da ich mit C++11 arbeite: Was sagt der C++11 Standard dazu?

Christoph schrieb:

Nur weil du an zwei unterschiedlichen Enden der Liste operierst, heißt das nicht, dass es nicht zu Konflikten kommen kann.

Ich könnte mir vorstellen, dass es im Debug kracht. Aber im Release sollte es bei jeder guten Implementierung hinhauen.

Christoph schrieb:

Bei einer konkreten Implementierung, zum Beispiel der stdlib vom g++, könntest du aber richtig liegen. Aber das ist dann keine C++-Frage, sondern eine Frage zu einem bestimmten Compiler.

Wo kann ich sowas nachsehen? Ich arbeite ausschließlich mit G++.

[ipsec]

314159265358979 schrieb:

- Der Zugriff auf den end()-Iterator muss synchronisiert werden, begin() verändert sich nie
- push_back muss ebenfalls synchronisiert werden, da es die Größe (und damit end()) verändert
- Die Iteration und das Einfügen kann ohne weiteres Locking problemlos parallel ablaufen

- Auch begin() muss gelockt werden, weil ein Thread versuchen könnte, am Anfang einzufügen
- Einfügen muss gelockt werden, weil z.B. zwei Threads gleichzeitig an der selben Stelle einfügen könnten und es somit einen Datarace auf die prev- und next-Zeiger auslösen würden. Da push_pack nur ein Sonderfall des Einfügens ist, muss es auch gelockt werden.
- Iteration muss nur dann nicht gelockt werden, wenn es in der Zeit zu garantiert keinen Schreibzugriffen kommt

Verallgemeinerung (wurde schon genannt): jeglichen Schriebzugriff locken, Lesezugriffe dann locken, wenn es währenddessen zu Schreibzugriffen kommen kann

[314159265358979]

ipsec schrieb:

- Auch begin() muss gelockt werden, weil ein Thread versuchen könnte, am Anfang einzufügen
- Einfügen muss gelockt werden, weil z.B. zwei Threads gleichzeitig an der selben Stelle einfügen könnten und es somit einen Datarace auf die prev- und next-Zeiger auslösen würden. Da push_pack nur ein Sonderfall des Einfügens ist, muss es auch gelockt werden.
- Iteration muss nur dann nicht gelockt werden, wenn es in der Zeit zu garantiert keinen Schreibzugriffen kommt

Ich hätte wohl dazuschreiben sollen, dass ich mich hier lieber auf meinen konkreten Fall beziehen möchte, also:
- Der einzige Thread, der überhaupt einfügt, ist der Acceptor Thread, und der fügt am Ende ein.
- Nur 1 Thread fügt ein - am Ende - darum sichere ich hier nur die Zugriffe auf end()
- Wie schon gesagt, nur der Client-Thread verändert die Elemente.

[Tachyon]

Bei einer std::list ändert sich end nicht, auch nicht durch Einfügen oder push_back . begin kann sich ändern, wenn die Liste leer ist, oder Du am Anfang einfügst.
Bei einem std::vector können sich alle iteratoren durch Einfügen ändern und ungültig werden.
Für Single-Writer<->Multiple-Reader Szenarien gibt es solche Sachen wie boost::shared_lock und boost::unique_lock.
Wenn Deine C++11-Implementierung das Threadzeugs schon drin hat, gibts shared_lock und uniquie_lock vielleicht auch ohne boost.

[314159265358979]

Tachyon schrieb:

Bei einer std::list ändert sich end nicht, auch nicht durch Einfügen oder push_back .

Stimmt, daran hab ich jetzt gar nicht gedacht. Allerdings möchte ich nur sicherstellen, dass kein Thread die Größe ändern kann, während der andere gerade was damit macht. Hier muss ich wohl end um 1 erniedrigen, und mich dann bis end vor arbeiten?

Tachyon schrieb:

begin kann sich ändern, wenn die Liste leer ist, oder Du am Anfang einfügst.

Der Client-Thread wartet ja solange, bis die Liste Inhalt hat, am Anfang füge ich ebenfalls nicht ein. Sollte also passen.

Tachyon schrieb:

Bei einem std::vector können sich alle iteratoren durch Einfügen ändern und ungültig werden.

Das war einer der Gründe, warum ich zur std::list gegriffen habe.

Tachyon schrieb:

Für Single-Writer<->Multiple-Reader Szenarien gibt es solche Sachen wie boost::shared_lock und boost::unique_lock.
Wenn Deine C++11-Implementierung das Threadzeugs schon drin hat, gibts shared_lock und uniquie_lock vielleicht auch ohne boost.

Meine Implementierung hat noch keine Threads - aber dafür steht mir boost komplett zur Verfügung
unique_lock benutze ich bei meiner Condition Variable. Alle anderen Locks sind lock_guards. Wobei ich auch ehrlich zugeben muss, dass ich den Unterschied zu einem normalen lock_guard nicht kenne. (Die Condition Variable verlangt einen unique_lock.)

[QuellenBitte]

Christoph schrieb:

Bei einer konkreten Implementierung, zum Beispiel der stdlib vom g++, könntest du aber richtig liegen.

Quellen bitte.
Die Allokatoren sind threadsafe. Die Container selbst sind nicht threadsafe.

[Christoph]

Tachyon schrieb:

Bei einer std::list ändert sich end nicht, auch nicht durch Einfügen oder push_back .

Diese Garantie gilt aber nur bei Single-Threaded-Programmen. Der C++-Standard behandelt kein Multi-Threading, deswegen gilt diese Garantie dort nicht mehr. Wenn du ein std::list::push_front() machst, ist zwar vorher und nachher end() derselbe iterator, aber während push_front() läuft, muss soweit ich weiß end() nicht gültig sein, und die Liste muss sich auch nicht in einem konsistenten Zustand befinden. Genau das wär nämlich (Teil einer) Garantie, dass die Container thread-safe sind, was sie wohl bei g++ nicht sind, wenn ich das nächste Posting so anschaue:

QuellenBitte schrieb:

Christoph schrieb:

Bei einer konkreten Implementierung, zum Beispiel der stdlib vom g++, könntest du aber richtig liegen.

Quellen bitte.
Die Allokatoren sind threadsafe. Die Container selbst sind nicht threadsafe.

Das war ein "könnte" im Sinne von "es ist nicht prinzipiell ausgeschlossen, dass es geht". Im Gegensatz dazu ist es prinzipiell ausgeschlossen, dass das geht, wenn man nur nach dem C++-Standard geht. Also scheint es wohl bei g++ nicht zu gehen.

[TyRoXx]

314159265358979 schrieb:

Meine Implementierung hat noch keine Threads - aber dafür steht mir boost komplett zur Verfügung
unique_lock benutze ich bei meiner Condition Variable. Alle anderen Locks sind lock_guards. Wobei ich auch ehrlich zugeben muss, dass ich den Unterschied zu einem normalen lock_guard nicht kenne. (Die Condition Variable verlangt einen unique_lock.)

Wenn du sowieso Boost verwendest, warum dann nicht einfach Asio?

[314159265358979]

Boost.Asio ist alles andere als einfach mit den tausenden Handlern. Ich bleibe bei meinen performanten C-Sockets.

[314159265358979]

Wenn ich immer von rbegin() bis rend() iteriere, dürfte alles (mit Locking natürlich) problemlos gehen, wenn ich mich nicht täusche. Die Reihenfolge für die Clients ist ja sowieso egal.

[gastgast]

Ich verstehe nicht, warum nicht einfach der Zugriff auf die Klasse mit einem mutex gelockt wird. Die std-lib schreibt nur sehr eingeschränkt vor, wie die methoden der container zu implementieren sind. Daher kann eigentlich nie davon ausgegagen werden, dass bestimmte Methoden thread-safe sind.

Wenn es um performance geht, kann man sich noch überlegen, bestimmte Methoden, z.B. für die iteratoren nicht thread-safe zu implementieren und nur in der konkreten Anwendung per mutex des myList-Objekte explizit zu locken.

[314159265358979]

Mein Server soll auf Performance ausgelegt sein. Das heißt:
- Möglichst wenig Heap-Allokationen (Ungenutzten Speicher recyclen!)
- Möglichst viel Locking vermeiden durch gute Struktur (der bool run ist z.B. ein static volatile bool im global Scope. Hier ist volatile genau richtig! Locking wäre absolut übertrieben.)
- Möglichst kein std::string (Kopien vermeiden!)
- etc.

C-Strings sind gar nicht mal so schlimm (Im Gegenteil, ich mag die Dinger. :p ). Das einzig schlimme ist meine Read-Funktion (75 Zeilen lang, herumgeschiebe mit 5 Zeigern auf nen Buffer), aber dafür ist es ziemlich flott.

[ipsec]

314159265358979 schrieb:

Mein Server soll auf Performance ausgelegt sein. Das heißt:
- Möglichst wenig Heap-Allokationen (Ungenutzten Speicher recyclen!)
- Möglichst viel Locking vermeiden durch gute Struktur (der bool run ist z.B. ein static volatile bool im global Scope. Hier ist volatile genau richtig! Locking wäre absolut übertrieben.)
- Möglichst kein std::string (Kopien vermeiden!)
- etc.

Scheint mir alles eher Premature Optimization zu sein. Wenn du tatsächlich eine Stelle hast, wo Heap-Allokationen performancekritisch sind, solltest du vielleicht gleich einen anderen Allokator (z.B. einen Pool-Allokator) nehmen. volatile hat mit threadsynchronisiert in etwa so wenig zu tun wie global static mit performanter und wenn du trotz Move-Semantik usw. so viele unnötigen String-Kopien machst, dass die Performance leidet, helfen dir C-Strings wohl erst recht nicht.

Davon abgesehen: wie viele Millionen Clients erwartest du denn auf deinem Server, dass du dir solche Performanceüberlegungen bei einem IRC-Daemon stellst?

[314159265358979]

ipsec schrieb:

Scheint mir alles eher Premature Optimization zu sein.

Korrekt. Ich steh auf Performance. :p

ipsec schrieb:

Wenn du tatsächlich eine Stelle hast, wo Heap-Allokationen performancekritisch sind, solltest du vielleicht gleich einen anderen Allokator (z.B. einen Pool-Allokator) nehmen.

Werde ich noch machen.

ipsec schrieb:

volatile hat mit threadsynchronisiert in etwa so wenig zu tun wie global static mit performanter

volatile bewirkt, dass die anderen Threads Änderungen bemerken. Ist mir doch egal, ob der Server nun 2 Durchläufe mehr oder weniger läuft. Global static hab ich der vollständigkeit halber erwähnt.

ipsec schrieb:

und wenn du trotz Move-Semantik usw. so viele unnötigen String-Kopien machst, dass die Performance leidet, helfen dir C-Strings wohl erst recht nicht.

Man müsste keine einzige Kopie machen (!)
Move ist auch nicht gratis.

ipsec schrieb:

Davon abgesehen: wie viele Millionen Clients erwartest du denn auf deinem Server, dass du dir solche Performanceüberlegungen bei einem IRC-Daemon stellst?

Wie oben erwähnt: Das ist mir egal. Performance ist doch schön.

[TyRoXx]

314159265358979 schrieb:

Mein Server soll auf Performance ausgelegt sein. Das heißt:
- Möglichst wenig Heap-Allokationen (Ungenutzten Speicher recyclen!)
- Möglichst viel Locking vermeiden durch gute Struktur (der bool run ist z.B. ein static volatile bool im global Scope. Hier ist volatile genau richtig! Locking wäre absolut übertrieben.)
- Möglichst kein std::string (Kopien vermeiden!)
- etc.

C-Strings sind gar nicht mal so schlimm (Im Gegenteil, ich mag die Dinger. :p ). Das einzig schlimme ist meine Read-Funktion (75 Zeilen lang, herumgeschiebe mit 5 Zeigern auf nen Buffer), aber dafür ist es ziemlich flott.

Meinst du das irgendwie ironisch oder so? Kommt mir beim Lesen so vor (du schreibst "gute Struktur" über den absoluten Anti-Code, "Locking wäre absolut übertrieben" wahrscheinlich ohne das einmal gemessen zu haben).
Was soll an std::string besser sein als an C-Strings? Es ist ja nicht so, dass man die Dinger ständig kopieren müsste, wenn das Programm vernünftig gestaltet ist.
Ich vermute, dass das ganze mit Boost.Asio sowohl einfacher als auch schneller wäre. Da ist Asynchronität nämlich mit eingebaut und du musst das nicht als Halbwissender ("Hier ist volatile genau richtig!") hinfrickeln.

BONUSMATERIAL:

314159265358979 schrieb:

ipsec schrieb:

volatile hat mit threadsynchronisiert in etwa so wenig zu tun wie global static mit performanter

volatile bewirkt, dass die anderen Threads Änderungen bemerken. Ist mir doch egal, ob der Server nun 2 Durchläufe mehr oder weniger läuft. Global static hab ich der vollständigkeit halber erwähnt.

Eben nicht.

314159265358979 schrieb:

ipsec schrieb:

und wenn du trotz Move-Semantik usw. so viele unnötigen String-Kopien machst, dass die Performance leidet, helfen dir C-Strings wohl erst recht nicht.

Man müsste keine einzige Kopie machen (!)
Move ist auch nicht gratis.

Aber so gut wie.
Einen const char * zu kopieren ist auch nicht gratis, also solltest du die Strings besser ganz weglassen, könnte am Ende zu langsam werden!!111elf

314159265358979 schrieb:

ipsec schrieb:

Davon abgesehen: wie viele Millionen Clients erwartest du denn auf deinem Server, dass du dir solche Performanceüberlegungen bei einem IRC-Daemon stellst?

Wie oben erwähnt: Das ist mir egal. Performance ist doch schön.

Performance ist völlig wurscht, wenn der Unterschied nicht nachweisbar ist.

[gastgast]

Der Punkt ist: Ohne zu messen, wissen die meisten - zu denen ich mich auch zähle - außer bei trivialen Konstrukten nicht, was performant ist und was nicht.

Konkretes Beispiel aus meinen letzten Arbeitswochen:

Ich habe einen Code gereviewt, bei dem eine 2D Matrix aus Performancegründen auf 1D abgebildet und dann mit pointern und pointerarithmetik gearbeitet wurde. Ich bin dann hergegangen und habe das gegen vector<vector<T>> gemessen und siehe da: Die Version mit std::vector ist bei verwendung von intrinsischen Typen (char, int, float, double) zwischen 3% und 17% schneller, je nachdem was man als T einesetzt.

Hinzu kommt, dass Du, wenn Du argumentierst:

Ist mir doch egal, ob der Server nun 2 Durchläufe mehr oder weniger läuft. Gloabal static hab ich der vollständigkeit halber erwähnt.

Du Dir selbst widersprichst, weil genau das, all Deine Optimierungsbemühungen zunichte machen kann.