sind stl-container in tiefer Schachtelung noch effizient?

PhilippM

Hallo,

ich möchte jetzt keine Diskussion darüber anstoßen, dass die STL performanter ist als alles, was der durchschnittliche Hobby-C++-Hacker schreiben kann, aber ich habe trotzdem eine Frage oder besser gesagt Bedenken bezüglich der Effizienz.

Durch das Template-Programmieren wird alles so bequem, dass man gar nicht mehr richtig merkt, auf was für komplexen Datentypen man mittlerweile operiert.

Bei einer template-spezifizierung ist mir jetzt aufgefallen, dass ich in einem Anwendungsfall mit einem

using std::vector;
using std::queue;
using std::pair;

queue<pair<unsigned char, vector<float> > >

arbeite, also eine queue abarbeite, die aus pairs von chars und vectoren von floats besteht.

Sind so tiefe typschachtelung in "professionellem C++" eigentlich die Regel oder ist das ne extreme Ausnahme??
Und ist sowas sehr langsam oder ist die STL wirklich so gut, dass man sich auch bei solchen verschachtelungen keinen Kopf machen muss?

Gruß,
Phil

Dravere

PhilippM schrieb:

ich möchte jetzt keine Diskussion darüber anstoßen, dass die STL performanter ist als alles, was der durchschnittliche Hobby-C++-Hacker schreiben kann, aber ich habe trotzdem eine Frage oder besser gesagt Bedenken bezüglich der Effizienz.

Soweit mir bekannt ist, ist die STL, bzw. die Standardbibliothek, so gehalten, dass man sie sehr allgemein einsetzen kann. Für spezielle Aufgaben, kann man meistens die Sache performanter machen. Aber da muss man natürlich schon ein wenig Wissen mitbringen, was aber auch ein Hobby C++ Programmierer haben kann.

PhilippM schrieb:

Sind so tiefe typschachtelung in "professionellem C++" eigentlich die Regel oder ist das ne extreme Ausnahme??

Ich hoffe du meinst das "tiefe" als Witz? Programmier mal mit Boost.Spirit, der Boost.MPL oder allgemein in der Template-Metaprogrammierung. Da erreichst du tiefe Verschachtelungen.

Ob sie eine Ausnahme sind ist eine schwere Frage, da es ganz darauf ankommt, wie man programmiert. Ein Templatefreak macht sehr viele und tiefe Typschachtelungen, ein anderer weniger

PhilippM schrieb:

Und ist sowas sehr langsam oder ist die STL wirklich so gut, dass man sich auch bei solchen verschachtelungen keinen Kopf machen muss?

Die Verschachtelung von Templates führt in erster Linie dazu, dass dein Kompiler in die Knie gezwungen wird. Allerdings noch nicht bei einem so einfachen Typen.
Langsamer wird es höchstens dadurch, dass der vector<float> kopiert werden muss. Wenn die Implementation aber gut ist, dann wird wohl ein swap eingesetzt um die Elemente nach vorne zu holen, wodurch keine wesentliche Kopie von nöten ist. Bei einer std::list wird es sogar nur ein umhängen von Zeigern sein.

Es ist daher eher unwahrscheinlich, dass der Code irgendwie langsamer werden wird. Vor allem ist die Frage, wie du es sonst lösen möchtest? Wenn du diesen Typ als Klasse implementierst, kommt es auf das gleiche raus.
Wenn du womöglich Vererbung einsetzt, dann kann es sogar langsamer werden, als die Templatelösung.

Ich würde mir darum keinen Kopf machen. Erst wenn du später merkst, dass du hier einen Performanceverlust hast, zum Beispiel dank einem Profiler, dann kannst du optimieren. Aber ich denke du wirst die Performance eher an anderer Stelle verlieren und der Bereich wird hervorragend laufen

Grüssli

volkard

PhilippM schrieb:

queue<pair<unsigned char, vector<float> > >

das ist super.

PhilippM schrieb:

