std::vector-Wachstum

[Mr. N]

pumuckl schrieb:

Ich weiss nicht genau in welchem, aber ein einem seiner Artikel schreibt Herb Sutter, dass ohne weitere Annahmen ein Faktor von ca. 1.5 am guenstigsten ist. Dabei wird natuerlich die Anzahl der alloziierten Bytes gerundet auf ein ganzzahliges Vielfaches von 8 byte (oder 16, 32 byte... systemabhaengig)

Bytes? Du meinst Elemente?

Ich kann mir durchaus vorstellen, dass 1.5 gut wäre. Vermutlich würde das die Benchmarks für kleine Vektoren kaputt machen, weswegen man lieber 2 nimmt?

[pumuckl]

Vergiss meinen Satz mit den 8 byte - war noch nicht ganz wach, hab da was durcheinander gebracht. Was das Thema kleinere vector<>en angeht, kann ich mir vorstellen, dass die erste Allokation ueberhaupt gleich einen groesseren Batzen reserviert, eventuell abhaengig von sizeof(T), sprich, bei vector<char> wird gleich Speicher fuer 50 chars geholt, bei vector<MonsterClass> mit sizeof(MonsterClass) = 10000 dann doch nicht ganz so viel.

[ChrisM]

Hi,

wie, ein frischer Vektor mit einem gepushten Element allokiert mehr Platz als für dieses eine Element?

Dann ist mein Vorschlag vom Anfang ja sogar schon umgesetzt...

ChrisM

[Mr. N]

ChrisM schrieb:

wie, ein frischer Vektor mit einem gepushten Element allokiert mehr Platz als für dieses eine Element?

Er darf. Muss aber nicht. Und tuts auch üblicherweise nicht.

[Bouncer]

Ponto schrieb:

Für die Laufzeit verteilt man aber alle Kopieraktionen auf alle Elemente und man sieht, dass bei einer Verdopplung jedes Element durchschnittlich weniger als 2 mal kopiert wurde. Daraus ergibt sich die amortisiert konstante Arbeit pro Einfügeoperation. Man kann amortisierte Laufzeit mit durchschnittlicher Laufzeit gleichsetzen.

jo, das sehe ich ja ein. je grösser so ein vektor wird, desto seltener musser 'realloc' machen und hat demzufolge im durchschnitt eine bessere laufzeit als einer, der in regelmässigen abständen 'realloct'. dafür verbrät er eben mehr speicher. geschenkt gibt's nix. 'there ain't no such thing as a free lunch';)

[ghorst]

da es gerade so halb zum thema passt. ich las gerade hier: Qt Quarterly - Issue 19 · Q3 2006 - Inside the Qt 4 Containers das die trolle sich für problemlos verschiebbare objekte/datentypen bewusst für eine variante mit konstanter vergrößerung des arrays entschieden, da diese ein besseres laufzeitverhalten hat, da realloc bei modernen systemen nicht immer eine kopie erzeugt, sondern häufig das os lediglich die zuordnung zwischen physikalischen und logischen speicherbereichen ändert.
wenn der inhalt nicht problemlos kopierbar ist, verwenden sie nebenbei eine vergrößerung auf das 1,5fache.

stellt sich hier die frage: geht die komplexitätsbetrachtung an der realität vorbei oder haben die trolle es schlicht falsch gemacht?

[hustbaer]

Die trolle haben es schlicht falsch gemacht würde ich sagen

[ghorst]

na ohne begründung kann ich das leider nicht akzeptieren.

[hustbaer]

ghorst schrieb:

na ohne begründung kann ich das leider nicht akzeptieren.

Weil das Statement:

This makes sense because modern operating systems don't copy the entire data when reallocating a buffer; the physical memory pages are simply reordered, and only the data on the first and last pages need to be copied.

IMO völliger Quatsch ist.
Mit Windows geht das auf jeden Fall nicht (zumindest nicht mit realloc, wenn dann müsste man da schon die Win32 API bemühen, und nichtmal da wüsste wie man es macht bzw. ob es überhaupt geht).

Es mag sein dass es für Linux einen Allocator gibt der das kann, aber z.B. tcmalloc kann es auch nicht (und bei ptmalloc würde es mich auch sehr wundern).

Davon abgesehen finde is es etwas brutal einfach 4K anzufordern - was wenn ich bloss 10 oder 20 longs brauche? Dann verscchwendet Qt fast 4K pro Vektor. Hm...

[Mr. N]

Bouncer schrieb:

Ponto schrieb:

Für die Laufzeit verteilt man aber alle Kopieraktionen auf alle Elemente und man sieht, dass bei einer Verdopplung jedes Element durchschnittlich weniger als 2 mal kopiert wurde. Daraus ergibt sich die amortisiert konstante Arbeit pro Einfügeoperation. Man kann amortisierte Laufzeit mit durchschnittlicher Laufzeit gleichsetzen.

