deque oder list (logsystem)

[Light]

Hi!

Ist eigentlich eine deque oder eine list schneller im Anlegen von Elementen am Anfang/Ende?
Oder ist das gleich?

Ein Logsystem soll zB. 1000 Einträge speichern, wenn ein neuer dazukommt, soll der älteste hinten gelöscht und der neue vorne drangehängt werden.

Für sowas ist doch eigentlich deque gedacht, oder geht es da nur um den random access, den ich allerdings nicht brauche?

(Btw. wie macht es eine deque eigentlich intern, wenn sie doch random access hat, aber trotzdem alle Elemente eigentlich immer verschiebt (wenn man vorne was dranhängt?), das kann doch nicht performant sein)

Danke schonmal

[volkard]

Wahrscheinlich ist deuque schneller, weil sie für einen string nur einmal new für die nutzdaten braucht, während eine normale verkettet liste einmal new für den knoten und einmal new für die nutzdaten braucht.
deque legt 4096 bytes große "seiten" an, und wächst, wenn eine seite voll ist, indem mit new eine neue seite dazugekauft wird.

[unskilled]

Ein Logsystem soll zB. 1000 Einträge speichern, wenn ein neuer dazukommt, soll der älteste hinten gelöscht und der neue vorne drangehängt werden

So was klingt mir aber eher nach nem ringpuffer...

bb

[SeppJ]

unskilled schrieb:

So was klingt mir aber eher nach nem ringpuffer...

Und somit wäre dann auch die 2te Frage des Threaderstellers geklärt, wie eine deque effektiv das Verschieben implementieren kann. Nämlich gar nicht, sondern es werden nur ein paar Zeiger verschoben. Es gibt aber auch andere Möglichkeiten sowas umzusetzen, weiß nicht, was deque intern verwendet.

[unskilled]

SeppJ schrieb:

unskilled schrieb:

So was klingt mir aber eher nach nem ringpuffer...

Und somit wäre dann auch die 2te Frage des Threaderstellers geklärt, wie eine deque effektiv das Verschieben implementieren kann. Nämlich gar nicht, sondern es werden nur ein paar Zeiger verschoben. Es gibt aber auch andere Möglichkeiten sowas umzusetzen, weiß nicht, was deque intern verwendet.

hat volkard doch schon beantwortet...
wenn vorn / hinten eine neue seite gebraucht wird, wird sie angefordert
und wenn vorn / hinten eine komplette seite leer ist, kann die wieder freigegeben werden...

bb

[camper]

Eine deque verschiebt keine Elemente, wenn am Anfang oder Ende eingefügt wird.
Daraus folgt, dass es sich intern nicht, wie bei vector, um ein einzelnes Array handeln kann. Haben wir es mit mehreren Datenfragmenten zu tun, müssen diese geeignet verknüpft werden, da amortisiert konstante Navigationszeiten gebraucht werden, bleibt hier nicht viel anderes übrig als eine Hashmap. Aus Effizienzgründen werden allerdings normalerweise mehrere aufeinanderfolgende Datenelemente in einem Array zusammengefasst. Damit ist auch der große Nachteil von deque klar: die Iteratoren sind langsam und vergleichsweise groß. Ob das bei dem genannten Einsatzzweck eine Rolle spielt, sei dahingestellt, ein Ringpuffer dürfte hier allerdings für gewöhnlich sinnvoller sein.

[volkard]

camper schrieb:

Damit ist auch der große Nachteil von deque klar: die Iteratoren sind langsam und vergleichsweise groß.

Langsam glaube ich eher nicht. Innerhalb der 4096 bytes großen Seite gehts eigentlich ratz fatz. Immer nur beim Seitenwechsel muß mal überlegt werden.

_Self&
      operator++()
      {
	++_M_cur;
	if (_M_cur == _M_last)
	  {
	    _M_set_node(_M_node + 1);
	    _M_cur = _M_first;
	  }
	return *this;
      }

Also im Normalfall ein Zeiger++ und ein if, das nichts tut und eh richtig predicted wurde.

Aber mit der Größe hast Du recht, die sind riesig.

cout<<sizeof(void*)<<'\n';
	cout<<sizeof(std::vector<int>::iterator)<<'\n';
	cout<<sizeof(std::deque<int>::iterator)<<'\n';

4
4
16

[camper]

