std::vector-Wachstum

[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.

[Mr. N]

Bouncer schrieb:

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.

Nein, geht nicht.

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.

Im allgemeinen geht das aber nicht. Und ich wette mit dir, keine Standardbibliothek hat eine Spezialisierung dafür.

Ponto schrieb:

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.

Gerne, aber bitte nicht in std::vector.

[Bouncer]

Mr. N schrieb:

Bouncer schrieb:

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.

Nein, geht nicht.

na, dann erklär' doch mal, warum verschieben nicht erlaubt ist.
und falls tatsächlich nicht verschoben werden darf: wie wird dann mehr speicher bereitgestellt?

[Mr. N]

Bouncer schrieb:

Mr. N schrieb:

Bouncer schrieb:

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.

Nein, geht nicht.

na, dann erklär' doch mal, warum verschieben nicht erlaubt ist.

Weil ein Objekt seine eigene Adresse speichern kann. Ja, das kommt tatsächlich vor.

Bouncer schrieb:

und falls tatsächlich nicht verschoben werden darf: wie wird dann mehr speicher bereitgestellt?

Ganz einfach. Er wird alloziert. Dann wird kopiert (so effizient wie möglich). Dann der alte Speicher dealloziert. Also das selbe, was realloc intern macht, nur flexibler.

[hustbaer]

Ponto schrieb:

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 würde allerdings den Adressraum ziemlich flott segmentieren. Das OS bzw. die C++ Implementierung kann ja nicht wissen ob ich 10 Vektoren anlegen werden die dann allesamt sehr gross werden, oder ob ich 100.000 Vektoren anlegen werden die allesamt sehr klein bleibe, und gleich darauf dann 20GB Speicher am Stück haben möchte. Oder ein 1TB sparse-File in den Speicher mappen. Oder...

Ich denke es macht nur dann Sinn sowas zu versuchen wenn man dem User die Möglichkeit gibt anzugeben ob diese Optimierung gemacht werden soll oder nicht.