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

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

[314159265358979]

ipsec schrieb:

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

Nur zu, sag mir wie ichs besser machen könnte. Wäre dir sehr dankbar dafür.

[ipsec]

Ich würde grundlegend anders herangehen. Z.B. würde ich das ganze Zeug mit unvollständigen Nachrichten, mehreren zusammenhängenden Nachrichten usw. den Netzwerkfunktionen überlassen und nicht im Client handeln, der sowas ja eigentlich gar nicht wissen muss. Zur Not selbst schreiben, aber u.A. für sowas wurden Bibliotheken wie Asio gemacht. Ich hab hier mal einen ersten Entwurf, wie ungefähr man es mit Asio lösen könnte (ungetestet, unvollständig, wie gesagt erster Entwurf).

Die message -Klasse stellt dabei eine IRC-Nachricht dar, mit Prefix, Command etc., die client_connection -Klasse ist deine jetzige client -Klasse (ich fand den Namen treffender). Wie man sieht, muss, wer immer sich um die Nachrichten kümmert, sich lediglich beim client_connection::new_message -Signal registrieren (was man eventuell noch kapseln könnte) und einmalig client_connection::start aufrufen, der Rest geschieht wunderschön automatisch, ohne dass es dieser ständigen Poll-Schleifen braucht. Dann brauchst du auch den Handler-Thread überhaupt nicht mehr, sondern nur noch den Akzeptor-Thread, welchen du aber mit Asio auch noch loswerden könntest. Entsprechend fällt manuelles Locking etc. weg, das regelt alles Asio.
Und falls dir die eine String-Kopie tatsächlich zu performancelastig ist (bei 512 Byte ), kannst du message auch gerne einen Iterator-Konstruktor spendieren, und mit istream_iterator arbeiten.

struct message
{
	message(const string& line);	// parse line
	...
};

class client_connection
{
	socket& s;
	asio::streambuf buffer;

public:
	connection(socket& s) : s(s), buffer(512) {}

	void start()
	{
		asio::async_read_until(s, buffer, "\r\n", boost::bind(&connection::handle_line, this, asio::placeholders::error));
	}

	boost::signal<void(const message&)> new_message;

private:
	void handle_line(const boost::system::error_code& e)
	{
		if(!e)
		{			
			std::istream is(&buffer);
			std::string line;
			std::getline(is, line);

			new_message(message(line));
		}

		start();
	}
}

[314159265358979]

Hm, also ich muss zugeben, du hast mich jetzt schon etwas neugierig gemacht. Leider ist die Doku zu Asio schlecht und bei Highscore werde ich auch kaum schlauer.

[ipsec]

Ja da muss ich dir leider Recht geben. Sieh dir am besten die Beispiele und Tutorials an, da lernt man m.E. recht viel über die grundlegende Techniken.

[314159265358979]

Was mich noch etwas stutzig macht: Ich kriege in meiner IDE (Eclipse) keine Libraries gelinkt. Das ist die Fehlermeldung:

ld: library not found for -l/opt/local/lib/libboost-thread-mt.a

Ich habe die Datei über die IDE ausgewählt, der Pfad muss also stimmen.

[Tachyon]

314159265358979 schrieb:

Was mich noch etwas stutzig macht: Ich kriege in meiner IDE (Eclipse) keine Libraries gelinkt. Das ist die Fehlermeldung:

ld: library not found for -l/opt/local/lib/libboost-thread-mt.a

Ich habe die Datei über die IDE ausgewählt, der Pfad muss also stimmen.

Lass mal den Pfad und das lib weg. Und setze den Pfad für die Libs in den entsprechenden Optionen.
Also /opt/local/lib/ in den Pfadeinstellungen, und boost-thread-mt als Lib angeben.
Und benutze boost.asio. Der Einstig ist zugegebenermaßen etwas schwierig, aber aus meiner Sicht lohnt es sich. Außerdem gibt es hier inzwischen einige, welche Fragen dazu beantworten können. Im Zweifelsfall kann man immer Hilfe in den boost.users-Mailinglisten bekommen. Und vor allem die Beispiele helfen auch gut weiter.

[krümelkacker]

314159265358979 schrieb:

Mit std::list kann man [im Gegensatz zu std::vector] bei mehreren Threads in manchen Fällen viel Locking vermeiden.

Nicht wirklich. Es gibt spezielle "Concurrent List"-Implementierungen, ja. Aber std::list kann so etwas nicht. Den Zugriff auf eine std::list musst Du genauso "locken" wie alles andere auch.

314159265358979 schrieb:

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

Nein!