std :: unordered_map uso de memoria muy alto

Question

Ayer traté de usar unordered_map y este código me confundió la cantidad de memoria que usaba.

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; 
} 

Todas estas partes del código se compilaron en MS VS2010 en modo de depuración. Lo que me han visto en mi administrador de tareas fue de aproximadamente 1200 kb de proceso "limpio", pero después de rellenar hash_map utiliza 8124 kb de memoria. ¿Es el comportamiento normal de unordered_map? ¿Por qué se usa tanta memoria?

Answer 1

La estructura unordered_map está diseñada para contener un gran número de objetos de forma que hace que las incorporaciones, eliminaciones, búsquedas y recorridos sin orden sean eficientes. No pretende ser eficiente con la memoria para estructuras de datos pequeñas. Para evitar las penalizaciones asociadas con el cambio de tamaño, asigna muchas cabezas de cadena hash cuando se crea por primera vez.

Answer 2

Esto no significa necesariamente que el mapa hash utiliza tanta memoria, pero que el proceso ha solicitado mucha memoria del sistema operativo.

Esta memoria se utiliza para satisfacer las solicitudes malloc/nuevas del programa. Algunos (o la mayoría, no estoy seguro de esto) los asignadores de memoria requieren más memoria del sistema operativo de la necesaria en ese momento para la eficiencia.

Para saber cuánta memoria utiliza el mapa no ordenado, utilizaría un generador de perfiles de memoria como perftools.

Answer 3

Eso es aproximadamente 6MB para objetos ~ 20k, entonces 300 bytes por objeto. Dado que la tabla hash puede ser dimensionada para tener varias veces más cubos que las entradas actuales, cada cubeta puede ser un puntero a una lista o vector de objetos en colisión, cada asignación de pila involucrada en todo eso probablemente se haya redondeado al punto más cercano poder de dos, y tienes depuración que puede generar algo de hinchazón adicional, todo me parece correcto.

De todos modos, no obtendrá simpatía por la memoria o la eficiencia de la CPU de nada en la construcción de depuración ;-P. Microsoft puede inyectar cualquier pendiente que les guste allí, y el usuario no tiene derecho a expectativas sobre el rendimiento. Si encuentra que es malo en una compilación optimizada, entonces tiene algo de qué hablar.

De manera más general, cómo se escala con size() es muy importante, pero es completamente legítimo preguntarse cómo un programa iría con una gran cantidad de mapas desordenados relativamente pequeños. Vale la pena señalar que por debajo de un determinado size() incluso las búsquedas de fuerza bruta en un vector, las búsquedas binarias en un vector ordenado, o un árbol binario pueden superar un mapa desordenado, además de ser más eficiente en cuanto a la memoria.