Performance von std::queue?

Hi,

ich habe zwei Threads laufen, bei denen einer Daten produziert, die der andere verwertet. Die Daten werden per std::queue vom einen zum anderen verschoben. queue erschien mir sinnvoll, da es ein FiFo sein muss.

Allerdings habe ich das Gefühl, dass queue ein Performanceproblem hat: das Timing ist bei diesen beiden Threads sehr knapp und nach dem eine gewisse Menge Daten durch die queue geschoben wurde, gibt es immer mal Aussetzer, sprich der Datenzugriff dauert sporadisch immer mal überraschend lange.

Nun frage ich mich, ob das an der queue liegt. Wie sieht es da mit der Performace aus, wird da immer mal skaliert/kopiert um die verwendete Speichergröße anzupassen oder ähnliches?

*rant*

Ich denke, dass das Problem eher bei deiner Threading-Lösung liegt, als an der Queue. Ich habe auch schon ähnliches programmieren müssen, und die Queue hat mir bisher immer gereicht. In der Regel ist der Flaschenhals andernorts versteckt.

Welchen Synchronisations-Mechanismus verwendest du, um die Queue geregelt lesen bzw. schreiben zu können? Wenn es nur einen Producer und einen Consumer gibt, wieso benutzt du dann Threads?

:xmas1:

Naja, wenn der Inhalt der Queue wächst, muss irgendwann neuer Speicher angefordert werden. Ansonsten hängt es etwas von der Implementation ab. Welchen Compiler benutzt du?

Ohne diese Information kann ich dir nur sagen, was der Standard sagt: std::queue unterliegt per Default eine std::deque. Durch Anfügen oder Entfernen am Anfang oder Ende einer Deque werden die Elemente in der Mitte nicht verlegt, massig Kopiererei wird da also nicht passieren, sofern die Bibliothek deines Compilers standardkonform ist (Watcom hinkt hier böse hinterher, ansonsten sollte das bei allen bekannteren Compilern der Fall sein). Trotzdem muss natürlich von Zeit zu Zeit neuer Speicher für neue Elemente angefordert werden, und es kann (wird) passieren, dass Verwaltungsinformationen der Deque (wie etwa ein äußerer Index) von Zeit zu Zeit neu aufgebaut werden müssen. In der gängigsten Implementationsmethode bedeutet das, dass von Zeit zu Zeit ein Zeigerarray umgelegt wird.

Ob deine Performanceprobleme wirklich da liegen, findest du am ehesten mit einem Profiler raus. Ich hätte bei einer Queue zwischen zwei Threads aber eher die Synchronisationsmechanismen im Blick - das Ding muss ja vernünftig gemutext werden.

seldon schrieb:

Ich hätte bei einer Queue zwischen zwei Threads aber eher die Synchronisationsmechanismen im Blick - das Ding muss ja vernünftig gemutext werden.

Der Mutex ist eigentlich ziemlich unkritisch, der wird nur dann kurz angeworfen, wenn ein Pointer auf die Datenstruktur in die Queue eingehängt wird bzw. wenn er dort wieder abgeholt und entfernt wird. Der Mutex ist also nur für das push() bzw. für front() und pop() aktiv, sonst gar nicht (und das dürfte ja wohl kaum mal eben 15 oder mehr Millisekunden verplempern).

hustbaer

@Digger:
Wie wartet der Consumer-Thread denn, wenn die Queue mal leer ist?
Doch nicht etwa über Polling?
Oder vielleicht hast du ja einen Fehler in deinem Benachrichtigungs-System?

Unter Windows kann das bei Verwendung von EVENTs schnell passieren. Wenn du dann ein kleines Timeout bei WaitForSingleObject verwendest, dann wird vermutlich alles trotzdem funktionieren, nur wenn der Fehler zuschlägt hast du nen komischen "Aussetzer" - nämlich so lange bis das Timeout abgelaufen ist.

ps: Polling und Critical-Sections vertragen sich nicht gut. Wenn der Thread der lesen will z.B. dauernd die Queue pollt, ala so

Data* d = 0;
    do
    {
        EnterCriticalSection(&m_cs);
        if (!m_queue.empty())
            d = m_queue.pop();
        LeaveCriticalSection(&m_cs);
    }
    while (d == 0);

Dann kann es LANGE dauern bis ein anderer Thread die Critical-Section locken kann, um z.B. neue Daten in die Queue zu stecken.
IIRC ging das mit Windows XP noch ganz gut, aber mit Vista wurde die Implementierung der Critical-Sections geändert. So dass der Thread der als erster "kann" die CS bekommt, und nicht der der am längsten wartet.
Und als erster "kann" der Thread der schon läuft, da das Aufwecken eines anderen, schlafenden Threads eine Zeit lang dauert.
D.h. der pollende Thread pollt fröhlich vor sich hin, während andere Threads u.U. lange lange warten müssen.

Nur falls es daran liegen sollte...

Nein, es wird weder gepollt noch gewartet. Der Consumer-Thread wird erst dann gestartet, wenn die Queue einen gewissen Füllstand hat. Sollte sie tatsächlich leerlaufen, dann wird dieser Thread einfach beendet. Es wird also weder irgend etwas signalisiert noch gewartet.

Ach ja, meine Aussetzer rühren nicht daher, dass der Thread neu gestartet wird, das würde ich im Log sehen und es würde länger als 15..25 msec dauern

hustbaer

Wobei.......
MOOOOOMENT.
15ms???
15ms kannst du unter Windows schnell mal haben. Da braucht bloss irgend ein Treiber der Meinung sein jetzt dieses oder jenes in einem DPC ausrechnen zu müssen.
Anders gesagt: wenn du Pech hast kanns du da gar nix dagegen tun.