jo, das sehe ich ja ein. je grösser so ein vektor wird, desto seltener musser 'realloc' machen und hat demzufolge im durchschnitt eine bessere laufzeit als einer, der in regelmässigen abständen 'realloct'. dafür verbrät er eben mehr speicher. geschenkt gibt's nix. 'there ain't no such thing as a free lunch';)

vector darf nicht realloc nutzen.

[Ponto]

Mr. N schrieb:

vector darf nicht realloc nutzen.

Warum nicht?

Ich finde auch die Idee von Trolltech einen Vector immer um eine Page zu erweitern gar nicht so übel, wenn das Betriebssystem mitspielt. Einfügeoperationen am Ende sind immer noch konstant. Nur die Pagetable eines Prozesses könnte stärker belastet werden, da die physikalischen Seiten stärker gewürfelt sein können. Ich denke aber, dass die Jungs nachgemessen haben.

[Mr. N]

Ponto schrieb:

Mr. N schrieb:

vector darf nicht realloc nutzen.

Warum nicht?

So eine Frage hätte ich von dir nicht erwartet.

1. Weil das Allocator-Konzept keine realloc-artige Funktion anbietet.
2. Weil C-realloc nicht mit Allocator zusammengeht.
3. C-realloc kopiert unnötigerweise byteweise die Daten, was ja für std::vector offensichtlich falsch ist.

Das mag nicht perfekt sein, doch so ist es nunmal.

[Bouncer]

Mr. N schrieb:

3. C-realloc kopiert unnötigerweise byteweise die Daten...

nicht immer. manchmal kann so'n block auch einfach vergrössert werden, wenn dahinter noch genug platz frei ist, ohne umkopieren. kommt drauf an, wie schlau der heap-code ist. was nimmt 'vector' denn, wenn es kein realloc benutzen soll? irgendwelche systemfunktionen wie sbrk(), VirtualAlloc(), usw? die sind ja meistens ziemlich unflexibel.

[Mr. N]

Bouncer schrieb:

Mr. N schrieb:

3. C-realloc kopiert unnötigerweise byteweise die Daten...

nicht immer. manchmal kann so'n block auch einfach vergrössert werden, wenn dahinter noch genug platz frei ist, ohne umkopieren. kommt drauf an, wie schlau der heap-code ist.

Ja. Aber manchmal kopiert es die Bytes und das ist aus Sicht von std::vector komplett falsch. (Zur Erinnerung: std::vector kann Objekte speichern und die lassen sich nicht unbedingt byteweise kopieren.)

Bouncer schrieb:

was nimmt 'vector' denn, wenn es kein realloc benutzen soll? irgendwelche systemfunktionen wie sbrk(), VirtualAlloc(), usw? die sind ja meistens ziemlich unflexibel.

Es benutzt den gegebenen Allocator. (Zur Erinnerung: std::vector<ValueType, Allocator>.)

[Bouncer]

Mr. N schrieb:

...manchmal kopiert es die Bytes und das ist aus Sicht von std::vector komplett falsch. (Zur Erinnerung: std::vector kann Objekte speichern und die lassen sich nicht unbedingt byteweise kopieren.)

wieso nicht? man kann zwar nicht immer durch byteweises kopieren einen klon erzeugen, aber verschieben müsste doch gehen.

Mr. N schrieb:

Bouncer schrieb:

was nimmt 'vector' denn, wenn es kein realloc benutzen soll? irgendwelche systemfunktionen wie sbrk(), VirtualAlloc(), usw? die sind ja meistens ziemlich unflexibel.

Es benutzt den gegebenen Allocator. (Zur Erinnerung: std::vector<ValueType, Allocator>.)

naja, aber so'n 'allocator' ist ja auch nur ein zwischengeschaltetes ding, d.h. irgendwo muss der seinen speicher auch her bekommen. wenn er kein realloc() benutzt und nix verschieben darf, dann muss er eine liste von pointern managen, die er sich mit 'new' oder malloc() besorgt hat, beim zugriff auf den 'vector' dann irgendwie rausfinden, in welchem speicherblock das objekt nun steckt, usw. ich glaub nicht, dass er's so macht. das wäre doch viel zu umständlich. vielleicht benutzt er einfach nur new/delete bzw. malloc/free und verschiebt dann selber? also: wie macht's denn nun der 'allocator'?

[Ponto]

Mr. N schrieb:

Ponto schrieb:

Mr. N schrieb:

vector darf nicht realloc nutzen.

Warum nicht?

So eine Frage hätte ich von dir nicht erwartet.

1. Weil das Allocator-Konzept keine realloc-artige Funktion anbietet.
2. Weil C-realloc nicht mit Allocator zusammengeht.
3. C-realloc kopiert unnötigerweise byteweise die Daten, was ja für std::vector offensichtlich falsch ist.

Das mag nicht perfekt sein, doch so ist es nunmal.

Das sind alles keine Gründe es nicht doch zu tun, wenn es sich um POD Daten handelt und der Standardallocator verwendet wird.

