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

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

[314159265358979]

gastgast schrieb:

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

Da liegst du vollkommen falsch, sorry. Wenn ich beim Beenden des Servers mal 500 ms länger mache, ist das nichts. Wenn ich bei jedem Schleifendurchlauf 0,5 ms länger warte, kommt da ordentlich was zusammen.

[ipsec]

314159265358979 schrieb:

ipsec schrieb:

Scheint mir alles eher Premature Optimization zu sein.

Korrekt. Ich steh auf Performance. :p

Leider geht die in solcher Form meistens nach hinten los. Der Code wird aufgeblähter, komplexer, unwartbarer und ist am Ende öfters auch tatsächlich langsamer. Hast du bei diesen Fällen gemessen, dass deine Varianten schneller sind?

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.

Nö. volatile bewirkt nur, dass der Compiler die Variable nicht wegoptimiert. Es sichert z.B. keine Cache-Kohärenz. Das macht die Threading-Library deiner Wahl, auch ohne volatile.

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 (!)

Dann musst du es mit Strings auch nicht. Kannst du mal deine read-Funktion posten? Im Übrigen: ein String-Move besteht in der Zuweisung von ein paar Zeigern - das dauert ein paar CPU-Takte. Allein mit deiner C-String-Verwaltung wirst du mit Sicherheit wesentlich mehr vergeuden.

[314159265358979]

TyRoXx schrieb:

du schreibst "gute Struktur" über den absoluten Anti-Code

Gute Struktur im Sinne von "wenige kurze Abschnitte, die synchronisiert laufen müssen".

TyRoXx schrieb:

"Locking wäre absolut übertrieben" wahrscheinlich ohne das einmal gemessen zu haben).

Ich wette, volatile bool ist schneller als 2 Aufrufe zum OS-Scheduler.

TyRoXx schrieb:

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.

Auch "gelegentlich" ist zu viel.

TyRoXx schrieb:

Ich vermute, dass das ganze mit Boost.Asio sowohl einfacher

Das bewezeifle ich. Asynchronität mit C-Sockets ist keine Zauberei.

TyRoXx schrieb:

als auch schneller wäre.

Das bezweifle ich auch mal. Direkt C API aufrufen oder Mega Wrapper aufrufen? Hm...

TyRoXx schrieb:

Da ist Asynchronität nämlich mit eingebaut

Mit einem kotzigen Interface. Klasse.

TyRoXx schrieb:

und du musst das nicht als Halbwissender

Was du alles weißt, das ich nicht weiß.

TyRoXx schrieb:

("Hier ist volatile genau richtig!") hinfrickeln.

Hinfrickeln? Du kennst von meinem Code doch nur Auszüge.

TyRoXx schrieb:

Eben nicht.

Eben doch.

TyRoXx schrieb:

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

Ich kopiere keine C-Strings, danke trotzedem für den Tipp.

TyRoXx schrieb:

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

Dir schon, mir nicht.

[314159265358979]

ipsec schrieb:

Leider geht die in solcher Form meistens nach hinten los. Der Code wird aufgeblähter, komplexer, unwartbarer und ist am Ende öfters auch tatsächlich langsamer. Hast du bei diesen Fällen gemessen, dass deine Varianten schneller sind?

Da hast du wohl Recht. Nein, ich habe nicht nachgemessen.

ipsec schrieb:

Nö. volatile bewirkt nur, dass der Compiler die Variable nicht wegoptimiert. Es sichert z.B. keine Cache-Kohärenz. Das macht die Threading-Library deiner Wahl, auch ohne volatile.

Das schlage ich mal im Standard nach, wenn ich Zuhause bin. Meiner Meinung signalisiert volatile dem Compiler, dass die Variable von außen geändert werden kann. Hat mit Optimierungen zu tun, so viel weiß ich.

ipsec schrieb:

Dann musst du es mit Strings auch nicht. Kannst du mal deine read-Funktion posten? Im Übrigen: ein String-Move besteht in der Zuweisung von ein paar Zeigern - das dauert ein paar CPU-Takte. Allein mit deiner C-String-Verwaltung wirst du mit Sicherheit wesentlich mehr vergeuden.

Ich fahre jetzt nach Hause, dann poste ich gerne meine read-Funktion.

[TyRoXx]

Ok, dann werde ich eben etwas sachlicher.

void handle_clients()
{
    while(run) // Der irdc hat noch einen Konsolen-Thread, der diese Variable auf false setzt, wenn der Server beendet werden soll
    {
        {
			//TyRoXx: Hier verwendest du einen Mutex, aber für 'run' ist das dann zu teuer?
			//TyRoXx: Du könntest ja auch beide Variablen zusammen schützen, würde hier keinen Unterschied machen.
            lock_my_client_mutex;
            while(clients.empty())
                my_client_cond_variable.wait(my_lock);
        }

		//TyRoXx: Hier wird wahrscheinlich mit dem bekannten select() auf alle Sockets gepollt.
		//TyRoXx: Ist das Kopieren eines std::vector<T> nicht viel zu teuer für dich?
		//TyRoXx: Außerdem muss das mehrmals pro Sekunde stattfinden, damit der Server halbwegs benutzbar ist.
        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
        {
			//TyRoXx: Wieder Polling = teuer.
            client new_client = server->try_accept(some_timeout);

            {
                lock_clients;

				//TyRoXx: Müsste eine std::list<T> oder std::vector<T> nicht viel zu teuer sein?
                clients.push_back(new_client);
            }

			//TyRoXx: Ganz abgesehen von boost::condition_variable, das AFAIK intern eine Queue verwendet.
            my_client_cond_variable.notify_one();
        }
		//TyRoXx: Wenn Performance so wichtig wäre, dürftest du keine Exceptions benutzen. Am besten sogar beim Compiler ausschalten.
        catch(my_sock_exeption)
        {}
    }
}

Und warum überhaupt mehrere Threads? Accept-Sockets funktionieren doch auch mit select .
volatile verwechselst du wahrscheinlich mit dem gleichnamigen Keyword aus Java (oder so).

[Ethon]

Mir fällt spontan kein Fall ein, in dem man eine String-Kopie nicht durch eine Referenz, eine const Referenz oder ein Move vermeiden könnte.

Böse sind natürlich APIs, die von allem Kopien machen, zb stringstreams.
Aber STl Streams sollte man sowieso möglichst vermeiden, wenn man Performance möchte.

//TyRoXx: Wenn Performance so wichtig wäre, dürftest du keine Exceptions benutzen. Am besten sogar beim Compiler ausschalten.

Watt?
Unter 64bit sind nicht-geworfene Exceptions komplett kostenlos, also performanter als sämtliche Alternativen.

[314159265358979]

TyRoXx schrieb:

Ok, dann werde ich eben etwas sachlicher.

void handle_clients()
{
    while(run) // Der irdc hat noch einen Konsolen-Thread, der diese Variable auf false setzt, wenn der Server beendet werden soll
    {
        {
			//TyRoXx: Hier verwendest du einen Mutex, aber für 'run' ist das dann zu teuer? ------ Mutexes verwenden, wo erforderlich.
			//TyRoXx: Du könntest ja auch beide Variablen zusammen schützen, würde hier keinen Unterschied machen. ------ Wie denn? Bin natürlich immer für Optimierungsvorschläge offen
            lock_my_client_mutex;
            while(clients.empty())
                my_client_cond_variable.wait(my_lock);
        }

		//TyRoXx: Hier wird wahrscheinlich mit dem bekannten select() auf alle Sockets gepollt. ------ Sag mir doch mal was besseres.
		//TyRoXx: Ist das Kopieren eines std::vector<T> nicht viel zu teuer für dich?  ------ Wird gemoved.
		//TyRoXx: Außerdem muss das mehrmals pro Sekunde stattfinden, damit der Server halbwegs benutzbar ist. ------ Was schlägst du vor? 1 Thread pro Client?
        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
        {
			//TyRoXx: Wieder Polling = teuer.  ------ Weil du ganz genau weißt, wie mein try_accept funktioniert.
            client new_client = server->try_accept(some_timeout);

            {
                lock_clients;
				
				//TyRoXx: Müsste eine std::list<T> oder std::vector<T> nicht viel zu teuer sein? ------ Du weißt selbst ganz genau, dass das sehr günstig ist.
                clients.push_back(new_client);
            }

			//TyRoXx: Ganz abgesehen von boost::condition_variable, das AFAIK intern eine Queue verwendet. ------ Das verhindert, dass select ohne Sockets aufgerufen wird. Denk mal nach.
            my_client_cond_variable.notify_one();
        }
		//TyRoXx: Wenn Performance so wichtig wäre, dürftest du keine Exceptions benutzen. Am besten sogar beim Compiler ausschalten. ------ Exceptions sind günstig.
        catch(my_sock_exeption)
        {}
    }
}

