Anatomy of STL Vector: Data Size

In the last post, we discussed the cost of using STL vector to module size. Now let’s take a look at how STL vector manages its data. Dia2Dump (Source code available in Microsoft Visual Studio 8\Dia SDK\Samples\Dia2Dump directory) shows the following internal structure of vector<short:>

 

UDT : std::vector<short,std::allocator<short> >

BaseClass : std::_Vector_val<short,std::allocator<short> >, offset = 0x0

BaseClass : std::_Container_base, offset = 0x0

Data : this+0x0, Member, Type: class std::allocator<short>, _Alval

Data : this+0x4, Member, Type: short *, _Myfirst

Data : this+0x8, Member, Type: short *, _Mylast

Data : this+0xc, Member, Type: short *, _Myend

 

Class vector<short> derives from _Vector_val<short>, which in turn derives from _Container_base. _Vector_val has one member variable, _Alval, which is of the type allocator<short>. Also allocator<short> does not have any member variable; its still occupies 1-byte space. Due to alignment, the cost is rounded up to 4-bytes. Class vector<short> itself has three member variables, all pointers to short. So the total size of a vector<short> is 16-bytes for 32-bit machines, in release build, and 32-bytes for 64-bit machines. The first member variable _Alval is never been actually accessed in release build binary code, not initialized, not referenced. For 32-bit machine, 4 extra bytes are added for debug build.

 

Class vector<T> manages its dynamic storage using three pointers, _Myfirst points to the first allocated slot, _Mylast points to the next free slot, and _Myend points after the last allocated slot. All three are initialized to null pointers. _Myfirst and _Myend change when the vector’s dynamic buffer is allocated or reallocated, their difference is the capacity of the vector. _Mylast changed when new elements are added to the vector. When it reaches _Myend, the vector is full. The difference between _Mylast and _Myfirst is the number of elements in the vector.

 

When not enough space is available in vector to add new elements, allocator<short> is used to allocate new space. Older elements are moved to the new space, empty space is filled with blank, new elements are injected into place, and then finally the old storage space is freed. To avoid large number of reallocations, STL vector tries to grow by 50% each time.

 

The following piece of code tests how STL vector grows when push_back is called repetitively:

 

    std::vector<int> intvector;

    printf("sizeof(vector<int>) %d\n\n", sizeof(intvector));

    size_t lastcap = 0xFFFFFFFF;

    const void * * p = (const void * *) & intvector;

    for (int i = 1; i <= 1000; i ++)

    {

       if (lastcap != intvector.capacity())

        {

            lastcap = intvector.capacity();

            printf("%3d %4d %4d %p %p %p %p \n",

                i, intvector.size(), lastcap, p[0], p[1], p[2], p[3]);

        }

        intvector.push_back(i);

    }

 

The code above measures the size of vector<int> itself and how it manages its dynamic storage. It prints out one line after each time a re-allocation occurs (vector<int>::capacity() changes). Here is the output:

 

sizeof(vector<int>) 16

Seq size() capacity() _Alval _Myfirst _Mylast _Myend

  1 0 0 C1C1C1C1 00000000 00000000 00000000

  2 1 1 C1C1C1C1 00382FE8 00382FEC 00382FEC

  3 2 2 C1C1C1C1 00382FF8 00383000 00383000

  4 3 3 C1C1C1C1 00383008 00383014 00383014

  5 4 4 C1C1C1C1 00383020 00383030 00383030

  6 5 6 C1C1C1C1 00383038 0038304C 00383050

  8 7 9 C1C1C1C1 00383058 00383074 0038307C

 11 10 13 C1C1C1C1 00383088 003830B0 003830BC

 15 14 19 C1C1C1C1 003830C8 00383100 00383114

 21 20 28 C1C1C1C1 00384F90 00384FE0 00385000

 30 29 42 C1C1C1C1 00385008 0038507C 003850B0

 44 43 63 C1C1C1C1 003850B8 00385164 003851B4

 65 64 94 C1C1C1C1 003851C0 003852C0 00385338

 96 95 141 C1C1C1C1 00385340 003854BC 00385574

143 142 211 C1C1C1C1 00385580 003857B8 003858CC

213 212 316 C1C1C1C1 003858D8 00385C28 00385DC8

318 317 474 C1C1C1C1 00385DD0 003862C4 00386538

476 475 711 C1C1C1C1 00386540 00386CAC 0038705C

713 712 1066 C1C1C1C1 00387068 00387B88 00388110

 

From the output, we can see STL vector grows by 50%: 9 + 9/2 = 13, 13 + 13/2 = 19, 19 + 19/2 = 28, … So on average, 25% more space than what’s needed could be not utilitied; while in worst case is 50%. Each time when STL vector needs to grow, it allocates the new space first before freeing the old space; realloc is not called. So the older storage is not reused even when realloc is possible. This can generate lots of heap fragmentation. To avoid these problems, application should call vector::resize or vector::reserve to change how dynamic storage is managed. If push_back is used to grow a vector one element at a time, there will be log(N)/log(1.5) times of memory re-allocation.

 

Here is a summary of STL vector’s data size cost:

                                                                                                                                             

Using STL vector<T>, if push_back is called repetitively:

Data Size Cost (per object) = 4 * sizeof(void *) + // vector<T> object itself

                 sizeof(T) * size() + // real data storage

                      sizeof(T) * size() * 25% + // Average reserved storage

                              log(N) / log(1.5) freed memory blocks in heap // Discarded memory blocks

 

 

PS: The actual command to use Dia2Dump to dump type information is (notice there needs to be a space between two ‘>’s):

 

Dia2Dump.exe -type "std::vector<short,std::allocator<short> >" template.exe

Comments

• Anonymous
  March 04, 2007
  Calling reserve can be tricky as well. If you add elements one by one and call reserve before each, MSVC's implementation increments the vector size by 1 each time, triggering a complete reallocation and copying of all items on every insert.