Sind so tiefe typschachtelung in "professionellem C++" eigentlich die Regel oder ist das ne extreme Ausnahme??

die ausnahme. kommt aber manchmal vor.

PhilippM schrieb:

Und ist sowas sehr langsam oder ist die STL wirklich so gut, dass man sich auch bei solchen verschachtelungen keinen Kopf machen muss?

bitte mach dir einen kopf.

volkard schrieb:

vector<pair<unsigned char, queue<float> > >

das ist kacke.

wenn hier der vector wachsen muß, dann kopiert er tausende von queues, die wiederum innendrin schleifen laufen haben, die kopieren, dazu pro queue-block, der daten bekommen hat, einmal new und einmal delete. das ist eher nicht lecker.
bei deiner queue<pair<unsigned char, vector<float> > > hingegen passiert beim wachstum gar nichts schlimmees, die vectoren müssen niemals kopiert werden.

demnächst mit rvalue references entschärft sich die sache und du kannst dann eigentlich nicht mehr aus versehen eine langsame datenstruktur aus anderen zusammenbasteln, vermute ich.

Badestrand

Dravere schrieb:

Langsamer wird es höchstens dadurch, dass der vector<float> kopiert werden muss. Wenn die Implementation aber gut ist, dann wird wohl ein swap eingesetzt um die Elemente nach vorne zu holen, wodurch keine wesentliche Kopie von nöten ist. Bei einer std::list wird es sogar nur ein umhängen von Zeigern sein.

Wie kann man denn mit swap kopieren

Dravere

Badestrand schrieb:

Wie kann man denn mit swap kopieren

Das lustige an der Sache ist doch, dass man das alte Objekt nach dem Kopieren nicht mehr braucht, deshalb kann man ein swap nehmen.

Nehmen wir als triviales dummes Beispiel ein Array aus 4 Elementen:

| 1 | 2 | 3 | 4 |

Wir vernichten das erste Element.
| x | 2 | 3 | 4 | (x = zerstörtes Element)

Grundsätzlich muss nun 2 -> x, 3 -> 2, 4 -> 3 kopiert werden.
| 2 | 2 | 3 | 4 |
| 2 | 3 | 3 | 4 |
| 2 | 3 | 4 | 4 |

Statt einer Kopie, könnten wir aber auch swappen.
x mit 2, x mit 3, x mit 4 (nacheinander)
| 2 | x | 3 | 4 |
| 2 | 3 | x | 4 |
| 2 | 3 | 4 | x |

Prinzip klar?
Für einen std::vector<float> könnte so ein durchswappen sehr optimal sein, da intern womöglich nur Grösse und Zeiger getauscht werden müssten. Bei einer Kopie müssten dagegen immer alle Elemente auch kopiert werden. Von jeweiliger Speicheranforderung und Freigabe gar nicht zu sprechen.

Grüssli

Badestrand

Oha, ok, ich hatte mir irgendwie was anderes drunter vorgestellt

hustbaer

Mit C++0x wird das alles (deutlich) besser

Hi volkard,

volkard schrieb:

PhilippM schrieb:

vector<pair<unsigned char, queue<float> > >

das ist kacke.

wenn hier der vector wachsen muß, dann kopiert er tausende von queues, die wiederum innendrin schleifen laufen haben, die kopieren, dazu pro queue-block, der daten bekommen hat, einmal new und einmal delete. das ist eher nicht lecker.

Deine Bedenken kann ich sehr gut verstehen.

Ich bin zwar nur C++-Hobby-Programmierer, aber wenn ich so ein Konstrukt
brauchen würde, dann würde ich es auch so verwenden.

Dazu würde ich std::swap für den Datentyp pair<unsigned char, queue<float> >
implementieren um somit das kopieren zu verhindern.

Würde das nicht den von mir erhofften Erfolg zur Folge haben?

Gruß,
CSpille

volkard

CSpille schrieb:

Dazu würde ich std::swap für den Datentyp pair<unsigned char, queue<float> >
implementieren um somit das kopieren zu verhindern.

Würde das nicht den von mir erhofften Erfolg zur Folge haben?

nein, eher nicht. Draveres swap ist bei Draveres beispiel ok, nicht aber beim wachsen. an sich geht er ja in die richtige richtung, da wollte ich nicht widersprechen.
beim wachsen passiert was anderes.
man hat zum beispiel einen vector mit 1000 elementen. und der ist voll. push_back löst ein wachsen aus. dabei wird an einem neuen ort im ram neuer speicher für 2000 elemente angelegt. dann werden die 1000 bisherigen elemente in den neuen speicher kopiert. mit dem kopierkonstruktor. falls eine exception fliegt beim 567. element, werden die 566 kopierten elemete halt schnell wieder destruiert.
nichsdestotrotz würde was einigermaßen schnelles mit swap gehen. man prüft vor jedem push_back selber, ob noch platz ist. wachsenlassen ginge dann mit: neuen vector mit 1000 leeren queues anlegen. die 1000 elemens vom alten und neuen swappen. dann die vectoren selbst swappen. und den kleinen löschen (fallenlassen). ein vector ist niicht so kompliziert, daß man nicht einfach eine eigene klasse bauen kann, die das macht, statt den std::vector in solcher weise von außen zu managen.

volkard

CSpille schrieb:

Ich bin zwar nur C++-Hobby-Programmierer, aber wenn ich so ein Konstrukt
brauchen würde, dann würde ich es auch so verwenden.

vielleicht würde ich mich einmischen und die sagen, daß du das eben nicht brauchen würdest.

nimm doch einfach statt
vector<pair<unsigned char, queue<float> > >
eine
queue<pair<unsigned char, queue<float> > >

die zugriffszeiten der äußeren queue sind immernoch lecker schnell und die leichte verlangsamung gegenüber vector wird nochmal relativiert, weil die zugriffszeiten der inneren queue noch dazukommen und die äußere queue kann wachsen, ohne was zu kopieren. queues haben doch nen operator[] mit der zeitkomplexität O(1), wenn ich mich recht erinnere.

Hi volkard,

vielen Dank für deine nächtliche Antwort. Hab gerade völlig vergessen,
dass der Copy-Konstruktor aufgerufen wird. Hab durch die swap-Diskussion
gedacht es würde der leere Konstruktor aufgerufen und ein swap. ^^
Naja, ist halt spät

Die Datenstruktur, die ich (unbedingt) verwenden wollte, war unabhängig
von dem Beispiel. Klar kann ich in diesem Beispiel eine sinnvollere verwenden.

volkard schrieb:

queues haben doch nen operator[] mit der zeitkomplexität O(1)

Wirklich? Ich dachte es war O(n)

Dann bleibt als einzige Copy-Prevention (ohne explizite push_back-Behandlung unter
Verwendung der STL) wohl doch nur
vector<pair<unsigned char, queue<float>* > >
bzw.
vector<pair<unsigned char, queue<float> >* >
EDIT: Wenn man also einen Vektor verwenden möchte (ohne Betrachtung alternativer Strukturen)...

Gruß,
CSpille

volkard

CSpille schrieb:

volkard schrieb:

queues haben doch nen operator[] mit der zeitkomplexität O(1)

Wirklich? Ich dachte es war O(n)

queue ist nur ein adapter, drunter liegt normalerweise deque.
ich meinte natürlich deque.
und der op[] hat dabei O(1).
http://www.cplusplus.com/reference/stl/deque/operator[].html

die deque ist nämlich nicht eine doppelt verkettete liste, sondern besteht aus lauter (zum beispiel) 4096 bytes großen seiten, die vollgemacht werden und beim wachsen müssen die seiten nicht umkopiert werden. für den op[] gibt es eine zusätzliche indirektion, also nix schlimmes. und du kannst sie weitgehend verwenden, ohne dran zu denken, daß sie gar kein vector ist.

