Effiziente konstante Warteschlange
-
Ich habe gehört dass die std::queue nicht sehr effizient sei. Da ich eine Warteschlange mit konstanter Anzahl an Plätzen brauche kann ich mir gut vorstellen, dass eine queue hierfür zu ineffizient ist, da sie beliebig viele Elemente aufnehmen kann (mehr Verwaltungsaufwand).
Meine Warteschlange soll als Puffer für zwei Threads dienen die sich darüber Elemente schicken sollen (eigentlich nur Zeiger auf Objekte). Das soll sehr schnell geschehen. Nur einer ist der Erzeuger und der andere der Verbraucher, also nur unidirektional. Wie gesagt reicht eine konstante Anzahl an Plätzen, der Erzeuger hängt Elemente rein und der Verbraucher holt sie raus. Würdet ihr das mit einem vector machen? Kann man die Warteschlange so bauen dass man kein Locking braucht? Oder wie kann man das Locking möglichst minimieren?
Dann wäre da noch eine ganz spezielle Funktion, von der ich wissen will ob sie das ganze ineffizient machen würde: Die Zeiger in der Warteschlange veralten, das heißt neuere sind wichtiger als ältere. Deshalb wäre es wünschenswert, dass wenn die Schlange voll ist und der Produzent ein weiteres Element einstellen will, das älteste beim Verbraucher "rausfällt" und alle eins nach vorne rücken, sodass hinten Platz wird.
-
deine zweite Forderung klingt nach einem Ringpuffer, wie der von Boost. Dort kannst du auch eine feste Anzahl an Elementen speichern und die ältesten werden rausgeschmissen, wenn ein neues dazukommt und der speicher voll ist.
-
-
Ich glaube fast, ich würde die Zeiger in eine Pipe stopfen. Da ist das ganze Erzeuger-Verbraucher-Gesychronieriere dann gleich mit dabei.
-
Richtig, es ist ein Ringpuffer! Das kam mir auch bald nach dem Thema. Aber nach nochmaligem Überlegen stellte sich der Ringpuffer als doch nicht nötig raus.
Das ganze ist so: Ich will die Speicherflächen recyceln. Dazu hat der Verbraucher eine Eingangs und Ausgangsschlange für Zeiger. Der Erzeuger gibt Zeiger auf neue Objekte in die Eingangsschlange wo sie der Verbraucher raus holt. Hat er sie verbraucht hängt er sie um in die Ausgangsschlange, wo sie wieder der Erzeuger abholt und recyclt.Wie meinst du das volkard? Pipes nimmt man doch nur bei Prozesses, ich verwende hier Threads. Ich dachte ich lasse den Verbraucher einfach so lange laufen wie Zeiger in der Eingangsschlange sind. Sind keine mehr drin dann wartet er mit wait auf eine Einlierung - dazu braucht man dann eine cond?
-
fabske schrieb:
Wie meinst du das volkard? Pipes nimmt man doch nur bei Prozesses, ich verwende hier Threads.
Die Pipe ist einfach das Muster was angewandt wird - quasi Consumer-Producer mit einem Buffer dazwischen. Ob die Pipe jetzt eine endliche Maximalgröße hat oder sich dynamisch vergrößern lässt, oder ob sie zwischen Threads oder Prozessen hängt und wie sie implementiert ist (z.B. queue für dynamische, Ringpuffer für fixe Größe) ist alles nur ein Designdetail. Eine Pipe bleibts trotzdem.
-
pumuckl schrieb:
fabske schrieb:
Wie meinst du das volkard? Pipes nimmt man doch nur bei Prozesses, ich verwende hier Threads.
Die Pipe ist einfach das Muster was angewandt wird - quasi Consumer-Producer mit einem Buffer dazwischen. Ob die Pipe jetzt eine endliche Maximalgröße hat oder sich dynamisch vergrößern lässt, oder ob sie zwischen Threads oder Prozessen hängt und wie sie implementiert ist (z.B. queue für dynamische, Ringpuffer für fixe Größe) ist alles nur ein Designdetail. Eine Pipe bleibts trotzdem.
Aha, und was meinte er damit "Erzeuger-Verbraucher-Gesychronieriere"
-
volkard belieben zu scherzen.
er meint eine windows pipe (EDIT: oder doch nicht?), und die ist wohl so ziemlich das langsamste was man hier nehmen kann.@fabske:
lock-free ginge vermutlich schon, bloss eher kompliziert und fehleranfällig. verwende einfach locks, wird vermutlich schnell genug sein.was die umsetzung der queue angeht: verwende nen std::vector als basis, und bau nen ring-puffer draus. dadurch muss nie viel im vector rumkopiert werden.
wenn die queue recht klein ist, würde ich einfach nur nen vector nehmen. ein paar zig zeiger rumkopieren geht ja schnell genug.