Und selbst wenn du kein Pecht hast, wirst du deine Threads mit ausreichend hoher Priorität laufen lassen müssen. Tun sie das?

So, Problem gelöst: ich habe die Queue einfach mal durch einen selbstgeschriebenen Ringpuffer ersetzt - und siehe da das Ding rennt wie verrückt und komplett ohne Aussetzer.

Mit anderen worten: die MSVC-STL-Queue-Implementierung ist schlichtweg katastrophal ineffizent...

unskilled

Digger schrieb:

Mit anderen worten: die MSVC-STL-Queue-Implementierung ist schlichtweg katastrophal ineffizent...

glaub ich dir ohne code samt messung (und deinen ergebnissen) schlichtweg nicht.

bb

Hmm...um welche MSVC-Version geht es hier? Wenn < 2010, definier in den Projekteinstellungen der Release-Konfiguration mal _SECURE_SCL=0. Wenn gar < 2005, dann wundert es mich so oder so überhaupt nicht.

unskilled

seldon schrieb:

Hmm...um welche MSVC-Version geht es hier? Wenn < 2010, definier in den Projekteinstellungen der Release-Konfiguration mal _SECURE_SCL=0. Wenn gar < 2005, dann wundert es mich so oder so überhaupt nicht.

ist vermutlich egal, weil das in der relase-version bei so was keinen unterschied macht. oeder jedenfalls keinen so extremen...

_SECURE_SCL=0 hat auch bisher nur in performance-tests mit containern merkbare unterschiede gemacht. ich setze immernoch ziemlich viel auf den debug-mode.

std::queue ist ein Container-Adapter und setzt per Default auf std::deque auf. std::deques Laufzeitverhalten wird von _SECURE_SCL beeinflusst, und vor MSVC 2010 ist die Voreinstellung _SECURE_SCL=1. Ich wäre ziemlich überrascht, wenn das nicht durchschlüge.

hustbaer

Ein selbst geschriebener Ringpuffer kann schon viel schneller sein als ne std::deque, je nach Anwendung.
Wer z.B. ne std::deque<char> verwendet, muss sich nicht wundern, dass das mit nem selbstgewastelten Ringpuffer viel viel schneller geht.

@Digger:
Ich fände es auch interessant wie dein Code genau aussieht.
Vielleicht bekommen wir ja raus wieso die std::deque in deinem Fall so viel langsamer ist. Mich interessiert sowas immer.

unskilled schrieb:

Digger schrieb:

Mit anderen worten: die MSVC-STL-Queue-Implementierung ist schlichtweg katastrophal ineffizent...

glaub ich dir ohne code samt messung (und deinen ergebnissen) schlichtweg nicht.

Aha. Ich ersetze in einer Applikation eine std::queue durch einen Ringbuffer, die entsprechenden Funktionsaufrufe bleiben an exakt den gleichen Stellen, der restliche Code ist auch unverändert und du glaubst das nicht. Dann bitte ich dich vielmals um Entschuldigung dafür, dass die Realität etwas ergeben hat, was deine offenbar heißgeliebte Firma Microsoft ein ganz klitzeklein wenig kritisiert. Ich werde versuchen, dich nie wieder mit solcherart Fakten zu verwirren.

volkard

Digger schrieb:

Aha. Ich ersetze in einer Applikation eine std::queue durch einen Ringbuffer, die entsprechenden Funktionsaufrufe bleiben an exakt den gleichen Stellen, der restliche Code ist auch unverändert und du glaubst das nicht. Dann bitte ich dich vielmals um Entschuldigung dafür, dass die Realität etwas ergeben hat, was deine offenbar heißgeliebte Firma Microsoft ein ganz klitzeklein wenig kritisiert. Ich werde versuchen, dich nie wieder mit solcherart Fakten zu verwirren.

Nein, im Allgemeinen funktioniert das nicht. So ein new/delete schafft man doch heutzutage mit unter 200 Takten und davon muß ein paar nur alle 4096 Bytes stattfinden. Macht einen Takt pro 20 Bytes. Andere Gründe. Cache-Lokalität, Debug-Heap(!), das genannte _SECURE_SCL, Locking, falsche Zielmaschine eingestellt, kein Inlining, andere Optimierungen auch abgestellt…
Du hast irgendwelche besonderen Bedingungen vorliegen, die die queue lahm gemacht hatten. :xmas2:

Zur deque: In der STL von Visual C++ wird alle 16 Bytes eine Allokation gemacht.

#define _DEQUESIZ	(sizeof (value_type) <= 1 ? 16 \
	: sizeof (value_type) <= 2 ? 8 \
	: sizeof (value_type) <= 4 ? 4 \
	: sizeof (value_type) <= 8 ? 2 \
	: 1)	/* elements per block (a power of 2) */

Finde ich ziemlich unakzeptabel.

Ethon

Einen Ringpuffer kann man immerhin - je nach Implementierung - auch lockfree gestalten.

Ethon schrieb:

Einen Ringpuffer kann man immerhin - je nach Implementierung - auch lockfree gestalten.

AFAIK hat ein Ringpuffer eine feste Größe und ist somit praxisfremd.

Skym0sh0

hide schrieb:

Ethon schrieb:

Einen Ringpuffer kann man immerhin - je nach Implementierung - auch lockfree gestalten.

AFAIK hat ein Ringpuffer eine feste Größe und ist somit praxisfremd.

Nö muss nicht. Wenn der voll ist, kannsten ja trotzdem vergrößern.

Ethon

Lockfree wäre in erster Linie sowieso ein verlinkter Ringpuffer, praktisch eine linked-list bei der erstes und letztes Element verkettet sind. Eigentlich eine relativ übliche Implementierung einer linked-list. Lässt sich mit primitiven atomaren Operationen thread-safe halten.