STL-template für FIFO?

It0101

Hi Leute

ich brauch mal eine Empfehlung, welches Template für ein FIFO am besten geeignet ist?

Die Anforderungen sind gering:

- Hinten Elemente Anhängen
- Vorn Elemente entnehmen
- Maximal mögliche Performance ( !! wichtig !! )

Zahlen & Fakten zum Einsatzgebiet:
- wenige Listenelemente ( < 20 )
- 10000 dieser Listen im Netz

Mein Problem skaliert zu nahezu 100% mit der Effizienz dieser Listen. Performance ist also das oberste Gebot. Dafür sind die sonstigen Anforderungen gering.

meine erste Idee: STL-List<...>

Jemand ne bessere Idee ?

Edit: hat jemand vielleicht einen Link, wo alle wichtigen Templates mal auf Performance untersucht wurden. Bzgl. Insert, Append, Delete, etc.... ?

Fellhuhn

std::queue

EDIT: Keine Performancevergleiche aber schau mal hier drauf: http://www.linuxsoftware.co.nz/containerchoice.png

David_pb

Queue?

Xebov

Hier stehen die Container http://cplusplus.com/reference/stl/

std::queue ist nur eine Wrapper, jenachdem was man Wählt für std::list oder std::deque.

Da du genaue Vorgaben hast und es für dich Wichtig ist könnte es sich für dich auch evtl lohnen dir nen Extra Container zu erstellen der extra auf dein Problem zugeschnitten ist.

It0101

Xebov schrieb:

Da du genaue Vorgaben hast und es für dich Wichtig ist könnte es sich für dich auch evtl lohnen dir nen Extra Container zu erstellen der extra auf dein Problem zugeschnitten ist.

ja... das war halt auch mein Gedanke. So ein FIFO-Template ist ja relativ schnell gemacht....

SeppJ

It0101 schrieb:

Xebov schrieb:

Da du genaue Vorgaben hast und es für dich Wichtig ist könnte es sich für dich auch evtl lohnen dir nen Extra Container zu erstellen der extra auf dein Problem zugeschnitten ist.

ja... das war halt auch mein Gedanke. So ein FIFO-Template ist ja relativ schnell gemacht....

Ja, aber was würdest du dabei anders/besser machen als die STL-Container?

It0101

Das wollen wir ja hier diskutieren.
Mein Template wäre vermutlich einfach schlanker, was nicht unbedingt bedeutet, dass es schneller wäre.

Ich gehe erstmal grundsätzlich nicht davon aus, dass die STL die Krone der Schöpfung ist. Ich lass mich aber von Performanceangaben gern überzeugen.
Deswegen diskutiere ich das Thema ja auch hier, weil ich geringe funktionelle Anforderungen habe,und dabei eben auf maximale Performance aus bin

Fellhuhn

Stumpf ein Array der Größe 20, ein Zeiger auf aktuelle Füllposition und aktuelle Leseposition. Fertig. Schneller geht nicht.

It0101

Fellhuhn schrieb:

Stumpf ein Array der Größe 20, ein Zeiger auf aktuelle Füllposition und aktuelle Leseposition. Fertig. Schneller geht nicht.

ich dachte gerade auch an einen ringbuffer. Da die Anzahl der Elemente anfangs steigt und dann konstant bei 20 bleibt, kann ich eine Art Ringbuffer bauen ( ich entnehme auch erst dann Elemente, wenn der Buffer voll ist , vorher ist das nicht nötig )

- Keine allokierung
- keine kopieroperationen
- nur Verschiebung der Put und Get Indizies und Umhängen von T* ( bei get und put )

Drehleiter

Eine Alternative könnte ein Ring-Puffer sein, z.B. boost::circular_buffer. Ich kann mir vorstellen, dass er u. U. für Deiné performante als die STL-Container ist.
Gruß

Xebov

SeppJ schrieb:

Ja, aber was würdest du dabei anders/besser machen als die STL-Container?

Vergiss nicht das die STL Container für allgemeinen Gebrauch gemacht wurden.

Würde auch sagen das es ein Ring Buffer hier bringen könnte.

It0101

Tataaa!

#ifndef RINGBUFFERFIFO_HPP_
#define RINGBUFFERFIFO_HPP_

#include <string.h>

// FIFO mit fester Groesse.
template <typename T>
class RingBufferFIFO
{
public:
	RingBufferFIFO( unsigned int _uiSize )
	{
		uiMaxSize = _uiSize;
		pr = pw = Buffer = new T*[ uiMaxSize ];
		pe = Buffer + uiMaxSize;

		memset( Buffer, 0, sizeof(T*) * uiMaxSize );
	}
	~RingBufferFIFO()
	{
		for ( pw = Buffer; pw != pe; delete *pw++ );
		delete [] Buffer;
	}

	bool Put( T *Item );
	T *Get();

private:
	T **Buffer, **pw, **pe, **pr;
	unsigned int uiMaxSize;
};

