[gelöst] Heap verliert scheinbar grundlos seinen Inhalt

Der std::vector speichert ganze drei Pointer ab (begin, end, endofstorage) und unnötigerweise noch einen Allokator.

Und auch wenn man am Anfang reserve() macht und mit höchsten Compileroptimierungen übersetzt; push_back bleibt immer ein ungeinlineter Funktionsaufruf, der ein inkrementieren des end-Pointers mit sich bringt. Der muss von meinem Code auch noch gespeichert werden (ich muss eine for-loop über int machen anstatt T*). Höchst ineffizient. Wenn ich resize() nehme, werden POD-Konstruktoren aufgerufen.

std::vector<> ist unvertretbar schlecht für sehr viele kleine Arrays mit konstanter Grösse und nachteilig für grössere push_back-Geschichten. Dein "kostet nichts" ist übertrieben.

SeppJ

keksfresser schrieb:

Der std::vector speichert ganze drei Pointer ab (begin, end, endofstorage) und unnötigerweise noch einen Allokator.

Du willst über Optimierung diskutieren und kennst nicht einmal Empty Base Optimization?

Und auch wenn man am Anfang reserve() macht und mit höchsten Compileroptimierungen übersetzt; push_back bleibt immer ein ungeinlineter Funktionsaufruf, der ein inkrementieren des end-Pointers mit sich bringt.

Wieso ungeinlined? Wieso wäre das bei einem selbstverwalteten Array anders? Da musst du auch wissen, wo das Ende ist.

std::vector<> ist unvertretbar schlecht für sehr viele kleine Arrays mit konstanter Grösse und nachteilig für grössere push_back-Geschichten. Dein "kostet nichts" ist übertrieben.

Warum solte man vector fur Arrays konstanter Größe nehmen? Da würdest du ja auch kein new[] nehmen. Deine Aussagen sind solche Blödsinn, dass ich bei einem Unregisitrierten annehmen muss, dass du nur trollen möchtest.

TyRoXx

keksfresser schrieb:

Der std::vector speichert ganze drei Pointer ab (begin, end, endofstorage) und unnötigerweise noch einen Allokator.

Der Allocator kann von einem schlauen Compiler weggelassen werden.
Das doppelte Ende ist eine Optimierung für push_back , der eine Zeiger ist aber verschmerzbar, wenn man ihn nicht braucht. Macht in der Praxis einfach keinen Unterschied ob der nun da ist oder nicht. Das wäre eine Mikrooptimierung, die in der Messungenauigkeit untergeht.

Ich muss aber zugeben, dass vector damit nicht ganz dem C++ Prinzip entspricht, dass man nur das bezahlt, was man auch benutzt. Übersehe ich etwas oder fehlt da wirklich ein Container für ein dynamisches Array garantiert ohne push_back -Optimierung?
Ein Kompromiss ist unique_ptr<T []> : Kein Komfort, aber wenigstens kein Leak.

keksfresser schrieb:

Und auch wenn man am Anfang reserve() macht und mit höchsten Compileroptimierungen übersetzt; push_back bleibt immer ein ungeinlineter Funktionsaufruf, der ein inkrementieren des end-Pointers mit sich bringt. Der muss von meinem Code auch noch gespeichert werden (ich muss eine for-loop über int machen anstatt T*). Höchst ineffizient. Wenn ich resize() nehme, werden POD-Konstruktoren aufgerufen.

Was hat push_back jetzt damit zu tun?
Das mit der Schleife ergibt keinen Sinn.
new[] ruft doch auch den Standardkonstruktor auf? push_back ruft hingegen gar keinen Standardkonstruktor auf.

keksfresser schrieb:

std::vector<> ist unvertretbar schlecht für sehr viele kleine Arrays mit konstanter Grösse und nachteilig für grössere push_back-Geschichten.

Konstante Größe? Joa, da nimmt man array .
Das tolle an vector ist ja gerade, dass er perfekt für " push_back -Geschichten" ist. Du hast einfach nur keine Ahnung.

keksfresser schrieb:

Dein "kostet nichts" ist übertrieben.

Dein "kostet was" ist nicht nur übertrieben, sondern aus der Luft gegriffen.

Falls der Beitrag als Scherz gemeint war, bitte nächstes Mal irgendeinen Hinweis auf Ironie hinterlassen.

