fifo buffer - deque oder vector?

Hallo,

habe einen Buffer, welcher in einem Consumer/Producer Pattern als fifobuffer dient.
D.h. "vorne" wird gelesen und gelöscht, und "hinten" eingefügt.
Bisher verwende ich hier einen deque, weil das Löschen am Anfang ja hier performanter sein sollte.
Jetzt ist meine Überlegung, da es sich nur um unsigned chars handelt, einen Vector dafür zu verwenden. Dann könnte ich nämlich die Blöcke die aus und in den Buffer gehen wohl mit memcpy schreiben, was evtl. einen vorteil gegenüber std::copy bringt.

Ist std::vector hier die bessere Alternative?
Und bringt der einsatz von memcpy hier überhaupt was? (i.d.R. werden 49152 Bytes maximal gelesen, und 131073 geschrieben.)

SeppJ

Wie immer bei Performancefragen lautet die allgemeine Antwort: Ausprobieren.

Aber wenn ich abschätzen darf, was schneller sein wird: Die Deque. Die ist genau dafür da. Ich glaube nicht, dass man durch Kombination von Vector und Handarbeit etwas wesentlich besseres hinbekommt.

pumuckl

deque schrieb:

Bisher verwende ich hier einen deque, weil das Löschen am Anfang ja hier performanter sein sollte.

Also zum Aufbau von vector und deque:vector verwaltet intern ein langes Array, deque einen Satz Arrays bestimmter fester Größe, wobei das erste und letzte Array nicht voll belegt sein müssen.
Wenn du beim vector vorn ein oder mehrere Elemente rauslöscht, müssen alle anderen Elemente umkopiert und nach vorne verschoben werden genauso muss wenn du vorn was einfügst erst alles nach hinten verschoben werden.
Bei der deque ist das nicht so, hier wird, wenn das erste Array bis vorne aufgefüllt ist, einfach noch eins davorgelegt.
Vector ist also in der Performance hier deutlich schlechter.

Jetzt ist meine Überlegung, da es sich nur um unsigned chars handelt, einen Vector dafür zu verwenden. Dann könnte ich nämlich die Blöcke die aus und in den Buffer gehen wohl mit memcpy schreiben, was evtl. einen vorteil gegenüber std::copy bringt.

"Eventuell" Ist kein Argument. Vor allem dann nicht wenn du nicht weißt wie std::copy mit deque-Iteratoren zusammenarbeitet. Es ist durchaus denkbar, dass es die zu kopierende Range erst in die einzelnen kontinuierlichen Sequenzen der deque zerlegt und diese dann so performant wie memcpy kopieren kann.
So oder so ist es aber müßig, da wilde Vermutungen anzustellen und danach zu handeln, das nennt sich Premature Optimization.

Ist std::vector hier die bessere Alternative?
Und bringt der einsatz von memcpy hier überhaupt was?

Das kann dir nur einer beantworten: der Profiler. Miss nach, was in deinem speziellen Anwendungsfall performanter ist. Oder miss erstmal nach ob der Bereich mit dem rein- und rauskopieren überhaupt performancekritisch ist, sonst lohnt sich das Kopfzerbrechen eh nicht.

pumuckl schrieb:

deque schrieb:

Bisher verwende ich hier einen deque, weil das Löschen am Anfang ja hier performanter sein sollte.

Also zum Aufbau von vector und deque:vector verwaltet intern ein langes Array, deque einen Satz Arrays bestimmter fester Größe, wobei das erste und letzte Array nicht voll belegt sein müssen.
Wenn du beim vector vorn ein oder mehrere Elemente rauslöscht, müssen alle anderen Elemente umkopiert und nach vorne verschoben werden genauso muss wenn du vorn was einfügst erst alles nach hinten verschoben werden.
Bei der deque ist das nicht so, hier wird, wenn das erste Array bis vorne aufgefüllt ist, einfach noch eins davorgelegt.
Vector ist also in der Performance hier deutlich schlechter.

Das ist mir bewusst.
Nur lese ich jetzt erst aus der Datei in einen unsigned char [] buffer, um diesen dann in den buffer zu kopieren. Woraus dann später wieder in ein unsigned char */[] kopiert wird. Denke aber das das Kopieren schon recht performant ist. Hatte schon dran gedacht, direkt in den vector einzulesen, damit würde auch eine Kopie entfallen.
Bliebe nur das Problem, das das Löschen beim Vector am Anfang natürlich überhaupt nicht performant ist.

