Сколько памяти может потреблять std::vector при расширении? ⇐ C++

[Anonymous]

В большинстве компиляторов Linux std::vector будет расширяться в 2 раза. Я проверял это на g++11.
Итак, я предполагаю что при расширении std::vector от N до 2N произойдет следующее:

• Вектор достигнет своего предела в N. Он потребляет X байт памяти.< /li>
  Вектор выделит 2*X байт памяти для массива из 2*N элементов. Таким образом, вектор может занимать в общей сложности 3*X байт.
• Вектор копирует или перемещает элементы из исходного массива размера N в массив 2*N.
• Вектор разрушает исходный массив. Таким образом, теперь ему требуется 2*X байт памяти.

В заключение, пиковое использование памяти вектором должно составлять 3*X. Итак, я пишу следующие коды, чтобы проверить это поведение.
В коде мы поместим 2 миллиона экземпляров Writes в вектор. И буду использовать getPeakRSS для записи максимального использования памяти в этой программе.
Время от времени я буду печатать текущее использование памяти. Информация об использовании взята из getPeakRSS. Ожидаемое вычисляется путем умножения размера записи и текущего счетчика вектора ww. Поле amp указывает на использование/ожидание. Если я прав, то максимальное значение amp составляет около 3.

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 

struct Writes16 {
uint64_t w1;
uint64_t w2;
};

struct Writes32 {
Writes16 w1;
Writes16 w2;
};

struct Writes128 {
Writes32 w1;
Writes32 w2;
Writes32 w3;
Writes32 w4;
};

struct Writes {
Writes128 w1;
Writes16 w2;
uint64_t w3;
};

/*
* Author:  David Robert Nadeau
* Site:    http://NadeauSoftware.com/
* License: Creative Commons Attribution 3.0 Unported License
*          http://creativecommons.org/licenses/by/3.0/deed.en_US
*/

#if defined(_WIN32)
#include 
#include

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
#include 
#include 

#if defined(__APPLE__) && defined(__MACH__)
#include 

#elif (defined(_AIX) || defined(__TOS__AIX__)) || (defined(__sun__) || defined(__sun) || defined(sun) && (defined(__SVR4) || defined(__svr4__)))
#include 
#include 

#elif defined(__linux__) || defined(__linux) || defined(linux) || defined(__gnu_linux__)
#include 

#endif

#else
#error "Cannot define getPeakRSS( ) or getCurrentRSS( ) for an unknown OS."
#endif

/**
* Returns the peak (maximum so far) resident set size (physical
* memory use) measured in bytes, or zero if the value cannot be
* determined on this OS.
*/
size_t getPeakRSS( )
{
#if defined(_WIN32)
/* Windows -------------------------------------------------- */
PROCESS_MEMORY_COUNTERS info;
GetProcessMemoryInfo( GetCurrentProcess( ), &info, sizeof(info) );
return (size_t)info.PeakWorkingSetSize;

#elif (defined(_AIX) || defined(__TOS__AIX__)) || (defined(__sun__) || defined(__sun) || defined(sun) && (defined(__SVR4) || defined(__svr4__)))
/* AIX and Solaris ------------------------------------------ */
struct psinfo psinfo;
int fd = -1;
if ( (fd = open( "/proc/self/psinfo", O_RDONLY )) == -1 )
return (size_t)0L;      /* Can't open? */
if ( read( fd, &psinfo, sizeof(psinfo) ) != sizeof(psinfo) )
{
close( fd );
return (size_t)0L;      /* Can't read? */
}
close( fd );
return (size_t)(psinfo.pr_rssize * 1024L);

#elif defined(__unix__) || defined(__unix) || defined(unix) || (defined(__APPLE__) && defined(__MACH__))
/* BSD, Linux, and OSX -------------------------------------- */
struct rusage rusage;
getrusage( RUSAGE_SELF, &rusage );
#if defined(__APPLE__) && defined(__MACH__)
return (size_t)rusage.ru_maxrss;
#else
return (size_t)(rusage.ru_maxrss * 1024L);
#endif

#else
/* Unknown OS ----------------------------------------------- */
return (size_t)0L;          /* Unsupported.  */
#endif
}

std::vector ww;

int main() {
static_assert(sizeof(Writes) == 152);
const size_t K = 1024;
const size_t M = 1024 * K;
size_t location = 0;
for (int m = 0; m < 2; m++) {
for (int j = 0; j < M; j++) {
ww.emplace_back(Writes());
if (j % 4096 == 0) {
if (j == 0) {
location = (size_t)&ww[0];
}
size_t usage = getPeakRSS();
size_t expected = ww.size() * 152;
double rate = usage * 1.0 / expected;
printf("Current memory usage %d: %u %.4fMB expected %u %.4fMB amp %.4f cap %u\n", m, usage, usage / 1024.0 / 1024.0, expected, expected / 1024.0 / 1024.0, rate, ww.capacity());
}
}
}
// To ensure the elements are copied. There is no realloc happening.
printf("Location prev %u end %u\n", location, (size_t)&ww[0]);
return 0;
}

Однако я обнаружил следующее. Похоже, что во время расширения максимальное использование памяти составляет всего 2*X байт, а не 3*X.

Код: Выделить всё

...
Current memory usage 0: 163250176 155.6875MB expeted 158761112 151.4064MB amp 1.0283 cap 1048576
Current memory usage 1: 322584576 307.6406MB expeted 159383704 152.0001MB amp 2.0239 cap 2097152
...

Интересно, почему сохраняются лишние X байты?
=====
Я понимаю, что то, как расширяется std::vector, полностью зависит от компилятора. Поэтому я хочу знать, какая оптимизация может произойти в g++, что приведет к «устранению» некоторых выделений памяти.

Подробнее здесь: https://stackoverflow.com/questions/788 ... -expanding