std::vector Size and Resize

Introduction

The second part of the study looks at the size and the resize behavior of std::vector. Both properties are undocumented. They will be analyzed by a little test program. Pay attention to use release compiler options. In debug mode we possibly get different results.

Object size

Now, let's look at the size of the vector object itself.

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

Output MSVC compiler version 2022 (64 bit):

  SizeOf: 24  

Using the g++ compiler 12.2.0 (64 bit) we get the same result. The vector object probably consists of three 64 bit values (pointer or integer).

Possible optimizations

In some scenarios, data structures contain a large amount of dynamic arrays, but the arrays are mostly empty. In such cases we should try to optimize the size of the object itself. The std::vector template can be customized with an alternative allocator. Unfortunately, this has no effect on the object size and the resize behavior.

For such use cases, the Spirick Tuning library provides the MiniBlock concept. A MiniBlock object (and a derived array container) only contains a pointer to the dynamic storage. The block size is stored inside of the dynamic memory block. The size variable only consumes memory if the block size is greater than zero.

Resize behavior

During the first part of the study, we found out that a std::vector resize is very expensive. To reduce the number of resize operations, the size of the internal memory block is mostly greater than required. The method capacity returns the current size of the internal memory block (number of elements). The method reserve sets the size to at least n elements. The method shrink_to_fit releases unused memory at the end of the internal memory block.

The resize behavior of std::vector is undocumented, that's why we use a little test program. The size of the test vector is increased stepwise. Afterwards, it will be decreased stepwise. During the test, we observe the size of the internal memory block.

  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 both cases, the unused memory is not released automatically. We will try clear first and shrink_to_fit afterwards.

  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

std::string Analysis

std::vector<char> and std::string are two very similar concepts. Both classes provide some equal-named methods. All the tests above can also be applied for std::string.

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

Apparently, current C++ compilers implement the so-called Short String Optimization (SSO). Small strings are stored in an internal buffer (without dynamic allocation). Unfortunately, this feature is not configurable. In some cases, the SSO is helpful. In other cases, string objects may waste a huge amount of memory.

Missing generalization

In object-oriented design, we try to move re-usable functionality of several classes, e.g. std::vector and std::string, into a common base class. In the C++ standard library this problem remains unresolved.

For such use cases, the Spirick Tuning library provides the Block concept. The Block interface is a simple object-oriented concept of managing a single memory block. Block classes are used as template parameters of strings and arrays, and they can be used otherwise.

Source code

Here is the source code of the small test program:

02_vector.cpp

© 2023 Dietmar Deimling