Dann bleibt als einzige Copy-Prevention (ohne explizite push_back-Behandlung unter
Verwendung der STL) wohl doch nur
vector<pair<unsigned char, queue<float>* > >
bzw.
vector<pair<unsigned char, queue<float> >* >
EDIT: Wenn man also einen Vektor verwenden möchte (ohne Betrachtung alternativer Strukturen)...

an die lösung hab ich auch gedacht, die ist aber nicht gerade exceptionsicher. nimmr man dann smart pointers rein, wird's am ende vielleicht langsamer als die deque und ist vor allem viel schlechter zu bedienen. man müßte ja die ganzen zeiger mit new bestücken.

Dravere

volkard schrieb:

man hat zum beispiel einen vector mit 1000 elementen. und der ist voll. push_back löst ein wachsen aus. dabei wird an einem neuen ort im ram neuer speicher für 2000 elemente angelegt. dann werden die 1000 bisherigen elemente in den neuen speicher kopiert. mit dem kopierkonstruktor. falls eine exception fliegt beim 567. element, werden die 566 kopierten elemete halt schnell wieder destruiert.

Sagt der Standard denn etwas dazu, dass hier der Kopierkonstruktor verwendet werden muss? Ich dachte es wäre auch korrekt, wenn die Implementierung einen swap der einzelnen Elemente ausführt. Was zur Konstruktion und Destruktion von nur sehr kleinen Objekten führt. Also grundsätzlich das, was du sagst, was man selber machen müsse.

Ich würde das grösste Problem eher in std::queue sehen. Queue ist nur ein Adapter, welcher keinen Zugriff auf den inneren Container gibt. Soweit mir bekannt ist, ist auch kein swap für std::queue vorhanden. Man muss diese Struktur somit immer kopieren.
(Bin im übrigen sowieso kein Fan von diesen Adaptern, habe den Vorteil noch nicht entdecken können)

Grüssli

volkard

Dravere schrieb:

Sagt der Standard denn etwas dazu, dass hier der Kopierkonstruktor verwendet werden muss?

nein.

Ich dachte es wäre auch korrekt, wenn die Implementierung einen swap der einzelnen Elemente ausführt. Was zur Konstruktion und Destruktion von nur sehr kleinen Objekten führt. Also grundsätzlich das, was du sagst, was man selber machen müsse.

und die version mit swap ist für PODs großer unfug. der vector müßte mit extrem spaßiger template-metaprogrammierung feststellen, ob die verwaltete klasse swap anbietet und ob das zu nehmen klug wäre. also in diesem falls feststellen: std::pair kann geswapped werden, ob's klug ist hängt aber davon ab, ob die inneren typen das mögen. drinnen sind a) unsigned char. der char mag es nicht. b) queue<float>. die mag es. die queue kann normalerweise viel mehr gewinnen als der bool verliert. also nehmen wir mal die swap-version.
ich bin sicher, daß es noch keine implemetierung der stl gibt, die sowas macht. und ich vermute, die wird es auch nie geben. sich die richtigen datenstrukturen rauszusuchen, bzw wie bei alexandrescu dem vector die grow-with-swap-policy mitzugeben, ist aufgabe des programmierers.

Ich würde das grösste Problem eher in std::queue sehen. Queue ist nur ein Adapter, welcher keinen Zugriff auf den inneren Container gibt. Soweit mir bekannt ist, ist auch kein swap für std::queue vorhanden. Man muss diese Struktur somit immer kopieren.
(Bin im übrigen sowieso kein Fan von diesen Adaptern, habe den Vorteil noch nicht entdecken können)

ich sehe da auch eher keinen vortiel. ich meinte auch die deque. deque hat swap. die queue nicht mehr, vielleicht um mehr innere container für diesen adapter zu erlauben? da wäre SFINAE wohl die wahl gewesen, und zu sagen, daß queue dann swap hat, wenn der innere container swap hat. aber das gab es damals noch nicht.