volkard schrieb:

Langsam glaube ich eher nicht.

Sicherlich nicht schneckentempo-langsam, aber doch erheblich im Vergleich zu den Iteratoren anderer Container.

volkard schrieb:

Innerhalb der 4096 bytes großen Seite gehts eigentlich ratz fatz.

Existiert wirklich eine Implementation die derart riesige Bouquets für normalgroße Objekte verwendet?
Visual C++ etwa macht es so

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

max. 16-byte Blöcke, oder eine Element pro Block (ist allerdings auch wahrscheinlich nicht die beste existierende Implementation für deque...)
Bei g++ sind es, wenn ich das richtig sehe, 512 byte.

volkard schrieb:

Immer nur beim Seitenwechsel muß mal überlegt werden.

Und wenn der Seitenwechsel selbst sehr teuer ist, bleiben im Durchschnitt trotzdem erhöhte Kosten stehen. Zudem ist denkbar, dass random-access auch mal ausgenutzt wird, was die zahl der Seitenwechsel erhöhen dürfte: bei einem sort etwa dürfte es wehtun. Aber das sind alles theoretische Überlegungen, wie immer geht nichts über eine Messung.
Soll ich was schreiben oder hast du einen fertigen Benchmark in der Schublade?

[volkard]

camper schrieb:

Existiert wirklich eine Implementation die derart riesige Bouquets für normalgroße Objekte verwendet?
Visual C++ etwa macht es so

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

max. 16-byte Blöcke, oder eine Element pro Block.

GCC nimmt wohl 512 Bytes große Seiten. 4096 könnte bei einer alten Verion von MSVC gewesen sein, irgenwo hab ich's mal im Debugger gehabt.

inline size_t
  __deque_buf_size(size_t __size)
  { return __size < 512 ? size_t(512 / __size) : size_t(1); }

camper schrieb:

bei einem sort etwa dürfte es wehtun. Aber das sind alles theoretische Überlegungen, wie immer geht nichts über eine Messung.

Ich hatte mal einen Wissenschaftlichen Artikel über's Sortieren gelesen und da schnitt deqeue mit dem op[] gar nicht schlecht ab.

Soll ich was schreiben oder hast du einen fertigen Benchmark in der Schublade?

Ich hab nix.

[rolling]

LONG MyTrackerIndex;
MY_TRACK_DATA MyTracker[1000];

VOID 
LogInTracker (
	MY_TRACK_DATA * Data
	) 
{
	LONG Index = InterlockedIncrement (&MyTrackerIndex);
	Index %= 1000;
	MyTracker[Index] = *Data;
}

[Light]

Ah, verstehe @rolling.

Hmm, soo kritisch ist es nicht.

Aber jetzt kann ich mich nicht entscheiden, deque oder ringbuffer...

[volkard]

Light schrieb:

Aber jetzt kann ich mich nicht entscheiden, deque oder ringbuffer...

Ringbuffer

[eee]

Light schrieb:

Hi!

Ist eigentlich eine deque oder eine list schneller im Anlegen von Elementen am Anfang/Ende?
Oder ist das gleich?

Ein Logsystem soll zB. 1000 Einträge speichern, wenn ein neuer dazukommt, soll der älteste hinten gelöscht und der neue vorne drangehängt werden.

Für sowas ist doch eigentlich deque gedacht, oder geht es da nur um den random access, den ich allerdings nicht brauche?

(Btw. wie macht es eine deque eigentlich intern, wenn sie doch random access hat, aber trotzdem alle Elemente eigentlich immer verschiebt (wenn man vorne was dranhängt?), das kann doch nicht performant sein)

wenn es wirklich so schnell sein muss, was ich ja irgendwie bezweifle, dann solltest du besser beim Einfügen keine Kopien der Strings machen, was std::liststd::string aber macht.

[Light]

Ok ich werde einen ringbuffer nehmen.

Ne, @eee, es werden eigentlich char-arrays geloggt, in meinem Fall dann wohl:

unsigned char data[100][32]; // 100 Einträge max., jeweils 32 Byte

Alles easy, thx.

[Nexus]

Light schrieb:

Ok ich werde einen ringbuffer nehmen.

Falls du das Rad nicht neu erfinden möchtest:
Boost.Circular Buffer

[eee]

