deque oder list (logsystem)
-
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?
-
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.
-
LONG MyTrackerIndex; MY_TRACK_DATA MyTracker[1000]; VOID LogInTracker ( MY_TRACK_DATA * Data ) { LONG Index = InterlockedIncrement (&MyTrackerIndex); Index %= 1000; MyTracker[Index] = *Data; }
-
Ah, verstehe @rolling.
Hmm, soo kritisch ist es nicht.
Aber jetzt kann ich mich nicht entscheiden, deque oder ringbuffer...
-
Light schrieb:
Aber jetzt kann ich mich nicht entscheiden, deque oder ringbuffer...
Ringbuffer
-
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.
-
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.
-
Light schrieb:
Ok ich werde einen ringbuffer nehmen.
Falls du das Rad nicht neu erfinden möchtest:
Boost.Circular Buffer
-
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?
-
Daten loggen (Zahlen, viele Zahlen).
So abnormal?
-
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: 4Visual 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: 8g++: 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.
-
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.
-
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.
-
camper schrieb:
accumulate-test schrieb:
vector: 0.81543 Ticks/Elem *** -797890978***
deque: 0.874023 Ticks/Elem *** -797890978***
list: 0.810425 Ticks/Elem *** -797890978***wie erklärt ihr euch das? Oo
-
unskilled schrieb:
camper schrieb:
accumulate-test schrieb:
vector: 0.81543 Ticks/Elem *** -797890978***
deque: 0.874023 Ticks/Elem *** -797890978***
list: 0.810425 Ticks/Elem *** -797890978***wie erklärt ihr euch das? Oo
Erstmal gar nicht.
Welcher Compiler?
Ist der Fehler wiederholbar?
Ist der Release-Modus an, bzw NDEBUG definiert und -O3?
-
volkard schrieb:
ps: #ifndef __WIN32__ wäre richtig gewesen.
wie gesagt: war nur schnell hingeschrieben. War zu faul nachzuschauen, wieviele Unterstriche dieses Symbol braucht, bei gcc hatte ich es im Kopf.
Nebenbei: Die Visual C++-Version läuft unter Win XP mit einem X6800 (alle Optimierungen an)
Die g++-version unter Gentoo 64bit mit eine Q9650 @ 3.3Ghz, um die Werte grob vergleichbar zu machen, sind die nanosec-Angaben also mit 3.3 zu multiplizieren.
Aufruf mit g++ -O3 -lrt test.cppaccumulate-test schrieb:
wie erklärt ihr euch das? Oo
Das sind ca. 135 Prozessortakte bezogen auf den kompletten accumulator-Aufruf. Das ist zuwenig, als dass man das die Iteratorimplementation zurückführen könnte. Den Grund findet man mit ein wenig Forschung sicher heraus, ich würde darauf tippen, dass es damit zu tun hat, wie der jeweilige Code im Speicher ausgerichtet ist - wenn man also Tests vertauscht, ändert sich vielleicht etwas. Da versucht wird, den schnellsten Durchgang zu ermitteln, kann es jedenfalls eigentlich nicht auf kalten Cache oder ähnliches zurückzuführen sein.
Wer Spass daran hat, kann ja versuchen, das herauszufinden.
