3. Wieviel wird bei std::vektor vorallokiert ?

Wieviel wird bei std::vektor vorallokiert ?


  • virtuell Realisticer schrieb:

    hustbaer schrieb:

    Nixe wird vorallokiert.
    Wäre auch etwas doof - gibt ja viele Fälle wo man nen vector anlegt, dann aber nie was reinsteckt...

    Es kann sein, dass mehr Speicher allokiert worden ist, damit nicht bei jedem
    push_back alles umkopiert werden muss. Ob das nun der Fall ist, haengt
    von der Implementierung ab.

    Wieviel allokiert worden ist, kann man mittels capacity() rausfinden.

    gruss
    v R

    Ja, genaugenommen ist das richtig. Praktisch wird aber, wenn man einen std::vector default konstruiert, nix voralloziert.
    p.S.: und praktsich wird auch meistens genau so viel alloziert wie man angibt wenn man den std::vector mit einem size_t konstuiert.

    0
  • K

    hustbaer schrieb:

    Nixe wird vorallokiert.
    Wäre auch etwas doof - gibt ja viele Fälle wo man nen vector anlegt, dann aber nie was reinsteckt...

    Hmm ... also ich glaube, Performanceanalysen haben etwas anderes erbracht, denn zumindest hat Microsoft nach sorgfältigen Analysen beschlossen, Listen und Stringbuilder im .NET-Framework mit einer Anfangskapazität von 10 (?) zu versehen.

    0
  • T

    hustbaer schrieb:

    gibt ja viele Fälle wo man nen vector anlegt, dann aber nie was reinsteckt...

    😕 is mir noch nie passiert..

    0
  • ?
     

    #include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
	vector<int> vec;
	cout << "Size:   -> Capacity:" << endl;
	cout << vec.size() << "       -> " << vec.capacity() << endl;
	for( int i = 0; i < 33; ++i )
	{
		vec.push_back( i );
		cout << vec.size() << "       -> " << vec.capacity() << endl;
	}
        return EXIT_SUCCESS;
}

    Size:   -> Capacity:
0       -> 0
1       -> 1
2       -> 2
3       -> 4
4       -> 4
5       -> 8
6       -> 8
7       -> 8
8       -> 8
9       -> 16
10       -> 16
11       -> 16
12       -> 16
13       -> 16
14       -> 16
15       -> 16
16       -> 16
17       -> 32
18       -> 32
19       -> 32
20       -> 32
21       -> 32
22       -> 32
23       -> 32
24       -> 32
25       -> 32
26       -> 32
27       -> 32
28       -> 32
29       -> 32
30       -> 32
31       -> 32
32       -> 32
33       -> 64

    Am Anfang 0, bei erreichen der Kapazitätsgrenze wird einfach verdoppelt.

    0
  • K

    DermitLangeweile schrieb:

    bei erreichen der Kapazitätsgrenze wird einfach verdoppelt.

    Das ist jetzt nicht gerade die Erkenntnis des Jahrhunderts ...

    0
  • ?

    Das ist jetzt nicht gerade der sinnvollste Beitrag des Jahrhunderts ... 🙄

    Wollts halt nur mal sagen, für alle die solche Fragen stellen:
    "Wieviel wird bei std::vektor vorallokiert?"
    Und der nächste kommt dann und fragt: "Wieviel wird bei std::vektor reallokiert?"

    Also...was?

    0

  • Konrad Rudolph schrieb:

    hustbaer schrieb:

    Nixe wird vorallokiert.
    Wäre auch etwas doof - gibt ja viele Fälle wo man nen vector anlegt, dann aber nie was reinsteckt...

    Hmm ... also ich glaube, Performanceanalysen haben etwas anderes erbracht, denn zumindest hat Microsoft nach sorgfältigen Analysen beschlossen, Listen und Stringbuilder im .NET-Framework mit einer Anfangskapazität von 10 (?) zu versehen.

    Oh Mann, du willst doch nicht C++ Container mit .NET Collections vergleichen? BTW: wo ist dieser Speicher zuhause, ist der Teil des Listenobjektes, oder eigens alloziert?
    Genau die gleiche Optimierung gibts auch in std::list, wo schonmal eine List Node als Teil der std::list mit angelegt wird, bloss bei std::vector funktioniert das nicht.

    0
  • K

    hustbaer schrieb:

    Oh Mann, du willst doch nicht C++ Container mit .NET Collections vergleichen?

    Prinzipiell: Wieso nicht? Die Schnittstellen in .NET sind zwar kaputt, die Implementierung an sich ist aber super.

    0

  • Konrad Rudolph schrieb:

    hustbaer schrieb:

    Oh Mann, du willst doch nicht C++ Container mit .NET Collections vergleichen?

    Prinzipiell: Wieso nicht? Die Schnittstellen in .NET sind zwar kaputt, die Implementierung an sich ist aber super.

    Speichern von Referenzen vs. Speichern von Instanzen? Oder checke ich da jetzt was nicht. Ich kann mir auf jeden Fall nicht vorstellen dass eine Liste in .NET die Instanzen speichert (falls es sowas geben sollte) Platz für 10 Instanzen vor-alloziert. Das wäre ja ziemlich heftig wenn z.B. einen Instanz gleich 10k braucht...

    Ich bin auf jeden Fall der Meinung dass es grobe Verschwendung wäre für jeden std::vector<T> gleich Platz für 10 Ts vor-zu-allozieren, zumindest bei grossen Ts. Klar könnte man eine Spezialisierung machen für kleine Ts (und wenn der standard Allocator verwendet wird), aber im "Allgemeinen" wird wohl ein std::vector nie Platz für Items vor-allozieren. Wäre denke ich katastrophal für Programme die nen Haufen Vektoren verwenden, aber bloss in ein paar wirklich was reinstecken. Es gibt ja schon Leute die sich aufgeregt haben weil die standard Lib von irgendeinem MSVC bei einer std::list gleich Platz für eine Node mit alloziert. Bei sehr vielen leeren std::list Instanzen kann das halt doch einen deutlichen Unterschied machen.

    0
  • K

    hustbaer schrieb:

    Konrad Rudolph schrieb:

    hustbaer schrieb:

    Oh Mann, du willst doch nicht C++ Container mit .NET Collections vergleichen?

    Prinzipiell: Wieso nicht? Die Schnittstellen in .NET sind zwar kaputt, die Implementierung an sich ist aber super.

    Speichern von Referenzen vs. Speichern von Instanzen? Oder checke ich da jetzt was nicht. Ich kann mir auf jeden Fall nicht vorstellen dass eine Liste in .NET die Instanzen speichert (falls es sowas geben sollte) Platz für 10 Instanzen vor-alloziert. Das wäre ja ziemlich heftig wenn z.B. einen Instanz gleich 10k braucht...

    Wann verbraucht eine "leere" Instanz (T()) denn mal 10kiB? Sicher gibt es das, aber wohl eher selten. Die meisten potentiell großen Datentypen sind doch wohl Container, die anfänglich leer sind.

    Zu Referenzen/Instanzen: Klar, in .NET sind Klassen als Referenzen gespeichert aber es gibt ja noch Werttypen (Strukturen). Die sind zwar laut Microsoft für kleine Typen vorgesehen -- aber wie gesagt: Wann ist ein Typ denn schon mal *wirklich* groß, so dass zehn vorgemerkte Speicherplätze ein Speicherproblem darstellen sollten?

    0

  • Ja, OK, die 10k waren übertrieben. Es reicht ja schon wenn es 32 Byte sind (was denke ich nicht unrealistisch ist), dann sind das für 10 Instanzen auch schon 320 Byte. Und 320 Byte für einen doofen leeren Vektor... naja.

    Ausserdem gäbe es denke ich ein Problem wenn "sizeof std::vector<T>" von "sizeof T" abhängig wäre - dann könnte ein "T" nämlich keinen "std::vector<T>" mehr enthalten - was hin und wieder aber recht praktisch ist. Hab' allerding keine Ahnung was der Standard dazu sagt, also ob das laut Standard gehen muss oder nicht.

    0
  • C

    hustbaer schrieb:

    Ja, OK, die 10k waren übertrieben. Es reicht ja schon wenn es 32 Byte sind (was denke ich nicht unrealistisch ist), dann sind das für 10 Instanzen auch schon 320 Byte. Und 320 Byte für einen doofen leeren Vektor... naja.

    Ausserdem gäbe es denke ich ein Problem wenn "sizeof std::vector<T>" von "sizeof T" abhängig wäre - dann könnte ein "T" nämlich keinen "std::vector<T>" mehr enthalten - was hin und wieder aber recht praktisch ist. Hab' allerding keine Ahnung was der Standard dazu sagt, also ob das laut Standard gehen muss oder nicht.

    Ganz einfach: Da das Objekt an sich ja eine konstante Größe hat, können die eigentlichen Vektor-Elemente nicht IM Objekt untegebracht werden. Und deshalb hat der vector<> auch nur einen T* _data (und einige size_t für Größe und Kapazität) und lagert die eigentlichen Daten auf dem Heap.

    (und der Heap-Bereich, den ein Objekt sich reserviert hat, wird von sizeof nicht erfasst)

    0

  • @CStoll: Danke, mir ist sehr gut klar wie ein Vektor arbeitet *wunder*.

    Es sollte aber auch klar sein dass man sehr wohl einen Vektor machen könnte der Platz für eine kleine Anzahl von Elementen IM Objekt selbst hat. Was ich nun nicht weiss ist ob der Standard das erlaubt, das ist alles.
    WENN es nämlich erlaubt wäre, dann wäre nichtmehr sichergestellt dass man in einer Klasse X ein Member vom Typ vector<X> haben kann.

    Und wenn ein Vector, wie in allen mir bekannten Implementierungen, eben keinen Platz für Elemente IM Objekt selbst hat, dann macht es auch keinen Sinn wenn man den default Ctor als "Optimierung" gleich Platz für ein paar Elemente schaffen lässt.

    0
  • C

    hustbaer schrieb:

    WENN es nämlich erlaubt wäre, dann wäre nichtmehr sichergestellt dass man in einer Klasse X ein Member vom Typ vector<X> haben kann.

    Durchaus möglich, daß es erlaubt ist. Aber sehr viel Sinn dürfte es nicht machen (besonders da afair die vector-Elemente hintereinander im Speicher stehen MÜSSEN - d.h. wenn der eventuell vorreservierte Speicherplatz zu klein wird, bleibt er nutzlos liegen).

    0

  • CStoll schrieb:

    hustbaer schrieb:

    WENN es nämlich erlaubt wäre, dann wäre nichtmehr sichergestellt dass man in einer Klasse X ein Member vom Typ vector<X> haben kann.

    Durchaus möglich, daß es erlaubt ist. Aber sehr viel Sinn dürfte es nicht machen (besonders da afair die vector-Elemente hintereinander im Speicher stehen MÜSSEN - d.h. wenn der eventuell vorreservierte Speicherplatz zu klein wird, bleibt er nutzlos liegen).

    Äh. Natürlich müssen sie das, also die Elemente eines Vektors hintereinander im Speicher stehen. Ist halt im Prinzip dasselbe wie die "small string optimization" - dabei bleibt der Speicher in z.B. std::string auch ungenutzt sobald der String zu lange wird, bloss solange der String kurz bleibt bringt das einiges an Performance, da dynamische Speicheranforderungen auf vielen Systemen verhältnismässig sehr teuer sind.

    BTW: du scheinst nicht den ganzen Thread gelesen zu haben, ich hab von Anfang an geschrieben dass std::vector nix vor alloziert 😉

    0
  • C

    hustbaer schrieb:

    CStoll schrieb:

    hustbaer schrieb:

    WENN es nämlich erlaubt wäre, dann wäre nichtmehr sichergestellt dass man in einer Klasse X ein Member vom Typ vector<X> haben kann.

    Durchaus möglich, daß es erlaubt ist. Aber sehr viel Sinn dürfte es nicht machen (besonders da afair die vector-Elemente hintereinander im Speicher stehen MÜSSEN - d.h. wenn der eventuell vorreservierte Speicherplatz zu klein wird, bleibt er nutzlos liegen).

    Äh. Natürlich müssen sie das, also die Elemente eines Vektors hintereinander im Speicher stehen. Ist halt im Prinzip dasselbe wie die "small string optimization" - dabei bleibt der Speicher in z.B. std::string auch ungenutzt sobald der String zu lange wird, bloss solange der String kurz bleibt bringt das einiges an Performance, da dynamische Speicheranforderungen auf vielen Systemen verhältnismässig sehr teuer sind.

    Ja, bei einem String ist das auch nicht so problematisch, ständig (ungenutzten) Platz für ein paar Elemente mitzuschleppen (dort geht es auch "nur" um Zeichen). Aber ein Vektor kann auch potentiell große Objekte aufnehmen - und damit dürfte der Nachteil des ungenutzten Speicherplatzes wohl die Performance-Vorteile überwiegen.
    (davon abgesehen, daß die gespeicherte Klasse auch wieder vector-en mitschleppen könnte)

    BTW: du scheinst nicht den ganzen Thread gelesen zu haben, ich hab von Anfang an geschrieben dass std::vector nix vor alloziert 😉

    Hab' ich etwas anderes behauptet?

    0

  • CStoll schrieb:

    BTW: du scheinst nicht den ganzen Thread gelesen zu haben, ich hab von Anfang an geschrieben dass std::vector nix vor alloziert 😉

    Hab' ich etwas anderes behauptet?

    Nein, aber wieso schreibst du MIR Sachen die ich a) schon weiss und auf die ich b) selbst schon hingewiesen habe?

    0
Anmelden zum Antworten