Jetzt bezweifle ich noch mehr, dass die wahl des passenden containers dein größtes Problem ist. Was soll denn das für ein logsystem sein, bei dem man solche arrays speichert?

[Light]

Daten loggen (Zahlen, viele Zahlen).
So abnormal?

[camper]

Ohne Anspruch hingeschrieben:

#define _SECURE_SCL 0

#include <numeric>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <time.h>
#include <ctime>
typedef unsigned long long u64;
#ifdef __GNUC__
#include <sched.h>
u64 get_ticks()
{
	timespec t;
	clock_gettime(CLOCK_REALTIME,&t);
	return t.tv_sec*1000000000ll+t.tv_nsec;
}
int init()
{
    cpu_set_t mask;
    CPU_ZERO( &mask );
    CPU_SET( 1, &mask );
    sched_setaffinity( 0, sizeof(mask), &mask );
	sleep(1);
}

#else
#include <windows.h>

u64 get_ticks()
{
	LARGE_INTEGER t;
	QueryPerformanceCounter(&t);
	return t.QuadPart;
};

int init()
{
	SetProcessAffinityMask(GetCurrentProcess(),1);
	Sleep(1);
	return 0;
}
#endif
int foo=init();

const int count = 1000;
template <typename T, int Size>
struct Foo
{
	typedef T value_type;
	static const int size = Size;
	union
	{
		T data;
		char dummy[size];
	};
	Foo(int x=0) : data(x) {}
	Foo(const Foo& other) : data(other.data) {}
	Foo& operator=(const Foo& other) { data = other.data; return *this; }
	static Foo acc;
};
template <typename T, int Size>
Foo<T,Size> Foo<T,Size>::acc;

template <typename T, int Size>
bool operator<(const Foo<T,Size>& lhs, const Foo<T,Size>& rhs) { return lhs.data < rhs.data; }
template <typename T, int Size>
bool operator==(const Foo<T,Size>& lhs, const Foo<T,Size>& rhs) { return lhs.data == rhs.data; }
template <typename T, int Size>
T operator+(const Foo<T,Size>& lhs, const Foo<T,Size>& rhs) { return lhs.data + rhs.data; }
#define MEASURE(result,op)             \
	{                                  \
		result = ~0ull;                \
		for ( int i = count; --i; )    \
		{                              \
			type::acc=0;               \
			u64 t = get_ticks();       \
			op;                        \
			t = get_ticks() - t;       \
			if ( t < result )          \
			{                          \
				result = t;            \
				i = count;             \
			}                          \
		}                              \
	}
#define MEASURE2(result,op,initop,endop) \
	{                                    \
		result = ~0ull;                  \
		for ( int i = count; --i; )      \
		{                                \
			initop;                      \
			type::acc=0;                 \
			u64 t = get_ticks();         \
			op;                          \
			t = get_ticks() - t;         \
			if ( t < result )            \
			{                            \
				result = t;              \
				i = count;               \
			}                            \
			endop;                       \
		}                                \
	}

template <typename T, int Size>
void measure(T* init, std::size_t size)
{
	typedef Foo<T,Size> type;
	std::cout << "****************************\n"
			  << "Objektgroesse: " << sizeof(type) << '\n';
	{
		std::cout << "accumulate\n";
		u64 time;
		std::vector<type> v(init,init+size);
		MEASURE(time,(type::acc=std::accumulate(v.begin(),v.end(),type::acc)));
		std::cout << "vector: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		std::deque<type> d(init,init+size);
		MEASURE(time,(type::acc=std::accumulate(d.begin(),d.end(),type::acc)));
		std::cout << "deque: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		std::vector<type> l(init,init+size);
		MEASURE(time,(type::acc=std::accumulate(l.begin(),l.end(),type::acc)));
		std::cout << "list: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
	}
	{
		std::cout << "find\n";
		u64 time;
		std::vector<type> v(init,init+size);
		MEASURE(time,(type::acc=*std::find(v.begin(),v.end(),v.back())));
		std::cout << "vector: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		std::deque<type> d(init,init+size);
		MEASURE(time,(type::acc=*std::find(v.begin(),v.end(),v.back())));
		std::cout << "deque: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		std::vector<type> l(init,init+size);
		MEASURE(time,(type::acc=*std::find(v.begin(),v.end(),v.back())));
		std::cout << "list: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
	}
	{
		std::cout << "sort\n";
		u64 time;
		MEASURE2(time,(std::sort(v.begin(),v.end())),std::vector<type> v(init,init+size),(type::acc=type::acc+v.front()));
		std::cout << "vector: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		MEASURE2(time,(std::sort(d.begin(),d.end())),std::deque<type> d(init,init+size),(type::acc=type::acc+d.front()));
		std::cout << "deque: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
		MEASURE2(time,(l.sort()),std::list<type> l(init,init+size),(type::acc=type::acc+l.front()));
		std::cout << "list: " << time/(double)size << " Ticks/Elem *** " << type::acc.data << "***\n";
	}
}

