std::vector Größe und Resize

Einleitung

Im zweiten Teil der Analyse betrachten wir die Größe und das Resize-Verhalten vom std::vector. Beide Eigenschaften sind nicht dokumentiert. Für die Untersuchung muß ein kleines Testprogramm verwendet werden. Beim Compilieren ist auf Release-Optionen zu achten. Im Debug-Modus haben solche Klassen manchmal ein abweichendes Verhalten.

Objektgröße

Am Anfang unseres kleinen Testprogramms untersuchen wir die Größe des vector-Objekts an sich.

  vector <MyPoint3D> vec3d;
  cout << "  SizeOf: " << sizeof (vec3d) << endl;  

Output MSVC-Compiler Version 2022 (64 Bit):

  SizeOf: 24  

Der g++-Compiler 12.2.0 (64 Bit) liefert genau denselben Output. Das vector-Objekt besteht vermutlich aus drei 64-Bit-Werten (Pointer oder Integer), dokumentiert ist es aber nicht.

Optimierungsmöglichkeiten

In einigen Szenarien gibt es sehr viele dynamische Array-Objekte, die schwach belegt sind, d.h. es gibt sehr viele leere Arrays. In solchen Anwendungsfällen sollte man versuchen, die Größe des Array-Objekts an sich zu optimieren. Das std::vector-Template kann zwar mit einem Allocator konfiguriert werden, dieser hat aber keinen Einfluß auf die Objektgröße oder das Resize-Verhalten.

In der Bibliothek Spirick Tuning gibt es für solche Anwendungsfälle das MiniBlock-Konzept. Ein MiniBlock-Objekt (und ein davon abgeleiteter Array-Container) enthält lediglich einen Pointer auf den dynamischen Speicherbereich. Die Blockgröße ist nicht im Objekt, sondern im Speicherblock untergebracht und belegt nur dann Speicher, wenn die Größe ungleich Null ist.

Resize-Verhalten

Im ersten Teil der Analyse hatten wir gesehen, daß beim std::vector der Resize eine rel. aufwendige Operation ist. Zum Minimieren der Anzahl der Resize-Operationen ist der interne Speicherblock meist größer als erforderlich. Die Methode capacity liefert die aktuelle Größe des internen Speicherblocks (Anzahl der Elemente). Mit reserve wird dieser Block auf eine bestimmte Mindestgröße gesetzt, und mit shrink_to_fit wird ungenutzter Speicher am Ende des Blocks freigegeben.

Das Resize-Verhalten vom std::vector ist nicht dokumentiert, deshalb untersuchen wir es mit Hilfe unseres kleinen Testprogramms. Der Testvector wird zuerst schrittweise vergrößert und danach wieder schrittweise verkleinert. Unterwegs beobachten wir die Größe des internen Speicherblocks und melden jede Veränderung.

  cout << "  Size: " << vec3d. size () << " Cap: " << vec3d. capacity () << endl;  
  size_t u_cap = vec3d. capacity ();
  cout << "  Cap inc: ";

  for (unsigned u = 0; u < 1000; u ++)
    {
    vec3d. push_back (p1);

    if (vec3d. capacity () != u_cap)
      {
      u_cap = vec3d. capacity ();
      cout << " " << u_cap;
      }
    }

  cout << endl;
  cout << "  Cap dec: ";

  for (unsigned u = 0; u < 1000; u ++)
    {
    vec3d. pop_back ();

    if (vec3d. capacity () != u_cap)
      {
      u_cap = vec3d. capacity ();
      cout << " " << u_cap;
      }
    }

  cout << endl;
  cout << "  Size: " << vec3d. size () << " Cap: " << vec3d. capacity () << endl;

Output MSVC-Compiler Version 2022 (64 Bit):

  Size: 0 Cap: 0
  Cap inc:  1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066  
  Cap dec: 
  Size: 0 Cap: 1066

Output g++-Compiler 12.2.0 (64 Bit):

  Size: 0 Cap: 0
  Cap inc:  1 2 4 8 16 32 64 128 256 512 1024  
  Cap dec: 
  Size: 0 Cap: 1024

In beiden Fällen wird der ungenutzte Speicher nicht automatisch freigegeben. Wir versuchen es zuerst mit clear und dann mit shrink_to_fit.

  vec3d. clear ();
  cout << "  Clear, Size: " << vec3d. size () << " Cap: " << vec3d. capacity () << endl;
  vec3d. shrink_to_fit ();
  cout << "  Shrink, Size: " << vec3d. size () << " Cap: " << vec3d. capacity () << endl;  

Output MSVC-Compiler Version 2022 (64 Bit):

  Clear, Size: 0 Cap: 1066  
  Shrink, Size: 0 Cap: 0

Output g++-Compiler 12.2.0 (64 Bit):

  Clear, Size: 0 Cap: 1024  
  Shrink, Size: 0 Cap: 0

Analyse std::string

std::vector<char> und std::string sind zwei sehr ähnliche Konzepte. Beide Klassen haben mehrere gleichlautende Methoden, die genau denselben Zweck erfüllen. Die o.g. Tests können auch mit std::string durchgeführt werden.

Output MSVC-Compiler Version 2022 (64 Bit):

  SizeOf: 32
  Size: 0 Cap: 15
  Cap inc:  31 47 70 105 157 235 352 528 792 1188  
  Cap dec: 
  Size: 0 Cap: 1188
  Clear, Size: 0 Cap: 1188
  Shrink, Size: 0 Cap: 15

Output g++-Compiler 12.2.0 (64 Bit):

  SizeOf: 32
  Size: 0 Cap: 15
  Cap inc:  30 60 120 240 480 960 1920  
  Cap dec: 
  Size: 0 Cap: 1920
  Clear, Size: 0 Cap: 1920
  Shrink, Size: 0 Cap: 15

Aktuelle C++-Compiler implementieren offenbar die sog. Short String Optimization (SSO). Kleine Strings bis zu einer bestimmten Größe werden in einem internen Buffer untergebracht. Für solche Strings muß kein dynamischer Speicher allokiert werden. Leider ist dieses Feature nicht konfigurierbar. In Anwendungsfällen mit vielen leeren Strings belegen die String-Objekte unnötig viel Speicher.

Fehlende Verallgemeinerung

Beim objektorientierten Design versucht man normalerweise, ähnliche Eigenschaften mehrerer Klassen, z.B. std::vector und std::string, in eine gemeinsame Basisklasse auszulagern. In der C++-Standardbibliothek ist es nach über 30 Jahren Entwicklung leider noch nicht gelungen.

In der Bibliothek Spirick Tuning gibt es zu diesem Zweck das Block-Konzept. Ein Block ist ein Objekt, das einen einzelnen Speicherbereich verwaltet. Blockklassen dienen als Templateparameter für Strings und Arrays und können auch anderweitig verwendet werden.

Quelltext

Hier ist noch der vollständige Quelltext des kleinen Testprogramms:

02_vector.cpp

© 2023 Dietmar Deimling