pumuckl

Die Frage ist:
- wie groß sind die Happen, die du aus der Datei in den Buffer liest? (Konstante Größe, unterschiedliche Größe?)
- wie groß sind die Happen, die du aus deinem fifo-Buffer wieder rausliest?

Wenn beides gleiche konstante größen sind, würde ich vermutlich sowas in der Art machen:

static const size_t chunk_size = 1024;
typedef std::tr1::array<unsigned char, chunk_size> chunk;
typedef std::queue<chunk, std::list<chink> > chunk_queue;

ifstream datei(datei.txt);
chunk_queue cqueue:
while (/* ...*/)
{
  chunk c;
  datei.read(chunk.c_array(), chunk_size);
  cqueue.push_back(c);
}

/* ... */
chunk c = cqueue.front(); //c.c_array() ist schon dein unsigned char[]

Warum musst du die gelesenen Bytes unbedingt loeschen?
Ein zyklischer Ringpuffer auf Basis eines Vectors waere meine Wahl gewesen.
Du schreibst dir eine Klasse die ca. so aussieht:

class MyBuf
{
private:
 std::vector<unsigned char> buffer:
 size_t start;
 size_t end;
public:
 void write( unsigned char* data, size_t length )
 {
  size_t piece_1_len = length - length % ( buffer.size() - end );

  // Erstes Stueck bis zum Ende des Puffers kopieren
  std::copy( data, data + piece_1_len, &buffer[end] );

  // Rest kopieren
  end = std::copy( data + piece_1_len, data + length, &buffer[0] ) - &buffer[0];
 }

 void read( unsigned char* data, size_t length )
 {
  size_t piece_1_len = length - length % ( buffer.size() - start );

  std::copy( &buffer[start], &buffer[ buffer.size() - 1 ], data );
  start = std::copy( &buffer[0], &buffer[ length - piece_1_len ], data + piece_1_len ) - &buffer[0];
 }
};

In der Loesung wuerdest du deine alten Daten einfach immer mit neuen ueberschreiben. Damit das funktioniert muss dein Puffer natuerlich gross genug sein, wobei es auch kein riesen Problem waere die Loesung so zu erweitern dass Sie dynamisch waechst.
Und ja, ich weiss der Code sieht furchtbar aus. Q&D!

rean

hustbaer

deque<char> ist overkill.
vector<char> als ringpuffer ist da sicher besser.

Gelesen wird wohl aus dem Buffer immer in Blöcken von 49152 Bytes, falls soviel noch im Buffer ist.

Der Consumer ist hier eine andere Library, die ich hier über eine Schnittstelle erweitere.
Lesen kann ich eigentlich aus der Datei so viel ich will, bisher ist die blockgröße 131072.

Der Ringbuffer, das wäre in der tat interessant, könnte ich mir viel sparen.
Würde das Löschen überflüssig machen und vector wäre dann optimal ausgenutzt.

hustbaer

Dann kannst du vermutlich auch gleiche eine deque<> mit 49152 Byte grossen Elementen machen, da wird ein Rinpuffer nichtmehr SO wahnsinnig viel schneller sein.
Ich dachte du willst einzelne Bytes in eine deque<char> reintun/rausnehmen.

Also bei dem Ringbuffer, solange man da einen fixed buffer nimmt, spricht eigentlich alles für ein normales array, vector bietet da keine Vorteile, oder?
Auch würde der Buffer ja dann auf dem Stack angelegt werden.

Das vector-Objekt wuerde auf dem Stack liegen aber vector speichert seine Daten intern auf dem Heap.
Natuerlich koenntest du ein normales Array auf den Stack legen, kommt halt drauf an wie gross dein Puffer sein muss. Afair ist die Stackgroesse in Win32 standardmaessig 12MB, wenn du also nen 5MB Puffer brauchst kannst du davon maximal 2 haben.

FrEEzE2046

By default ist die Stackgröße pro Thread 1 MB.

FrEEzE2046 schrieb:

By default ist die Stackgröße pro Thread 1 MB.

Stimmt, aber ich brauche sowieso nur 500kb höchstens, wird ja nie mehr als 49kb gelesen.
Allerdings, wie ist der Geschwindigkeitsunterschied zum heap?
Nutze memcpy fürs kopieren und lese mit std::istream::read direkt in den buffer.*
Ein größerer Buffer bräuchte ja weniger reads aus dem Source.

* Das erspart mir gegenüber Deque schon mal einige Kopien.

deque schrieb:

FrEEzE2046 schrieb:

By default ist die Stackgröße pro Thread 1 MB.

Stimmt, aber ich brauche sowieso nur 500kb höchstens, wird ja nie mehr als 49kb gelesen.
Allerdings, wie ist der Geschwindigkeitsunterschied zum heap?
Nutze memcpy fürs kopieren und lese mit std::istream::read direkt in den buffer.*
Ein größerer Buffer bräuchte ja weniger reads aus dem Source.

* Das erspart mir gegenüber Deque schon mal einige Kopien.

Die groesse des Puffers haengt davon ab wie schnelle dein Verbraucher im Verhaeltnis zum Erzeuger ist.
Eigentlich duerfte es zwischen Stack und Heap keinen Geschwindigkeitsunterschied geben.
Koenntest du deinen Sachverhalt in ein paar Zeilen Pseudocode beschreiben? (Verbraucher und Erzeuger getrennt voneinander)

Zugriffszeit ist auf Stack und Heap identisch, jedoch ist der Speicher auf dem Stack deutlich schneller reserviert (wenn auch begrenzt).

stumpfi schrieb:

deque schrieb:

FrEEzE2046 schrieb:

By default ist die Stackgröße pro Thread 1 MB.

Stimmt, aber ich brauche sowieso nur 500kb höchstens, wird ja nie mehr als 49kb gelesen.
Allerdings, wie ist der Geschwindigkeitsunterschied zum heap?
Nutze memcpy fürs kopieren und lese mit std::istream::read direkt in den buffer.*
Ein größerer Buffer bräuchte ja weniger reads aus dem Source.

* Das erspart mir gegenüber Deque schon mal einige Kopien.

Die groesse des Puffers haengt davon ab wie schnelle dein Verbraucher im Verhaeltnis zum Erzeuger ist.
Eigentlich duerfte es zwischen Stack und Heap keinen Geschwindigkeitsunterschied geben.
Koenntest du deinen Sachverhalt in ein paar Zeilen Pseudocode beschreiben? (Verbraucher und Erzeuger getrennt voneinander)

Pseudocode?
Mein Verbraucher ruft eine Methode readBytes(uchar* to,size_t maxread) auf.
Diese Methode liest aus dem Buffer, und der Producer schreibt dort hinein.
maxread ist (fast) immer 49152. Die Quelldatei ist im 1-500mb bereich.
Der Producer läuft in einem eigenen Thread, er soll wenn möglich den Buffer wieder auffüllen.

Mir ist noch die Idee eines Flipbuffers gekommen, in dem es 2 buffer a und b gibt. Beide Buffer haben die Größe x, (1 mb z.b.).
Anfangs werden beide gefüllt, wenn einer leer gelesen ist, wird der andere gelesen.
In der Zeit wird der erste wieder aufgefüllt. So stelle ich sicher, das ich immer in einem festen Block aus der Datei lese, und nicht in vielen kleineren Reads (von z.b. 100kb).
Bin noch am überlegen, ob dies wirklich sinnvoll wäre

FrEEzE2046

deque schrieb:

Allerdings, wie ist der Geschwindigkeitsunterschied zum heap?

Dem Prozessor ist es egal ob du Speicher aus dem Heap oder Stack kopierst. Auf dem Stack liegen u.a. lokale Variablen und die übergebenen Parameter.

Der Unterschied ist nur beim anlegen vorhanden. Wenn du statische Variablen benutzt, dann werden sie auf dem Stack bereitgestellt. Und das steht schon zur Kompilierzeit so fest.

Wenn du dynamisch Speicher allokierst, dann nimmst du dir Speicher vom Heap und hast aufm Stack lediglich die Adressbreite mit dem dein OS arbeitet.