int main()
{
	const int size = 8192;
	int init[size] = {};
	std::srand(std::time(0));
	for ( int i = 0; i < size; ++i )
		init[i] = std::rand();
	measure<int,4>(init,size);
	measure<int,8>(init,size);
	measure<int,16>(init,size);
	measure<int,32>(init,size);
	measure<int,64>(init,size);
	std::cout << "************************"
			  << "\nvoid*:            " << sizeof (void*)
		      << "\nvector::iterator: " << sizeof (std::vector<int>::iterator)
		      << "\ndeque::iterator:  " << sizeof (std::deque<int>::iterator)
			  << "\nlist::iterator:   " << sizeof (std::list<int>::iterator) << std::endl;
}

Folgende Schlussfolgerungen scheinen erlaubt:

Visual C++ schrieb:

Objektgroesse: 16
accumulate
vector: 2.39685 Ticks/Elem *** 134044258***
deque: 10.0802 Ticks/Elem *** 134044258***
list: 2.39819 Ticks/Elem *** 134044258***
sort
vector: 190.106 Ticks/Elem *** 1***
deque: 679.37 Ticks/Elem *** 1***
list: 424.543 Ticks/Elem *** 1***
************************
void*: 4
vector::iterator: 4
deque::iterator: 8
list::iterator: 4

Visual C++: normales Vorwärtsiterieren ist bei deque erheblich langsamer als bei vector und list, das Mißverhältnis ist nocheinmal größer bei zufälligen Zugriffen. deque-Iteratoren haben die Größe von zwei Zeigern, gegenüber jeweils einem zeiger bei vector und list.

g++ schrieb:

Objektgroesse: 16
accumulate
vector: 0.81543 Ticks/Elem *** -797890978***
deque: 0.874023 Ticks/Elem *** -797890978***
list: 0.810425 Ticks/Elem *** -797890978***
sort
vector: 45.771 Ticks/Elem *** 236175***
deque: 59.0277 Ticks/Elem *** 236175***
list: 102.196 Ticks/Elem *** 236175***
************************
void*: 8
vector::iterator: 8
deque::iterator: 32
list::iterator: 8

g++: Vorwärtsiterieren ist etwa genauso schnell wie bei vector und list, bei randomaccess besteht wiederum ein Nachteil. Das wird mit Iteratorgröße erkauft, die beträgt hier 4 Zeiger.

Absolut aussagekräftig ist der Test nicht, z.B. wird nicht die in realen Systemen auftretende Fragmentierung von list und deque berücksichtigt, die bei diesen zusätzliche Performance kosten dürfte.

[SeppJ]

Und für alle die es interessiert: Beim compiliert man campers Testprogramm mit dem neuesten intel Compiler, so bekommt man fast das gleiche Ergebnis wie beim g++. Deque schneidet einen Tacken schlechter ab, aber nur 1-2% langsamer als beim gcc - bei meinen drei Messungen bin ich mir nicht sicher, ob dies signifikant ist.

[volkard]

ps: #ifndef __WIN32__ wäre richtig gewesen.

Jo, Deine Messungen passen zu dem, was ich in Erinnerung habe. [] ungefähr dreimal lahmer. Durchiterieren ungefähr gleich. Deine Messungen für MS sagen, daß man sich nötigenfalls besser eine eigene deque baut, wenn man die Geschwindigkeit braucht. Nicht wirklich überraschend. Erfreut bin ich, daß op[] gar nicht dreimal lahmer ist, sondern nur 50% lahmer.

Und auf alle Fälle alles noch wahnsinnig schnell. Sobald Daten auch angefaßt werden und was einigermaßen sinnvolles getan wird, isses völlig unerheblich.