[camper]

Ponto schrieb:

Das sind alles keine Gründe es nicht doch zu tun, wenn es sich um POD Daten handelt und der Standardallocator verwendet wird.

Abgesehen davon, dass Allokatoren kein entsprechendes Interface haben, um einen bereits allokierten Block zu vergrößern oder zu verkleinern (damit beschränkt sich die mögliche Anwendung von realloc auf die Funktionalität von malloc/free - das ist selbstverständlich möglich), kann der Allokator nicht wissen, ob im allokierten Speichern tatsächlich Objekte vom angeforderten Typ leben. Ein Container könnte einfache PODs angefordert haben, um an hinreichend ausgerichteten Speicher zu gelangen und dann etwas völlig anderes darin konstruieren. Das wäre z.B. denkbar bei einem Container, der verschiedene Datentypen (ähnlich boost::variant) verwalten kann. Auch die Implementation von Knoten bei list, map usw. ist mitunter etwas exotisch in dieser Hinsicht, etwa:

struct Node
{
    Node* next,*prev;
    alignas(T) char v[sizeof(T)]; // Node ist ein Pod, T wird dann später hier hineinkonstruiert
};

Wie schon Stepanov selbst festgestellt hat: Allokatoren sind eine gute Idee, die nicht funktioniert.

[Ponto]

camper schrieb:

Ponto schrieb:

Das sind alles keine Gründe es nicht doch zu tun, wenn es sich um POD Daten handelt und der Standardallocator verwendet wird.

Abgesehen davon, dass Allokatoren kein entsprechendes Interface haben, um einen bereits allokierten Block zu vergrößern oder zu verkleinern (damit beschränkt sich die mögliche Anwendung von realloc auf die Funktionalität von malloc/free - das ist selbstverständlich möglich), kann der Allokator nicht wissen, ob im allokierten Speichern tatsächlich Objekte vom angeforderten Typ leben.

Der Implementierer der Bibliothek kann machen, was er will. Er kann seinen Standardallokator mit realloc versehen. Er kann darauf verzichten, einen Allokator zu verwenden, wenn das für den Programmierer nichts ändert. Ein std::vector muss nicht mal in C++ implementiert werden. Wenn das OS sowas bereitstellt, kann der Implementierer es weiterreichen.

[camper]

Ponto schrieb:

Der Implementierer der Bibliothek kann machen, was er will. Er kann seinen Standardallokator mit realloc versehen. Er kann darauf verzichten, einen Allokator zu verwenden, wenn das für den Programmierer nichts ändert. Ein std::vector muss nicht mal in C++ implementiert werden. Wenn das OS sowas bereitstellt, kann der Implementierer es weiterreichen.

touché. Die Sichtweise nimmt nebenbei der gesamten Diskussion effektiv jeden Sinn.

[Ponto]

camper schrieb:

Ponto schrieb:

Der Implementierer der Bibliothek kann machen, was er will. Er kann seinen Standardallokator mit realloc versehen. Er kann darauf verzichten, einen Allokator zu verwenden, wenn das für den Programmierer nichts ändert. Ein std::vector muss nicht mal in C++ implementiert werden. Wenn das OS sowas bereitstellt, kann der Implementierer es weiterreichen.

touché. Die Sichtweise nimmt nebenbei der gesamten Diskussion effektiv jeden Sinn.

Nicht wirklich. Das Betriebssystem kann durch den Pagemechanismus den virtuellen Speicher beliebig aus physikalischem Speicher zusammensetzen. Es wäre sinnlos das nicht zu nutzen. (Ich kann jetzt nicht einschätzen, ob es wirklich schneller oder sparsamer ist).

Vor allem auf 64bit-Plattformen kann man so um einen std::vector<double> oder std::vector<int> mal 1 Terabyte im Addressraum frei lassen und bei Bedarf einfach Pages dranhängen. So spart man sich jede Kopieraktion. Und anders als bisher angeklungen funktioniert das für alle Datentypen, die in einem vector gespeichert werden können. Nicht nur für POD.

Das Verhindern von Kopieraktionen ist gar nicht mal Erbsenzählerei. Das Erweitern eines std::vector von 10 Gigabyte auf 20 Gigabyte dauert auf NUMA Architekturen schon mal mehrere Sekunden. Und die will man manchmal nicht spendieren. So haben wir durch ein entsprechendes reserve() schon mal die Laufzeit halbiert.

Wenn der Benutzer einen eigenen Allokator oder sonstwas benutzen möchte, was solche Optimierungen verhindert, kann das die Implementierung durch Templatespezialisierung oder Zusammenarbeit mit dem Compiler leicht erkennen und auf ein Standardverhalten zurückweichen. Alles in den Grenzen von C++.

PS: Ich denke man kann sowas mit mmap() und mremap() auf Linux relativ einfach implementieren. Zunächst sehe ich keinen Grund, der das verhindert.