std :: unordered_map очень высокое использование памяти

Question

Вчера я пытался использовать std::unordered_map, и этот код смутил меня, сколько памяти он использовал.

typedef list<string> entityId_list;
struct tile_content {
   char cost;
   entityId_list entities;
};
unordered_map<int, tile_content> hash_map;

for (size_t i = 0; i < 19200; i++) {
   tile_content t;
   t.cost = 1;
   map[i] = t;
}

Все эти части кода были скомпилированы в MS VS2010 в режиме отладки. То, что я видел в моем диспетчере задач, было около 1200 КБ «чистого» процесса, но после заполнения hash_map он использует 8124 КБ памяти. Это нормальное поведение unordered_map? Почему используется так много памяти?

Answer 1

Это примерно 6 МБ для ~ 20 тыс. Объектов, то есть 300 байт на объект.Учитывая, что хэш-таблица может иметь размер, который может иметь в несколько раз больше сегментов, чем текущие записи, каждый блок может сам по себе быть указателем на список или вектор сталкивающихся объектов, причем каждое выделение кучи, вовлеченное во все это, вероятно, было округлено до ближайшегоСтепень двойки, и у вас есть отладка, которая может привести к некоторому дополнительному вздутию, все это звучит как раз для меня.

В любом случае, вы не получите симпатии к эффективности памяти или процессора чего-либов отладочной сборке ;-P.Microsoft может внедрить в нее любое помои, которые им нравятся, и пользователь не имеет права ожидать от производительности.Если вы обнаружите, что это плохо в оптимизированной сборке, вам есть о чем поговорить.

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

Answer 2

Структура unordered_map предназначена для хранения большого количества объектов таким образом, чтобы обеспечить эффективное добавление, удаление, поиск и упорядоченный обход.Он не предназначен для эффективного использования памяти для небольших структур данных.Чтобы избежать штрафов, связанных с изменением размера, при первом создании он выделяет много заголовков цепочки хэшей.

Answer 3

Это не обязательно означает, что хэш-карта использует так много памяти, но процесс запросил столько памяти у ОС.

Затем эта память используется для удовлетворения запросов malloc / newпрограмма.Некоторым (или большинству, я не уверен в этом) распределителям памяти требуется больше памяти от ОС, чем требовалось в данный момент для эффективности.

Чтобы узнать, сколько памяти используется unordered_map, я бы использовалпрофилировщик памяти типа perftools .