Und warum überhaupt mehrere Threads? Accept-Sockets funktionieren doch auch mit select . ------ Last verteilen.
volatile verwechselst du wahrscheinlich mit dem gleichnamigen Keyword aus Java (oder so). ------ Nö. Habe ich doch gesagt. Aber ich schlage gleich mal nach.

Und hier meine Read-Funktion.

void handle_client(ircd::client& client)
{
    char* const begin = client.begin;
    char*& mid = client.mid;
    char*& mid2 = client.mid2;
    char* const end = client.end;

    ircd::client_socket& sock = client.socket;

    // just read, the buffer is freeeeee
    char* mid3 = mid2 + sock.read(mid2, 512);

    // look for \n
    char* rn = std::find(mid2, mid3, '\n');

    // if we didn't find \n, try \r. some stupid clients use \r instead
    if(rn == mid3)
        rn = std::find(mid2, mid3, '\r');

    // got it
    if(rn != mid3)
    {
        // message too long?
        if(rn - mid > 512)
        {
            // then just ignore stuff
            mid = rn;

            // save our position
            mid2 = mid3;
        }

        // message not too long
        else
        {
            char* begin = mid;
            char* end = rn;

            // skip all \r's and \n's at front and back
            for(; begin != rn && (*begin == '\r' || *begin == '\n'); ++begin);
            for(; end - 1 != begin - 1 && (end[-1] == '\r' || end[-1] == '\n'); --end);

            // we have characters left
            if(begin != end)
                // parse it
                parse_message(begin, end);

            // now we can ignore the parsed stuff
            mid = rn;

            // set mid2 to the end of data we read
            mid2 = mid3;
        }
    }

    // no \r\n found
    else
    {
        // message too long?
        if(mid3 - mid > 512)
        {
            // kill it with fire
            mid = mid3;
            mid2 = mid3;
        }

        // okay, we have to read again, thus, save our buffer position
        else
            mid2 = mid3;
    }

    // would we meet the end of the buffer next time?
    if(mid2 + 512 >= end)
        // since memcpy kills people, use memmove
        std::memmove(begin, mid, mid2 - mid);
}

Habe mich geirrt, sind 6 Zeiger. Und bevor hier gleich Flames bzgl. std::memmove kommen: Das optimier ich noch weg, hier ist dann die Faulheit zum tragen gekommen :p

[ipsec]

314159265358979 schrieb:

Und hier meine Read-Funktion.

Was ist denn client.begin, client.end, client.mid und client.mid2? Sind das Teile der Nachricht? Was machen die im Client? Und sehe ich richtig, dass Nachrichten länger als 512 Zeichen ignoriert werden?

[314159265358979]

ipsec schrieb:

Was ist denn client.begin, client.end, client.mid und client.mid2? Sind das Teile der Nachricht?

Die benutze ich, um zu speichern, wo ich gerade im Buffer bin.

ipsec schrieb:

Und sehe ich richtig, dass Nachrichten länger als 512 Zeichen ignoriert werden?

Jop. Die maximale Länge ist laut Protokoll 512.

Hier nochmal die client-struct, damits vielleicht verständicher wird.

struct client : boost::noncopyable
    {
        client_socket socket;
        int bufsize;

        std::unique_ptr<char[]> buffer;

        char* begin;
        char* mid;
        char* mid2;
        char* end;

        client(client_socket&& socket)
            : socket(std::move(socket))
            , bufsize(4096)
            , buffer(new char[bufsize])
            , begin(&buffer[0])
            , mid(begin)
            , mid2(begin)
            , end(begin)
        {}

        client(client&& client)
            : socket(std::move(client.socket))
            , bufsize(client.bufsize)
            , buffer(std::move(client.buffer))
            , begin(&buffer[0])
            , mid(begin)
            , mid2(begin)
            , end(begin)
        {
            client.buffer = 0;
        }

        client& operator = (client&& other)
        {
            socket = std::move(other.socket);
            bufsize = other.bufsize;

            buffer = std::move(other.buffer);

            begin = other.begin;
            mid = other.mid;
            mid2 = other.mid2;
            end = other.end;

            other.begin = 0;
            other.mid = 0;
            other.mid2 = 0;
            other.end = 0;

            return *this;
        }
    };

Edit: Da fällt mir doch glatt auf, dass ich mir den begin und end Zeiger schenken könnte. Wie gut, dass ich diesen Thread eröffnet habe.

[Ethon]

Die benutze ich, um zu speichern, wo ich gerade im Buffer bin.

Klingt gruselig, wieso keinen std::vector<> anstatt alles selbst zu machen?

[314159265358979]

Ethon schrieb:

Die benutze ich, um zu speichern, wo ich gerade im Buffer bin.

Klingt gruselig, wieso keinen std::vector<> anstatt alles selbst zu machen?

Das Teil ist ein Ringbuffer. Das heißt, ich lese dort weiter, wo ich als letztes reingeschrieben habe. Dadurch vermeide ich Kopien. Irgendwann ist der Buffer aber dennoch voll, das ist das memmove am Ende. Dann gehts wieder von vorne los.

[Ethon]

314159265358979 schrieb:

Ethon schrieb:

Die benutze ich, um zu speichern, wo ich gerade im Buffer bin.

Klingt gruselig, wieso keinen std::vector<> anstatt alles selbst zu machen?

Das Teil ist ein Ringbuffer. Das heißt, ich lese dort weiter, wo ich als letztes reingeschrieben habe. Dadurch vermeide ich Kopien. Irgendwann ist der Buffer aber dennoch voll, das ist das memmove am Ende. Dann gehts wieder von vorne los.

1. Gibt es da doch was von Ratiophar ... ähh Boost.
2. Was bufferst du da eigentlich? Das Ergebnis von recv ?

[314159265358979]

Ethon schrieb:

1. Gibt es da doch was von Ratiophar ... ähh Boost.

Gut möglich, dazu kenne ich boost zu wenig.

Ethon schrieb:

2. Was bufferst du da eigentlich? Das Ergebnis von recv ?

Genau. Ich lese ja schließlich nicht immer genau bis \r\n. Kann ja auch mal ne halbe Nachricht kommen, dann der Rest und die hälfte der nächsten, usw. Je größer der Buffer, desto weniger muss ich natürlich auch kopieren.

[ipsec]

Äußerst umständlich. Was hindert dich, einen string als Buffer zu verwenden?
Außerdem ist das Design grauenhaft, da viel zu wenig abstrahiert. Nachrichtenbuffer gehören gar nicht in die Clientklasse, sondern in eine Nachrichtenklasse. Und solche Internas wie die aktuelle Bufferposition, auch noch public, haben im Client überhaupt nichts zu suchen. Und das alles nur, weil du dir bessere Performance erhoffst... Das meinte ich mit Premature Optimization.