seahawk1986
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11180
Wohnort: München
|
Hallo, ich frage mich gerade, wie ich das Befüllen eines std::vector in C++ mit verschachtelten Objekten möglichst effizient umsetzen kann - mein Beispielcode sieht aktuell so aus:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64 | #include <iostream>
#include <memory>
#include <vector>
class InnerClass {
private:
int m;
public:
InnerClass() {
std::cout << "called default constructor of inner (" << this << ")" << std::endl;
}
InnerClass(int m): m(m) {
std::cout << "constructing InnerClass (" << this << ") with " << m << std::endl;
}
~InnerClass() {std::cout << "destructing InnerClass (" << this << ") with " << m << std::endl;};
};
class OuterClass {
private:
int n;
InnerClass inner{n * n};
public:
OuterClass() {
std::cout << "called default constructor of outer (" << this << ")" << std::endl;
}
OuterClass(int n): n(n) {
std::cout << "constructing OuterClass (" << this << ") with " << n << std::endl;
};
~OuterClass() {std::cout << "destructing OuterClass (" << this << ") with " << n << std::endl;};
};
class OuterClassPointer {
private:
int n;
std::unique_ptr<InnerClass> inner = std::make_unique<InnerClass>(n * n);
public:
OuterClassPointer(int n): n(n) {
std::cout << "constructing OuterClassPointer (" << this << ") with " << n << std::endl;
}
~OuterClassPointer() {std::cout << "destructing OuterClassPointer (" << this << ") with " << n << std::endl;};
};
int main() {
std::cout << "----------- vector with copy(?) constructor ----------" << std::endl;
std::vector<OuterClass> vOuter;
int i;
for (i=1; i<=3; i++) {
vOuter.push_back(OuterClass(i));
}
std::cout << "clear vector" << std::endl;
vOuter.clear();
std::cout << "cleared vector" << std::endl;
std::cout << "----------- vector with smart pointers ------------" << std::endl;
std::vector<std::unique_ptr<OuterClassPointer>> vOuterP;
for (i=1; i<=3; i++) {
vOuterP.push_back(std::make_unique<OuterClassPointer>(i));
}
std::cout << "clear vector" << std::endl;
vOuterP.clear();
std::cout << "cleared vector" << std::endl;
return 0;
}
|
Und die Ausgaben so:
$ ./a.out
----------- vector with copy(?) constructor ----------
constructing InnerClass (0x7ffdda97de64) with 1
constructing OuterClass (0x7ffdda97de60) with 1
destructing OuterClass (0x7ffdda97de60) with 1
destructing InnerClass (0x7ffdda97de64) with 1
constructing InnerClass (0x7ffdda97de64) with 4
constructing OuterClass (0x7ffdda97de60) with 2
destructing OuterClass (0x5615c49e32c0) with 1
destructing InnerClass (0x5615c49e32c4) with 1
destructing OuterClass (0x7ffdda97de60) with 2
destructing InnerClass (0x7ffdda97de64) with 4
constructing InnerClass (0x7ffdda97de64) with 9
constructing OuterClass (0x7ffdda97de60) with 3
destructing OuterClass (0x5615c49e32e0) with 1
destructing InnerClass (0x5615c49e32e4) with 1
destructing OuterClass (0x5615c49e32e8) with 2
destructing InnerClass (0x5615c49e32ec) with 4
destructing OuterClass (0x7ffdda97de60) with 3
destructing InnerClass (0x7ffdda97de64) with 9
clear vector
destructing OuterClass (0x5615c49e3300) with 1
destructing InnerClass (0x5615c49e3304) with 1
destructing OuterClass (0x5615c49e3308) with 2
destructing InnerClass (0x5615c49e330c) with 4
destructing OuterClass (0x5615c49e3310) with 3
destructing InnerClass (0x5615c49e3314) with 9
cleared vector
----------- vector with smart pointers ------------
constructing InnerClass (0x5615c49e32c0) with 1
constructing OuterClassPointer (0x5615c49e32e0) with 1
constructing InnerClass (0x5615c49e3370) with 4
constructing OuterClassPointer (0x5615c49e3350) with 2
constructing InnerClass (0x5615c49e33b0) with 9
constructing OuterClassPointer (0x5615c49e3330) with 3
clear vector
destructing OuterClassPointer (0x5615c49e32e0) with 1
destructing InnerClass (0x5615c49e32c0) with 1
destructing OuterClassPointer (0x5615c49e3350) with 2
destructing InnerClass (0x5615c49e3370) with 4
destructing OuterClassPointer (0x5615c49e3330) with 3
destructing InnerClass (0x5615c49e33b0) with 9
cleared vector Für mich sieht der erste Teil so aus, als ob er da Objekte erst initialisiert, dann mehrfach kopiert (wie kann man denn den Aufruf eines Copy Constructor sichtbar machen?) - und dann die Originale und Zwischenkopien abräumt. Gibt es da einen eleganten Weg ohne (Smart-)Pointer (wie bei meinem zweiten Ansatz) und möglichst ohne unnötige Kopien und damit verbundene Destruktor-Aufrufe auszukommen?
|
ChickenLipsRfun2eat
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Hallo! Zur Effizienz kann ich dir nichts sagen, den copy-Constructor kannst du aber selbst deklarieren: | class InnerClass {
// …
InnerClass( InnerClass const © );
// …
|
und dir da wieder ein std::cout reinsetzen.
|
seahawk1986
(Themenstarter)
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11180
Wohnort: München
|
Vielen Dank für den Hinweis mit der Syntax für den copy constructor. Mir ist bei einer Runde um den Block noch emplace_back eingefallen, außerdem habe ich Meldungen für den Debug- und Copy-Constructor eingebaut und lasse die capacity des vectors ausgeben:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 | #include <iostream>
#include <memory>
#include <vector>
class InnerClass {
private:
public:
int m=-1;
InnerClass() { std::cout << "called default constructor of inner (" << this << ") with " << m << std::endl; }
InnerClass(int m): m(m) { std::cout << "constructing InnerClass (" << this << ") with " << m << std::endl; }
InnerClass( InnerClass const ©): m(copy.m) {
std::cout << "called copy on InnerClass (" << this << ") with " << m << std::endl;
};
InnerClass(InnerClass&& other) : m(std::move(other.m))
{ std::cout << "moving InnerClass (" << this << ") with " << m << std::endl; }
InnerClass& operator=(const InnerClass& other) = default;
~InnerClass() {std::cout << "destructing InnerClass (" << this << ") with " << m << std::endl;};
};
class OuterClass {
private:
public:
int n=-1;
InnerClass inner;
OuterClass() { std::cout << "called default constructor of outer (" << this << ") with " << n << std::endl; }
OuterClass(int n): n(n), inner(n *n) { std::cout << "constructing OuterClass (" << this << ") with " << n << std::endl; };
OuterClass( OuterClass const ©): n(copy.n), inner(copy.inner) {
std::cout << "called copy on OuterClass (" << this << ") with " << n << std::endl;
};
OuterClass(OuterClass&& other) : n(std::move(other.n)), inner(std::move(other.inner)) { std::cout << "moving OuterClass (" << this << ")" << std::endl; }
OuterClass& operator=(const OuterClass& other) = default;
~OuterClass() {std::cout << "destructing OuterClass (" << this << ") with " << n << std::endl;};
};
int main() {
std::vector<OuterClass> vOuter;
std::cout << "vector capacity is " << vOuter.capacity() << std::endl;
int i;
for (i=1; i<=3; i++) {
vOuter.emplace_back(i);
std::cout << "vector capacity is " << vOuter.capacity() << std::endl;
}
std::cout << "checked values" << std::endl;
std::cout << "clear vector" << std::endl;
vOuter.clear();
std::cout << "cleared vector" << std::endl;
|
Damit sieht es so aus:
$ ./a.out
vector capacity is 0
constructing InnerClass (0x561db51872c4) with 1
constructing OuterClass (0x561db51872c0) with 1
vector capacity is 1
constructing InnerClass (0x561db51872ec) with 4
constructing OuterClass (0x561db51872e8) with 2
called copy on InnerClass (0x561db51872e4) with 1
called copy on OuterClass (0x561db51872e0) with 1
destructing OuterClass (0x561db51872c0) with 1
destructing InnerClass (0x561db51872c4) with 1
vector capacity is 2
constructing InnerClass (0x561db5187314) with 9
constructing OuterClass (0x561db5187310) with 3
called copy on InnerClass (0x561db5187304) with 1
called copy on OuterClass (0x561db5187300) with 1
called copy on InnerClass (0x561db518730c) with 4
called copy on OuterClass (0x561db5187308) with 2
destructing OuterClass (0x561db51872e0) with 1
destructing InnerClass (0x561db51872e4) with 1
destructing OuterClass (0x561db51872e8) with 2
destructing InnerClass (0x561db51872ec) with 4
vector capacity is 4
checked values
clear vector
destructing OuterClass (0x561db5187300) with 1
destructing InnerClass (0x561db5187304) with 1
destructing OuterClass (0x561db5187308) with 2
destructing InnerClass (0x561db518730c) with 4
destructing OuterClass (0x561db5187310) with 3
destructing InnerClass (0x561db5187314) with 9
cleared vector
Da scheint also immer kopiert zu werden, wenn die Kapazität des Vektors angehoben werden muss. Wenn ich die Kapazität des vector vorher erhöhe, indem ich mit vOuter.reserve(3); dafür sorge, dass genügend freie Plätze vorhanden sind, bevor ich in Zeile 41 mit dem Befüllen anfange, fällt das Kopieren weg:
vector capacity is 3
constructing InnerClass (0x56295a5d02c4) with 1
constructing OuterClass (0x56295a5d02c0) with 1
vector capacity is 3
constructing InnerClass (0x56295a5d02cc) with 4
constructing OuterClass (0x56295a5d02c8) with 2
vector capacity is 3
constructing InnerClass (0x56295a5d02d4) with 9
constructing OuterClass (0x56295a5d02d0) with 3
vector capacity is 3
checked values
clear vector
destructing OuterClass (0x56295a5d02c0) with 1
destructing InnerClass (0x56295a5d02c4) with 1
destructing OuterClass (0x56295a5d02c8) with 2
destructing InnerClass (0x56295a5d02cc) with 4
destructing OuterClass (0x56295a5d02d0) with 3
destructing InnerClass (0x56295a5d02d4) with 9
cleared vector Vielleicht kann mir ein Wissender noch sagen, warum sich das so verhält - wird da eventuell beim Vergrößern ein neuer Speicherbereich für den vector gewählt und die bestehenden Daten kopiert?
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
... wird da eventuell beim Vergrößern ein neuer Speicherbereich für den vector gewählt und die bestehenden Daten kopiert?
Ich bin zwar kein C++ Experte, aber ich bin bisher immer davon aus gegangen, dass dem so ist. Ich kann mir auch nicht vorstellen, wie das anders gehen soll. Ein Vector ist ja keine verlinkte Liste. Wenn ich die benötigte Größe in etwa abschätzen kann, verlange ich daher mit reserve gleich am Anfang eine entsprechende Speicherkapazität.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Na klar, wie soll das denn sonst funktionieren, wenn der zuvor reservierte Speicher nicht ausreicht? Da wird unter der Haube per realloc() dann mehr angefordert. Dabei kann, muss aber nicht, der neue Speicher an den Adressen unmittelbar hinter dem bisher letzten Element liegen. Weil dies jedoch nicht durch realloc() garantiert ist, wird zur Sicherheit alles an die neue (und damit evtl alte) Adresse kopiert, die durch realloc() zurückgeliefert wurde. Dies ist nötig, da ansonsten die Pointer-Arithmetik nicht mehr funktionieren würde. Denn dafür müssen bekanntlich alle Elemente an unmittelbar aufeinander folgenden Speicheradressen liegen.
|
ChickenLipsRfun2eat
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Soweit ich mich erinnere arbeitet der std::vector intern mit calloc und realloc, reserviert also bei jeder Erweiterung einen neuen, zusammenhängenden Speicherbereich, im Gegensatz zur std::unordered_map, die arbeitet auch mit "zerstückeltem Speicher". Eventuell könntest du auch noch die compiler-Optimierung ausschalten, um das reelle Verhalten zu sehen. Vorreservieren ist auf jeden Fall eine gute Idee bei der Arbeit mit einem vector.
|
snafu1
Anmeldungsdatum: 5. September 2007
Beiträge: 2123
Wohnort: Gelsenkirchen
|
Dakuan schrieb: Wenn ich die benötigte Größe in etwa abschätzen kann, verlange ich daher mit reserve gleich am Anfang eine entsprechende Speicherkapazität.
Eben. Und man kann andernfalls auch einen halbwegs sinnvollen Startwert nehmen, der erstmal etwas größer gehalten ist. Sowohl in er Windows-Welt wie auch unter Linux wird heutzutage der angeforderte Speicher nicht mehr unmittelbar nach malloc() (oder eben new bei C++) als benutzt zugewiesen, sondern erst dann, wenn er tatsächlich verwendet wird. Somit hält sich der tatsächliche Speicherverbrauch des genutzten Programms dann auch noch in Grenzen. Grundsätzlich könnte man auch optimieren, indem man sich die alte Speicheradresse merkt. Falls realloc() diese liefert, dann könnte das Kopieren entfallen, da hierbei ein aneinander gehängter Speicherbereich von der C-Spezifikation garantiert wird. Ich weiß aber nicht, inwieweit man sich darauf verlassen kann, dass der neue Speicherbereich unverändert bleibt. Denn nur dann hätte man ja noch die alten Zeiger auf die Elemente zur Wiederverwendung.
|
fu_mm
Anmeldungsdatum: 6. März 2020
Beiträge: Zähle...
|
Also ja, std:vector reorganisiert seinen internen Speicher. Vielleicht kann man einen C++11 "Move Constructor" der Itens implementieren um das Befüllen zu beschleunigen, ohne das dynamische Wachstum des vectors durch preallokation zu umgehen. Soll aber nur ein Hinweis sein. Ich weis es nicht.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
seahawk1986 schrieb:
Für mich sieht der erste Teil so aus, als ob er da Objekte erst initialisiert, dann mehrfach kopiert (wie kann man denn den Aufruf eines Copy Constructor sichtbar machen?) - und dann die Originale und Zwischenkopien abräumt.
Genau. Da der std::vector intern ein Array nutzt (ist so vom Standard vorgeschrieben, wenn ich mich nicht täusche), müssen bei jeder Änderung der Größe dieses Arrays alle Objekte im Array kopiert werden.
Gibt es da einen eleganten Weg ohne (Smart-)Pointer (wie bei meinem zweiten Ansatz) und möglichst ohne unnötige Kopien und damit verbundene Destruktor-Aufrufe auszukommen?
Du kannst die Situation etwas verbessern, indem Du std::deque verwendest. Die bessere Lösung ist, die Objekte auf den Heap zu legen und nur Zeiger (z.B. std::shared_ptr) im Container zu verwalten.
|
seahawk1986
(Themenstarter)
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11180
Wohnort: München
|
Danke für die Antworten. Ich kann die maximal erwartbare Zahl der Elemente berechnen, bevor ich den vector nach und nach mit Daten befülle. Um Daten im Heap scheine ich nicht herum zu kommen, um Moves der konstruierten Objekte zu vermeiden, wenn der vector als Referenz herum gereicht wird. Soweit ich das gelesen habe wäre die Performance für den Anwendungsfall Elemente am Ende einzufügen und dann zum Schluss einmal über alle Elemente zu laufen, um sie zu verarbeiten mit einer deque schlechter als mit einem vector mit vorab reserviertem Platz (https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html). Leider kennt die STL vor C++20 noch keine Koroutinen (und zusätzliche Abhängigkeiten wie libboost will ich nach Möglichkeit erst mal nicht dazu nehmen), sonst könne man auf das Zwischenspeichern der Daten weitgehend verzichten und die Objekte direkt weiterverarbeiten.
|
Neral
Anmeldungsdatum: 3. Oktober 2007
Beiträge: 229
|
Ein std::vector move t seine Elemente nicht, wenn man eine Referenz auf ihn bildet. Beispiel:
| template<typename T>
auto foo(std::vector<T> const& ts) -> size_t {
return ts.size();
}
|
foo ist O(1), es wird keins der Elemente gemove t, egal was für ein Typ T ist. Wenn du die Länge des Vectors kennst und reserve aufrufst, sollte gar kein move passieren. Wenn du nicht alle Elemente gleichzeitig brauchst, sondern eins nach dem anderen verarbeiten willst, brauchst du nicht unbedingt Coroutinen,
sondern kannst dir einen eigenen Iterator schreiben, der die Werte lazy generiert. Hier mal ein Beispiel, das unendlich viele Fibonacci-Zahlen generiert (Godbolt):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63 | #include <cstdint>
#include <cstdio>
#include <cinttypes>
#include <optional>
#include <tuple>
struct Fibonacci {
struct Iterator {
// `value_type` and `reference` are required by `LegacyInputIterator`
// (https://en.cppreference.com/w/cpp/named_req/InputIterator).
// Without these types, the iterator cannot be used in STL algorithms.
using value_type = uint64_t;
using reference = value_type;
std::optional<Fibonacci*> fibonacci;
auto operator!=(Iterator const& other) const -> bool {
return this->fibonacci != other.fibonacci;
}
auto operator++() -> Iterator& {
(*this->fibonacci)->advance();
return *this;
}
auto operator++(int) -> Iterator {
auto copy = *this;
++(*this);
return copy;
}
auto operator*() const -> uint64_t {
return (*this->fibonacci)->value();
}
};
uint64_t a{0};
uint64_t b{1};
auto begin() -> Iterator {
return Iterator{this};
}
auto end() -> Iterator {
return Iterator{std::nullopt};
}
auto value() const -> uint64_t {
return a;
}
auto advance() -> void {
std::tie(a, b) = std::make_tuple(b, a + b);
}
};
auto main() -> int {
for (auto const& n: Fibonacci{}) {
// Use `printf` here because the assembly is way easier to read.
std::printf("%" PRIu64 "\n", n);
}
}
|
Ist zwar ein bisschen Tipparbeit, aber üblicherweise kann das alles gut optimiert werden (In diesem Beispiel: drei Assemblerbefehle für das Rechnen und vier für den printf -Aufruf). Zum Heap vs. std::deque : Ein std::vector<std::unique_ptr<T>> hat bei jedem Iterationsschritt eine Indirektion, die nicht gut vorhergesagt werden kann (einmal den unique_ptr dereferenzieren). Eine std::deque<T> hat diese Kosten nicht, weil die meisten Elemente zusammenhängend gespeichert sind und nur wenige Indirektionen zwischen den Chunks vorkommen. Es ist also (für mich) nicht offensichtlich, dass ein std::vector<std::unique_ptr<T>> schneller ist. Da müsste man messen. Und ob ein std::vector<T> zu langsam ist, müsstest du auch messen. Ohne Messung kann man sich in diesem Thema wunderbar verrennen. 😀
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Neral schrieb: Ein std::vector move t seine Elemente nicht, wenn man eine Referenz auf ihn bildet.
Ja, aber der Fall, um den es hier hautpsächlich geht, ist der der Objekte in dem std::vector - insbesondere beim Einfügen.
|
Neral
Anmeldungsdatum: 3. Oktober 2007
Beiträge: 229
|
@rklm: Ich hatte den letzten Post von seahawk1986 so verstanden, dass er/sie sich um Moves der Elemente des Vectors Sorgen macht, wenn er per Referenz an eine Funktion übergeben wird: seahawk1986 schrieb: um Moves der konstruierten Objekte zu vermeiden, wenn der vector als Referenz herum gereicht wird.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12832
|
Neral schrieb: @rklm: Ich hatte den letzten Post von seahawk1986 so verstanden, dass er/sie sich um Moves der Elemente des Vectors Sorgen macht, wenn er per Referenz an eine Funktion übergeben wird: seahawk1986 schrieb: um Moves der konstruierten Objekte zu vermeiden, wenn der vector als Referenz herum gereicht wird.
Achso. Aber wieso sollte das bei einer Referenz passieren? Das würde dann ja höchstens passieren, wenn man lokale Objekte aus denen in der Collection erzeugt.
|
seahawk1986
(Themenstarter)
Anmeldungsdatum: 27. Oktober 2006
Beiträge: 11180
Wohnort: München
|
Neral schrieb: Ein std::vector move t seine Elemente nicht, wenn man eine Referenz auf ihn bildet.
Ja stimmt, da hatte ich beim Testen Objekte, die Moves hatte ich nur, weil ich Objekte, die in der Funktion per ´emplace_back in den vector geschoben werden sollten, unnötigerweise konstruiert hatte, statt nur die Argumente für den constructor zu übergeben.
Wenn du nicht alle Elemente gleichzeitig brauchst, sondern eins nach dem anderen verarbeiten willst, brauchst du nicht unbedingt Coroutinen,
sondern kannst dir einen eigenen Iterator schreiben, der die Werte lazy generiert.
Danke, das muss ich mit mal genauer ansehen, wie sich das auf meinen Fall anwenden lässt - ich will Abfragen an eine REST-API stellen, die Datensätze mit Paginierung herausrückt und dann Elemente aus JSON-Arrays dieser einzelnen nach Eigenschaften filtern, verarbeiten und pro Element ein Objekt konstruieren, bei dem fehlende Daten mit weiteren API-Abfragen ergänzt werden, bevor die Daten dann in die Datenbank geschrieben werden. Das ganze soll in einer schon bestehenden Anwendung die Klassen für eine ältere API-Version ersetzen (bei der die Daten z.T. anders aufbereitet waren) und ich will möglichst wenig am Rest ändern. Zum Heap vs. std::deque : Ein std::vector<std::unique_ptr<T>> hat bei jedem Iterationsschritt eine Indirektion, die nicht gut vorhergesagt werden kann (einmal den unique_ptr dereferenzieren). Eine std::deque<T> hat diese Kosten nicht, weil die meisten Elemente zusammenhängend gespeichert sind und nur wenige Indirektionen zwischen den Chunks vorkommen. Es ist also (für mich) nicht offensichtlich, dass ein std::vector<std::unique_ptr<T>> schneller ist. Da müsste man messen. Und ob ein std::vector<T> zu langsam ist, müsstest du auch messen. Ohne Messung kann man sich in diesem Thema wunderbar verrennen. 😀
Ich bin schon froh, wenn ich von den nackten Pointern wegkomme, die da aktuell genutzt werden. Die meiste Zeit dürfte für die API-Abfragen und die Kommunikation mit der Datenbank drauf gehen, mir geht es vor allem darum eine Lösung zu finden, in der ich ich gegenüber dem jetzigen Stand nichts unabsichtlich verschlimmbessere. Soweit ich das im Hinterkopf habe, ist die Stacksize begrenzt und da Bilddaten in den Objekten stecken können, lebt es sich mit Daten im Heap vermutlich unbesorgter als wenn die auf dem Stack Platz finden müssen, oder?
|