Расширение STL Vector

При создании пустого вектора размер буфера для хранения элементов равен нулю. Для того, чтобы делать расширения буфера реже, при добавления небольшого количества элементов не помещающихся в буфер, последний увеличивается с запасом. Стандарт не регламентирует какой должен быть новый размер буфера, оставляя это реализациям:

vector::push_back()
“Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation
happens, all the iterators and references before the insertion point remain valid. If an exception is
thrown other than by the copy constructor or assignment operator of T or by any InputIterator
operation there are no effects” [1]

В libstdc++ 4.4.3 это реализовано следующим образом:
libstdc++-v3/include/bits/stl_vector.h +1133

size_type _M_check_len(size_type __n, const char* __s) const
{
if (max_size() - size() < __n)
__throw_length_error(__N(__s));
const size_type __len = size() + std::max(size(), __n);
return (__len max_size()) ? max_size() : __len;
}

Т.е. увеличение вдвое если добавляем по одному элементу.

В Sun Compiler увеличение ~1.618 [3] что приближено к (1+sqrt(5))/2 – это полезно для first-fit схем выделения памяти (упрощенно говоря, чтобы размер n+2 выделенного блока был меньше или равен сумме размеров блоков n и n+1, и это наглядно видно табличке в [3] ). Так же видно что Sun Compiler при первом выделении создает буфер размером 32 элемента, а не 2, таким образом избегая сразу 4 расширений, за счет большего потребления памяти.

“В Visual C++ 6.0 взята константа 2. Такой коэффицент использовать пробелы не дает. А вот в Visual C++ 7 уже используется константа 1.5.” [2]

Tip для GCC:
При создании вектора выделять память под 32 элемента.

Copy Source | Copy HTML

  1. #include <vector>
  2.  
  3. // Exp. 1
  4. // #define PRE_SIZE 0
  5.  
  6. // Exp. 2
  7. // #define PRE_SIZE 32
  8. int main(){
  9.     for(int i=0; i<10000000; ++i){
  10.         std::vector<int> v;
  11.         v.reserve(PRE_SIZE);
  12.         for(int k=0; k<50; ++k)
  13.             v.push_back(k);
  14.     }
  15.     return 0;
  16. }

# g++ 7.cpp
# time ./1.out
real 0m32.495s
user 0m32.350s
sys 0m0.120s

# g++ 7.cpp
# time ./2.out
real 0m14.853s
user 0m14.800s
sys 0m0.040s

# g++ 7.cpp -O2 -felide-constructors -fno-exceptions -fno-rtti -funroll-loops -ffast-math -fomit-frame-pointer -march=opteron
# time ./1.out
real 0m9.232s
user 0m8.970s
sys 0m0.050s

# g++ 7.cpp -O2 -felide-constructors -fno-exceptions -fno-rtti -funroll-loops -ffast-math -fomit-frame-pointer -march=opteron
# time ./2.out
real 0m2.669s
user 0m2.670s
sys 0m0.000s

Источники:

1. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3035.pdf

2. http://alenacpp.blogspot.com/2005/06/vector_30.html

3. http://easy-coding.blogspot.com/2010/03/stdvector.html

Advertisements

One thought on “Расширение STL Vector

  1. Pingback: C/C++ memory management – realloc and mremap | Tech notes

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s