Home
TuningLib
C++ Themen
  std::vector Analyse
  std::vector Resize
English
Impressum

std::vector Performance Analyse

Einleitung

Der std::vector wird in C++-Programmen sehr häufig verwendet. Viele Programmierer wissen jedoch nicht, daß dieses Container-Template ein schlechtes Laufzeitverhalten hat und für größere Datenmengen nicht geeignet ist.

Dokumentation: cppreference.com

Protokollklasse

Das Laufzeitverhalten vom std::vector untersuchen wir mit einer geschwätzigen Protokollklasse, die ausführlich über alle Ereignisse aus ihrem C++-Leben berichtet. 

  class Chatterbox
    {
    int i;
  public:
    Chatterbox ()
      { cout << "+ Chatterbox" << endl; i = 0; }
    Chatterbox (int init)
      { cout << "+ Chatterbox " << init << endl; i = init; }
    Chatterbox (const Chatterbox & cp)
      { cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
    ~Chatterbox ()
      { cout << "- Chatterbox " << i << endl; }
    Chatterbox & operator = (const Chatterbox & asgn)
      { cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }  
    };

Beispieldaten

Am Anfang von unserem kleinen Testprogramm werden ein paar Beispielobjekte angelegt. 

  cout << "Construct samples" << endl;  
  Chatterbox cb1 (1);
  Chatterbox cb2 (2);
  Chatterbox cb3 (3);
  Chatterbox cb4 (4);
  Chatterbox cb5 (5);

Output:

Construct samples
+ Chatterbox 1
+ Chatterbox 2
+ Chatterbox 3
+ Chatterbox 4
+ Chatterbox 5

Testvector

Der Testvector wird am Anfang eines geschachtelten Blocks angelegt, damit wir am Ende des Scopes den Destruktor beobachten können. 

  {
  vector <Chatterbox> cbvec;

Ein- und Anfügen

Wenn sich die Größe des internen Speicherblocks ändert, dann wird der vorhandene Block nicht reallokiert. Stattdessen wird ein neuer Block allokiert, und alle vorhandenen Elemente werden mit dem Copy-Konstruktor dort hinein kopiert. Anschließend werden die Destruktoren der bisherigen Objekte aufgerufen und der bisherige Speicherblock wird freigegeben. Dieses Verhalten ist unabhängig davon, ob das neue Element am Anfang, in der Mitte oder am Ende eingefügt wird. 

  cout << "--------------" << endl;
  cout << "Append cb 3" << endl;
  cbvec. push_back (cb3);

  cout << "--------------" << endl;
  cout << "Insert cb 2" << endl;
  cbvec. insert (cbvec. begin (), cb2);  

  cout << "--------------" << endl;
  cout << "Append cb 4" << endl;
  cbvec. push_back (cb4);

  cout << "--------------" << endl;
  cout << "Insert cb 1" << endl;
  cbvec. insert (cbvec. begin (), cb1);

  cout << "--------------" << endl;
  cout << "Append cb 5" << endl;
  cbvec. push_back (cb5);

Output:

--------------
Append cb 3
+ Chatterbox cp 3
--------------
Insert cb 2
+ Chatterbox cp 2
+ Chatterbox cp 3
- Chatterbox 3
--------------
Append cb 4
+ Chatterbox cp 4
+ Chatterbox cp 2
+ Chatterbox cp 3
- Chatterbox 2
- Chatterbox 3
--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4

Elemente löschen

Beim Löschen von Elementen werden die vorhandenen Elemente mit dem Assignment-Operator an eine neue Stelle kopiert. Die Anzahl der internen Kopieroperationen ist abhängig von der Position, an der der Vector-Container verändert wird.
Der überschüssige Speicher wird i.a. nicht automatisch freigegeben. Zum Freigeben dieses Speichers muß explizit shrink_to_fit aufgerufen werden. 

  cout << "--------------" << endl;  
  cout << "Remove first" << endl;
  cbvec. erase (cbvec. begin ());

  cout << "--------------" << endl;
  cout << "Remove last" << endl;
  cbvec. pop_back ();

Output:

--------------
Remove first
. Chatterbox = 2
. Chatterbox = 3
. Chatterbox = 4
. Chatterbox = 5
- Chatterbox 5
--------------
Remove last
- Chatterbox 5

Ein- und Anfügen im freien Speicher

Wenn im internen Speicherblock noch freier Platz vorhanden ist (z.B. wegen vorangegangener Löschoperationen), dann ist das Verhalten des Vector-Containers beim Ein- und Anfügen sehr ähnlich wie beim Löschen. 

  cout << "--------------" << endl;
  cout << "Insert cb 1" << endl;
  cbvec. insert (cbvec. begin (), cb1);  

  cout << "--------------" << endl;
  cout << "Append cb 5" << endl;
  cbvec. push_back (cb5);

Output:

--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 4
. Chatterbox = 3
. Chatterbox = 2
. Chatterbox = 1
- Chatterbox 1
--------------
Append cb 5
+ Chatterbox cp 5

Interne Größe explizit ändern

Wenn man die Größe des internen Speicherblocks explizit ändert, dann wird der vorhandene Block (wie oben beschrieben) nicht reallokiert. Stattdessen wird ein neuer Block allokiert, und alle vorhandenen Elemente werden mit dem Copy-Konstruktor dort hinein kopiert. 

  cout << "--------------" << endl;  
  cout << "Reserve" << endl;
  cbvec. reserve (10);

  cout << "--------------" << endl;
  cout << "Shrink" << endl;
  cbvec. shrink_to_fit ();

Output:

--------------
Reserve
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
+ Chatterbox cp 5
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5
--------------
Shrink
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
+ Chatterbox cp 5
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5

Destruktor

Am Ende des geschachtelten Block-Scopes wird der Destruktor des Vector-Containers ausgeführt. Dieser ruft die Destruktoren aller enthaltenen Elemente auf. 

  cout << "--------------" << endl;
  cout << "Destruct vector" << endl;  
  }

Output:

--------------
Destruct vector
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
- Chatterbox 5

Beispieldaten löschen

Am Ende unseres kleinen Testprogramms werden die Beispielobjekte gelöscht, die wir ganz am Anfang angelegt hatten. 

  cout << "--------------" << endl;
  cout << "Destruct samples" << endl;  
  return 0;

Output:

--------------
Destruct samples
- Chatterbox 5
- Chatterbox 4
- Chatterbox 3
- Chatterbox 2
- Chatterbox 1

Compiler-Unterschiede

Der oben gezeigte Output des Testprogramms wurde mit dem MSVC-Compiler Version 2022 erzeugt. Bei anderen Compilern ist das Rechenergebnis (der Inhalt vom Vector-Container) stets dasselbe. Die Wege dorthin, also die internen Zwischenschritte, können aber sehr unterschiedlich sein. Beim g++-Compiler 11.2.0 gibt es z.B. beim erstmaligen Einfügen vom Objekt 1 kein Neu-Allokieren und komplettes Umkopieren.

Output:

--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox cp 4
. Chatterbox = 3
. Chatterbox = 2
. Chatterbox = 1
- Chatterbox 1

C++11 Move Semantics

Wenn wir in unserer geschwätzigen Protokollklasse die C++11 Move Semantics ergänzen, dann ruft der Compiler in einigen (nicht in allen) Fällen statt des Copy-Konstruktors den Move-Konstruktor auf und statt des Assignment-Operators den Move-Assignment-Operator. Anzahl und Reihenfolge der Aufrufe bleiben jedoch gleich. 

  class Chatterbox
    {
    int i;
  public:
    Chatterbox ()
      { cout << "+ Chatterbox" << endl; i = 0; }
    Chatterbox (int init)
      { cout << "+ Chatterbox " << init << endl; i = init; }
    Chatterbox (const Chatterbox & cp)
      { cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
    Chatterbox (Chatterbox && mv)
      { cout << "+ Chatterbox mv " << mv. i << endl; i = mv. i; }
    ~Chatterbox ()
      { cout << "- Chatterbox " << i << endl; }
    Chatterbox & operator = (const Chatterbox & asgn)
      { cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }  
    Chatterbox & operator = (Chatterbox && mv)
      { cout << ". Chatterbox mv = " << mv. i << endl; i = mv. i; return * this; }
    };

Beispiel Output, erstmaliges Einfügen von Objekt 1 und 5:

--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox cp 1
+ Chatterbox cp 2
+ Chatterbox cp 3
+ Chatterbox cp 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4

C++11 Move Semantics mit noexcept

Wenn wir den Move-Konstruktor und den Move-Assignment-Operator zusätzlich mit noexcept kennzeichnen, dann werden diese Funktionen vom std::vector häufiger aufgerufen.
Beachte aber folgendes:

  • Es handelt sich um ein undokumentiertes Feature, das funktionieren kann oder auch nicht.
  • Die Anzahl der internen Zwischenschritte bleibt gleich, es sind eben nur andere Schritte.
  • In einigen Fällen können Move-Konstruktor und Move-Assignment-Operator Exceptions werfen und dürfen nicht mit noexcept gekennzeichnet werden. 

  class Chatterbox
    {
    int i;
  public:
    Chatterbox ()
      { cout << "+ Chatterbox" << endl; i = 0; }
    Chatterbox (int init)
      { cout << "+ Chatterbox " << init << endl; i = init; }
    Chatterbox (const Chatterbox & cp)
      { cout << "+ Chatterbox cp " << cp. i << endl; i = cp. i; }
    Chatterbox (Chatterbox && mv) noexcept
      { cout << "+ Chatterbox mv " << mv. i << endl; i = mv. i; }
    ~Chatterbox ()
      { cout << "- Chatterbox " << i << endl; }
    Chatterbox & operator = (const Chatterbox & asgn)
      { cout << ". Chatterbox = " << asgn. i << endl; i = asgn. i; return * this; }  
    Chatterbox & operator = (Chatterbox && mv) noexcept
      { cout << ". Chatterbox mv = " << mv. i << endl; i = mv. i; return * this; }
    };

Beispiel Output, erstmaliges Einfügen von Objekt 1 und 5:

--------------
Insert cb 1
+ Chatterbox cp 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4
--------------
Append cb 5
+ Chatterbox cp 5
+ Chatterbox mv 1
+ Chatterbox mv 2
+ Chatterbox mv 3
+ Chatterbox mv 4
- Chatterbox 1
- Chatterbox 2
- Chatterbox 3
- Chatterbox 4

Hintergrund-Infos

Dokumentation: cppreference.com

Der C++-Standard ISO/IEC 14882 beschreibt in der Version C++20 die Klasseneigenschaften "trivially copyable" (6.8, 11.2.1) und "standard-layout" (11.2.5). In früheren Versionen gab es noch die Eigenschaft POD (Plain Old Data, 14882:2017 6.9.9), seit C++20 wird dieser Begriff nicht mehr verwendet.
Gemäß C++20 6.8 können "trivially copyable" Objekte mit memcpy und memmove im Speicher kopiert und verschoben werden. Über andere Objekte gibt es keine Aussage.

Für Container-Templates wie std::vector beschreibt der C++-Standard das Interface und das Verhalten. Die konkrete Implementierung bleibt dem Compilerbauer überlassen. Ein std::vector muß beliebige C++-Objekte verarbeiten können, nicht nur "trivially copyable". Deshalb verwenden die Implementierungen weder realloc noch memcpy und memmove.

Siehe auch: C++ Object relocation, Published Proposal
"It is intended that most standard library types be trivially relocatable types."

Mögliche Optimierungen

In der Praxis können fast alle C++-Objekte mit memcpy und memmove an eine andere Stelle im Speicher verschoben werden. Beachte: Es geht hier um das Verschieben von kompletten Objekten ("most derived object", C++20 6.7.2.2, 6.7.2.6) und nicht um "potentially-overlapping subobjects" (C++20 6.7.2.7). Ein Container wie std::vector enthält stets komplette Objekte. Beachte weiterhin: Es geht hier um das Verschieben von Elementen innerhalb eines dynamischen Array-Containers (Verschieben an eine andere Stelle im Speicher) und nicht um das Duplizieren von Objekten mit memcpy.

Zum Verbessern der Performance von dynamischen Arrays gibt es u.a. die folgenden Möglichkeiten:

  • Beim Einfügen/Löschen werden die nachfolgenden Objekte mit memmove verschoben.
  • Beim Ändern der Größe wird der interne Speicherblock reallokiert.
  • Mit einer optimierten Speicherverwaltung werden Reallokationen und Fragmentierung reduziert.

Quelltext

Hier ist noch der vollständige Quelltext der drei Testprogramme ohne und mit Move Semantics:

01_vector1.cpp
01_vector2.cpp
01_vector3.cpp


© 2023 Dietmar Deimling