hustbaer

volkard schrieb:

die queue nicht mehr, vielleicht um mehr innere container für diesen adapter zu erlauben? da wäre SFINAE wohl die wahl gewesen, und zu sagen, daß queue dann swap hat, wenn der innere container swap hat. aber das gab es damals noch nicht.

was hat das mit SFINAE zu tun?
diese dinge löst man doch normalerweise dadurch dass man die funktion einfach implementiert -- solange sie nicht instanziert wird ist alles OK. und wenn man versucht sie zu instanzieren, dann sieht man eh ob es klappt oder nicht.

volkard

hustbaer schrieb:

was hat das mit SFINAE zu tun?
diese dinge löst man doch normalerweise dadurch dass man die funktion einfach implementiert

stimmt. das hab ich gerade verwechselt mit einem eigenen globalen swap, das mit SFINAE geschaut hat, ob die klasse eine memberswap hat und das gegebenenfalls benutzt und anderenfalls nur dreieckstausch macht. jetzt frage ich mich, warum die queue kein swap hat.

Dravere

volkard schrieb:

und die version mit swap ist für PODs großer unfug.

Hmmm, stimmt. Hab die PODs vergessen. Gibt es keine einfachere Lösung, um auch die zu berücksichtigen? *gähnende müde leere im Kopf hat*
Naja, das überleg ich mir nicht mehr um 5 Uhr morgens

volkard schrieb:

jetzt frage ich mich, warum die queue kein swap hat.

Wenn du schon dabei bist, frag gleich mal nach, wieso std::stack und std::priority_queue kein swap haben. Und ein clear wäre auch nicht schlecht. Und noch ein paar andere Dinge. Wozu sind die Dinger überhaupt gut?

Grüssli

volkard

Dravere schrieb:

volkard schrieb:

und die version mit swap ist für PODs großer unfug.

Hmmm, stimmt. Hab die PODs vergessen. Gibt es keine einfachere Lösung, um auch die zu berücksichtigen?

ich sehe keine. aber meiner meinung nach sollte c++ das nicht tun aus ideologischen gründen (sie stehen nicht im standard). c++ darf nicht erkennen, daß ich bubble-sort gebaut habe und es klammheimlich durch intro-sort ersetzen. es kann nämlich sein, daß ich die ausgefallene datenlage habe, daß ich mein telefonbuch sortiert auf platte und im ram halte und sort nach jedem neuladen aufrufe und mit dem benutzer vereinbart habe, daß er nur einträge löschen darf und neue einträge hinten an die datei anhängen darf. da ist bubblesort einfach schneller als die ganzen profi-alternativen. beim
vector<pair<unsigned char, queue<float> > >
mags ja klar sein, aber beim
vector<pair<unsigned char[8192], queue<float> > >
muß einfach der programmierer entscheiden, ob die queues gewöhnlich sehr wenige elemente haben und der POD bestimmt oder ob die queues gewöhnlich sehr viele elemente haben und swap gut ist.
darüberhinaus ist es nicht gut, bloß auf die verbrauchte zeit zu achten, manchmal ist eine langsame lösung besser, weil sie nicht ruckelt. deswegen ist die globale objektliste im 3d-spiel eine verkettete liste, die 150-mal so viel rechenzeit frißt wie der entsprechende vector. aber die liste ruckelt nicht. wenn der vector von 1000000 elementen auf 2000000 mio springt, dann steht der rechner für ein halbes sekündchen und der player ist mausetot. das mag er nicht. lieber gibt er 50€ mehr für hardware aus und nimmt die verkettete liste. hingegen muß im backup-brogramm der vector genommen werden. da will ich ein paar minuten schneller sein und ein ruckeln ist mir egal.
ich möchte keine sprache benutzen, die für mich entscheidet, ob mein programm eher ein backup-programm oder ein spiel ist. ok, wie kopiert werden soll, darf sie entscheiden, solange ich noch ein vetorecht behalte.