SeppJ schrieb:

keksfresser schrieb:

Der std::vector speichert ganze drei Pointer ab (begin, end, endofstorage) und unnötigerweise noch einen Allokator.

Du willst über Optimierung diskutieren und kennst nicht einmal Empty Base Optimization?

Gut, lass den Allokator weg. Es bleibt der Overhead von einem Pointer.

Wieso wäre das bei einem selbstverwalteten Array anders? Da musst du auch wissen, wo das Ende ist.

Irgendwie muss ich dem Vektor sagen, wie gross er sein soll. vec.resize(n). Dann speichere ich n *und* das Ende ab; Nochmals overhead von einem Pointer.

Deine Aussagen sind solche Blödsinn, dass ich bei einem Unregisitrierten annehmen muss, dass du nur trollen möchtest.

Deine Sprech ist solche Fehler, dass ich bei einem Modirerator annehmen.

TyRoXx schrieb:

Ich muss aber zugeben, dass vector damit nicht ganz dem C++ Prinzip entspricht, dass man nur das bezahlt, was man auch benutzt. Übersehe ich etwas oder fehlt da wirklich ein Container für ein dynamisches Array garantiert ohne push_back -Optimierung?
Ein Kompromiss ist unique_ptr<T []> : Kein Komfort, aber wenigstens kein Leak.

Jupp, Punkt für new.

new[] ruft doch auch den Standardkonstruktor auf?

Nein, tuts nicht. new[] () macht das.

keksfresser schrieb:

Falls der Beitrag als Scherz gemeint war, bitte nächstes Mal irgendeinen Hinweis auf Ironie hinterlassen.

Ne, der Grund war zu tollen.

314159265358979

Vielleicht sollte man erst einmal sagen, wann man vector besser nicht (bzw nicht direkt) verwenden sollte. Wenn ich ein Array fester Größe brauche, diese aber erst zur Laufzeit feststeht, ist vector, sagen wir mal, suboptimal, durch die zusätzlichen Verwaltungsdaten. Bei einer Dimension ist das ganze nicht wirklich schlimm, aber spätestens bei 3 Dimensionen fallen die Verwaltungsdaten besonders bei kleinen Arrays ins Gewicht. Auch sind 3 geschachtelte Vektoren nicht gerade Cache-freundlich und somit langsam.

Bei mehr als 1 Dimension würde ich den vector in eine Klasse stecken, die mir die Elemente auf ein 1-dimensionales Array mappt, bzw wenn die Größe zur Laufzeit konstant bleibt, würde ich unique_ptr<T[]> wrappen, um noch ein paar Bytes rauszuholen.

TyRoXx

keksfresser schrieb:

new[] ruft doch auch den Standardkonstruktor auf?

Nein, tuts nicht. new[] () macht das.

Mein Compiler tut das und selbst wenn er es nicht täte, wäre das ein Argument gegen new[] . Was will man denn mit einer Folge nicht initialisierter Objekte?

314159265358979 schrieb:

Vielleicht sollte man erst einmal sagen, wann man vector besser nicht (bzw nicht direkt) verwenden sollte. Wenn ich ein Array fester Größe brauche, diese aber erst zur Laufzeit feststeht, ist vector, sagen wir mal, suboptimal, durch die zusätzlichen Verwaltungsdaten.

Hallo? Es geht hier um einen Zeiger pro vector -Instanz. Schreib für deine Bedürfnisse einen Container, der mit zwei Zeigern auskommt, aber vergiss den unique_ptr -Hack.

314159265358979 schrieb:

Bei einer Dimension ist das ganze nicht wirklich schlimm, aber spätestens bei 3 Dimensionen fallen die Verwaltungsdaten besonders bei kleinen Arrays ins Gewicht. Auch sind 3 geschachtelte Vektoren nicht gerade Cache-freundlich und somit langsam.

Niemand, der bei Trost ist, würde das so implementieren.

314159265358979 schrieb:

Bei mehr als 1 Dimension würde ich den vector in eine Klasse stecken, die mir die Elemente auf ein 1-dimensionales Array mappt, bzw wenn die Größe zur Laufzeit konstant bleibt, würde ich unique_ptr<T[]> wrappen, um noch ein paar Bytes rauszuholen.

