Как я могу оценить использование памяти std :: map?

Question

Например, у меня есть std :: map с известными sizeof (A) и sizeof (B), тогда как map содержит N записей внутри. Как бы вы оценили использование памяти? Я бы сказал, что-то вроде

(sizeof(A) + sizeof(B)) * N * factor

Но каков фактор? Может быть, другая формула?

Может быть, проще задать верхнюю границу?

Answer 1

Оценка будет ближе к

(sizeof(A) + sizeof(B) + ELEMENT_OVERHEAD) * N + CONTAINER_OVERHEAD

Для каждого добавляемого элемента есть издержки, а также есть фиксированные накладные расходы на поддержку структуры данных, используемой для структуры данных, хранящей карту. Обычно это двоичное дерево, такое как Красно-Черное дерево . Например, в GCC C ++ STL реализация ELEMENT_OVERHEAD будет sizeof(_Rb_tree_node_base), а CONTAINER_OVERHEAD будет sizeof(_Rb_tree). К приведенному выше рисунку вы также должны добавить накладные расходы на структуры управления памятью, используемые для хранения элементов карты.

Вероятно, проще получить оценку, измерив потребление памяти вашим кодом для различных больших коллекций.

Answer 2

Вы можете использовать MemTrack , Кертис Бартли. Это распределитель памяти, который заменяет один по умолчанию и может отслеживать использование памяти вплоть до типа выделения.

Пример вывода:

-----------------------
Memory Usage Statistics
-----------------------

allocated type                        blocks          bytes  
--------------                        ------          -----  
struct FHRDocPath::IndexedRec          11031  13.7% 2756600  45.8%
class FHRDocPath                       10734  13.3%  772848  12.8%
class FHRDocElemPropLst                13132  16.3%  420224   7.0%
struct FHRDocVDict::IndexedRec          3595   4.5%  370336   6.2%
struct FHRDocMDict::IndexedRec         13368  16.6%  208200   3.5%
class FHRDocObject *                      36   0.0%  172836   2.9%
struct FHRDocData::IndexedRec            890   1.1%  159880   2.7%
struct FHRDocLineTable::IndexedRec       408   0.5%  152824   2.5%
struct FHRDocMList::IndexedRec          2656   3.3%  119168   2.0%
class FHRDocMList                       1964   2.4%   62848   1.0%
class FHRDocVMpObj                      2096   2.6%   58688   1.0%
class FHRDocProcessColor                1259   1.6%   50360   0.8%
struct FHRDocTextBlok::IndexedRec        680   0.8%   48756   0.8%
class FHRDocUString                     1800   2.2%   43200   0.7%
class FHRDocGroup                        684   0.8%   41040   0.7%
class FHRDocObject * (__cdecl*)(void)     36   0.0%   39928   0.7%
class FHRDocXform                        516   0.6%   35088   0.6%
class FHRDocTextColumn                   403   0.5%   33852   0.6%
class FHRDocTString                      407   0.5%   29304   0.5%
struct FHRDocUString::IndexedRec        1800   2.2%   27904   0.5%

Answer 3

Если вы действительно хотите знать объем оперативной памяти, используйте специальный распределитель и передайте его при создании карты. См. Книгу Джосуттиса и эту страницу его (для пользовательского распределителя).

Может быть, проще задать верхнюю границу?

Верхняя граница будет зависеть от точной реализации (например, от конкретного варианта использования сбалансированного дерева). Может быть, вы можете сказать нам, почему вам нужна эта информация, чтобы мы могли лучше помочь?

Answer 4

Мне недавно нужно было ответить на этот вопрос для себя, и я просто написал небольшую тестовую программу, используя std :: map, которую я скомпилировал в MSVC 2012 в 64-битном режиме.

Карта с 150 миллионами узлов, пропитанными ~ 15 ГБ, что подразумевает 8-байтовый L, 8-байтовый R, 8-байтовый ключ int и 8-байтовый набор данных, всего 32 байта, впитавший около 2/3 память карты для внутренних узлов, оставляя 1/3 для листьев.

Лично я обнаружил, что это удивительно плохая эффективность памяти, но это то, что есть.

Надеюсь, это пригодится для практического использования.

PS: издержки std :: map - это размер AFAICT одного узла.

Answer 5

Формула больше похожа на:

(sizeof(A) + sizeof(B) + factor) * N

где коэффициент - это накладные расходы на каждую запись. Карты C ++ обычно реализуются в виде красно-черных деревьев. Это двоичные деревья, поэтому для левого / правого узла будет как минимум два указателя. Также будут некоторые вещи реализации - вероятно, родительский указатель и индикатор «цвета», поэтому коэффициент может быть что-то вроде

(sizeof( RBNode *) * 3 + 1) / 2

Однако все это в значительной степени зависит от реализации - чтобы убедиться, что вам действительно нужно изучить код для реализации собственной библиотеки.

Answer 6

Размер карты действительно зависит от реализации карты. У вас могут быть разные размеры на разных компиляторах / платформах, в зависимости от того, какую реализацию STL они предоставляют.

Зачем вам нужен этот размер?