// Fuegt dem Buffer hinzu ein Element
template <typename T> bool RingBufferFIFO<T>::Put( T *PutItem )
{
	if ( *pw == 0 )
	{
		*pw++ = PutItem;
		if ( pw == pe )
			pw = Buffer;
		return true;
	}
	return false;
}

// Entnimmt ein Element aus dem Buffer
template <typename T> T *RingBufferFIFO<T>::Get()
{
	T *TempItem = *pr;
	*pr++ = 0;
	if ( pr == pe )
		pr = Buffer;
	return TempItem;
}

#endif /* RINGBUFFERFIFO_HPP_ */

Edit: Bug gefixed...

It0101

schlagt mich tot, wegen STL-Ignorierung, aber ich find das template geil ^^ ( noch kürzer hab ichs leider nicht hinbekommen )

PS: ich liebe das Pointergeschubse ( das Ding hat übrigens keine Memory-Leaks ^^ )

Th69

Deine Get-Funktion ist aber fehlerhaft. Versuch mal, mehrmals hintereinander etwas zu entfernen...

Schau mal bei Wikipedia: http://de.wikipedia.org/wiki/Warteschlange_(Datenstruktur)

knivil

Es ist unvollstaendig, sehr unvollstaendig! Wie sehen die Zugriffsfunktionen aus? Wie kann ich mittels Iterator sortieren?

( das Ding hat übrigens keine Memory-Leaks ^^ )

Das kommt darauf an, wie Ringbuffer verwendet wird. Auch werden andere Bugs provoziert, insbesondere weil nicht geklaert ist, wer der Eigentuemer der Objekte ist, auf die im Buffer gezeigt wird.

ich liebe das Pointergeschubse

Ich haette die Zugriffe ueber Indizes mitels modulo realisiert.

It0101

du hast recht... ich kümmer mich gleich drum - schlampig getestet

It0101

knivil schrieb:

Es ist unvollstaendig, sehr unvollstaendig!

es kann genau die Funktionen, die ich benötige. Wenn ich Overhead gewollt hätte, hätte ich auch ein STL-Template nehmen können.

knivil schrieb:

Wie sehen die Zugriffsfunktionen aus?

Put und get, mehr ist nicht nötig

knivil schrieb:

Wie kann ich mittels Iterator sortieren?

garnicht, weil ich das nicht brauch.

knivil schrieb:

Das kommt darauf an, wie Ringbuffer verwendet wird. Auch werden andere Bugs provoziert, insbesondere weil nicht geklaert ist, wer der Eigentuemer der Objekte ist, auf die im Buffer gezeigt wird.

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Übrigens bin ich der festen Überzeugung, dass dieses Template von der Performance her die allgemeiner gefassten STL-Templates schlägt.

knivil

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:

for ( p = Buffer; p != pe; delete *p++ );

Übrigens bin ich der festen Überzeugung, dass dieses Template von der Performance her die allgemeiner gefassten STL-Templates schlägt.

Es zaehlen aber nur Messergebnisse, keine Ueberzeugungen. Ich lasse mich gern eines besseren belehren, wenn du einen Benchmark postest, so dass ich ihn auf meiner lokalen Maschine testen kann.

It0101

knivil schrieb:

Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:
for ( p = Buffer; p != pe; delete *p++ );

Diese Zeile löscht das Element, weil ich sonst vom Eigentümer verlangen müsste, den Buffer mit "get" komplett zu entleeren.
Hat schlicht und ergreifend praktische Gründe.

Das Template hat im Gegensatz zur STL nicht den Anspruch der allgemeinen Verwendbarkeit. Es ist für mich und im Dienste der maximalen Performance entwickelt.

It0101

knivil schrieb:

Es zaehlen aber nur Messergebnisse, keine Ueberzeugungen. Ich lasse mich gern eines besseren belehren, wenn du einen Benchmark postest, so dass ich ihn auf meiner lokalen Maschine testen kann.

Die werde ich nachliefern.
g++ auf Linux, wenns recht ist.

It0101 schrieb:

knivil schrieb:
Üblicherweise der, der sie erzeugt hat. Und das ist bei mir nicht anders.

Diese Zeile sagt was anderes:
for ( p = Buffer; p != pe; delete *p++ );
Diese Zeile löscht das Element, weil ich sonst vom Eigentümer verlangen müsste, den Buffer mit "get" komplett zu entleeren.

Aber damit ist nicht mehr klar, wer der Eigentümer ist.

It0101 schrieb:

Hat schlicht und ergreifend praktische Gründe.

Praktisch ist es eben genau nicht. Kann man sehr leicht aufzeigen:

// in irgendeinem Block
{
  RingBufferFIFO<int> buffer(20);

  // ... irgendwo im nirgendwo passt der Programmierer nicht richtig auf,
  // da er sich nicht mehr recht erinnert, dass RingBufferFIFO jeglichem
  // Eigentümer Standard widerspricht.
  int agreatvalue = 256;
  buffer.Put(&agreatvalue);

  // ... viel später, aber agreatvalue ist noch im Puffer.
} // <- BAMMMMM; BUMMM; WELTUNTERGANG ... naja nicht so extrem, aber eben nicht praktisch.

Grüssli