Spart immer noch einen Zeiger. In anderen Worten: Acht Bytes. Eine enorme Ersparnis bei einer typischerweise tausende Bytes großen Matrix, nicht? Also um Speicher an sich geht es hier nicht.
Der einzige Fall, in dem der kleinere vector messbar schneller sein kann:
Iteration über eine lange Folge von vector en ohne die Elemente der vector en anzufassen. Der unnötige Zeiger braucht Platz im Cache und erfordert damit häufigeres Nachladen.

Wie gesagt: Es gibt noch keine optimale Lösung für das Problem. vector ist der sehr gute Kompromiss, wenn man man ihn nicht mit zwei Zeigern nachbauen möchte oder kann.

Ethon

Wieso wird hier über die Performance von std::vector schlecht geredet? Soetwas besitzt ein new[] Array gar nicht. Von daher steht das nicht zur Debatte.
Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors, nämlich ganze 4/8 Byte auf gängen Maschienen. Das ist extrem vernachlässigbar.

SeppJ

@TyRoXx: Pi hat schon recht (das ich das mal sagen wurde ). vector wäre da deutlich langsamer und deutlich verschwenderischer als statische Arrays. vector ist kein Kompromiss. vector ist wie new[]. Meistens will man auch dynamische Arrays. Aber wenn man sie nicht braucht, dann nimmt man weder vector noch new.

Ich habe mir schon überlegt, ob ich von meiner Seite aus einen Flamewar starten soll, um dem Moderator zu sagen, dass er von seinem Elfenbeinturm steigen soll. Und nun sehe ich, dass ihr dies bereits hervorragenderweise alleine gelöst habt. Eventuell sollte ich wieder anfangen, den Leuten zu vertrauen.

std::vector erzeugt einen Overhead, welcher bei einigen Anwendungsgebieten vermeidbar ist, wenn man stattdessen Arrays benutzt. Jeder, der etwas anderes behauptet, gehört nicht an den Computer, sondern ins Hausmeisterkabuff.

Ethon schrieb:

Wieso wird hier über die Performance von std::vector schlecht geredet? Soetwas besitzt ein new[] Array gar nicht.

Doch. Ein new int[1000] ist schneller als ein vector<int>(1000), eben weil ein int ein POD ist und PODs durch new nicht mit 0 initialisiert werden.

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

SeppJ

keksfresser schrieb:

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

Ein zusätzlicher Pointer, weil du bei vector die Größe nicht speichern musst. Dafür aber echter und deutlicher Performanceverlust, falls du nach und nach Elemente zu deinem new-Array hinzufügen musst. Also im wohl allerhäufigsten Anwendungsszenario, denn selten weiß man im Voraus, wieviel kommen wird.

Ethon

keksfresser schrieb:

Ethon schrieb:

Wieso wird hier über die Performance von std::vector schlecht geredet? Soetwas besitzt ein new[] Array gar nicht.

Doch. Ein new int[1000] ist schneller als ein vector<int>(1000), eben weil ein int ein POD ist und PODs durch new nicht mit 0 initialisiert werden.

Upps, erstens seh ich dass ich da etwas übersehen habe, ich hab mich bei der Aussage auf push_back bezogen. Soetwas hat ein new[] array nicht.

Stimmt. Das sind aber auch nur einmalige Kosten.

keksfresser schrieb:

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

Bei new[] müsste ich mir die Größe auch irgendwo merken. Oder wenn sie sowieso bekannt ist: std::array.

SeppJ schrieb:

keksfresser schrieb:

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

Ein zusätzlicher Pointer, weil du bei vector die Größe nicht speichern musst. Dafür aber echter und deutlicher Performanceverlust, falls du nach und nach Elemente zu deinem new-Array hinzufügen musst. Also im wohl allerhäufigsten Anwendungsszenario, denn selten weiß man im Voraus, wieviel kommen wird.

... was sich, nebenbei bemerkt, auch hervorragend mit einer Liste lösen lässt. Nur der Zugriff auf diese Elemente gestaltet sich dann - das gebe ich zu - ohne weiteren Buffer wieder recht langsam.

TyRoXx

SeppJ schrieb:

Meistens will man auch dynamische Arrays. Aber wenn man sie nicht braucht, dann nimmt man weder vector noch new.

Es geht hier nur um Sequenzen von Elementen, deren Anzahl erst zur Laufzeit feststeht.

Der aus dem Westen .. schrieb:

std::vector erzeugt einen Overhead, welcher bei einigen Anwendungsgebieten vermeidbar ist, wenn man stattdessen Arrays benutzt.

Was für Arrays? Statische -> siehe oben

keksfresser schrieb:

Ethon schrieb:

Wieso wird hier über die Performance von std::vector schlecht geredet? Soetwas besitzt ein new[] Array gar nicht.

Doch. Ein new int[1000] ist schneller als ein vector<int>(1000), eben weil ein int ein POD ist und PODs durch new nicht mit 0 initialisiert werden.

Davon war vorher nie die Rede. Ein Punkt für das new[] ohne Standardinitialisierung, wenn man dieses Verhalten denn wirklich braucht.

SeppJ schrieb:

Ein zusätzlicher Pointer, weil du bei vector die Größe nicht speichern musst.

Ihr versteht nicht.
Man will ein Array mit Grösse n, wobei n erst zur Laufzeit bekannt ist.
n ist eine Variable vom Typ size_t.

size_t n; std::cin >> n; // n ist erst zur Laufzeit bekannt.
std::unique_ptr<char[]>(new char[n]); // wunderbar
std::vector<char>(n); // schlecht. Overhead 2 Pointer + memset auf n bytes
                      // Merke: ich habe n und kann es nicht /nicht/ speichern.

SeppJ schrieb:

Dafür aber echter und deutlicher Performanceverlust, falls du nach und nach Elemente zu deinem new-Array hinzufügen musst. Also im wohl allerhäufigsten Anwendungsszenario, denn selten weiß man im Voraus, wieviel kommen wird.

lol, optimierst du schon bevor du weisst, wieviel kommen wird?

TyRoXx

Der aus dem Westen .. schrieb:

SeppJ schrieb:

keksfresser schrieb:

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

Ein zusätzlicher Pointer, weil du bei vector die Größe nicht speichern musst. Dafür aber echter und deutlicher Performanceverlust, falls du nach und nach Elemente zu deinem new-Array hinzufügen musst. Also im wohl allerhäufigsten Anwendungsszenario, denn selten weiß man im Voraus, wieviel kommen wird.

... was sich, nebenbei bemerkt, auch hervorragend mit einer Liste lösen lässt. Nur der Zugriff auf diese Elemente gestaltet sich dann - das gebe ich zu - ohne weiteren Buffer wieder recht langsam.

list ist beim Anfügen und beim Iterieren langsamer als vector .
Hinzufügen ans Ende können beide in konstanter Zeit, vector ist da aber schneller, weil im Mittel kein Speicher angefordert wird.
Iteration bei list = Herumspringen im Speicher = schlecht für den Cache.

TyRoXx schrieb:

Der aus dem Westen .. schrieb:

SeppJ schrieb:

keksfresser schrieb:

Ethon schrieb:

Der einzige Unterschied ist ein zusätzlicher Pointer auf Seiten des Vektors

Zwei zusätzliche Pointer, weil du die Grösse meist noch woanders gespeichert hast.

Ein zusätzlicher Pointer, weil du bei vector die Größe nicht speichern musst. Dafür aber echter und deutlicher Performanceverlust, falls du nach und nach Elemente zu deinem new-Array hinzufügen musst. Also im wohl allerhäufigsten Anwendungsszenario, denn selten weiß man im Voraus, wieviel kommen wird.

... was sich, nebenbei bemerkt, auch hervorragend mit einer Liste lösen lässt. Nur der Zugriff auf diese Elemente gestaltet sich dann - das gebe ich zu - ohne weiteren Buffer wieder recht langsam.

list ist beim Einfügen und beim Iterieren langsamer als vector .

std::list kann ich nicht beurteilen, damit habe ich bisher kaum gearbeitet. Was ich allerdings festgestellt habe, ist dass wenn ich meine Liste from the scratch implementiere, diese schneller als der Vektor ist.

Also eine nicht- std -Liste verglichen mit std:vector . Vor allem in C kann man hier recht schöne, typenunabhängige Konstrukte bauen, durch die blickt dann aber kein Schwein mehr durch.

dot

Der aus dem Westen .. schrieb:

Was ich allerdings festgestellt habe, ist dass wenn ich meine Liste from the scratch implementiere, diese schneller als der Vektor ist.

Was genau verstehst du denn unter "schneller"?