c++ stl c++11 hashmap concurrenthashmap

c++ - ¿Es lenta la implementación de gcc std:: unordered_map? Si es así, ¿por qué?



stl c++11 (3)

Encontré la razón: ¡es un problema de gcc-4.7!

Con gcc-4.7

inserts: 37728 get : 2985

Con gcc-4.6

inserts: 2531 get : 1565

Entonces std::unordered_map en gcc-4.7 está roto (o mi instalación, que es una instalación de gcc-4.7.0 en Ubuntu - y otra instalación que es gcc 4.7.1 en pruebas de Debian).

Enviaré un informe de error ... hasta entonces: ¡NO use std::unordered_map con gcc 4.7!

Estamos desarrollando un software crítico de alto rendimiento en C ++. Allí necesitamos un mapa hash simultáneo e implementado uno. Así que escribimos un punto de referencia para averiguar cuánto más lento es nuestro mapa hash concurrente en comparación con std::unordered_map .

Pero, std::unordered_map parece ser increíblemente lento ... Así que este es nuestro micro-benchmark (para el mapa simultáneo generamos un nuevo hilo para asegurarnos de que el bloqueo no se optimice y tenga en cuenta que nunca inserté 0 porque también punto de referencia con google::dense_hash_map , que necesita un valor nulo):

boost::random::mt19937 rng; boost::random::uniform_int_distribution<> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max()); std::vector<uint64_t> vec(SIZE); for (int i = 0; i < SIZE; ++i) { uint64_t val = 0; while (val == 0) { val = dist(rng); } vec[i] = val; } std::unordered_map<int, long double> map; auto begin = std::chrono::high_resolution_clock::now(); for (int i = 0; i < SIZE; ++i) { map[vec[i]] = 0.0; } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin); std::cout << "inserts: " << elapsed.count() << std::endl; std::random_shuffle(vec.begin(), vec.end()); begin = std::chrono::high_resolution_clock::now(); long double val; for (int i = 0; i < SIZE; ++i) { val = map[vec[i]]; } end = std::chrono::high_resolution_clock::now(); elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin); std::cout << "get: " << elapsed.count() << std::endl;

(EDITAR: el código fuente completo se puede encontrar aquí: http://pastebin.com/vPqf7eya )

El resultado para std::unordered_map es:

inserts: 35126 get : 2959

Para google::dense_map :

inserts: 3653 get : 816

Para nuestro mapa simultáneo respaldado a mano (que sí lo hace, aunque el índice de referencia es de un solo subproceso, pero en un subproceso separado):

inserts: 5213 get : 2594

Si compilo el programa de referencia sin soporte pthread y ejecuto todo en el hilo principal, obtengo los siguientes resultados para nuestro mapa simultáneo respaldado a mano:

inserts: 4441 get : 1180

Compilo con el siguiente comando:

g++-4.7 -O3 -DNDEBUG -I/tmp/benchmap/sparsehash-2.0.2/src/ -std=c++11 -pthread main.cc

Así que especialmente las inserciones en std::unordered_map parecen ser extremadamente caras: 35 segundos frente a 3-5 segundos para otros mapas. También el tiempo de búsqueda parece ser bastante alto.

Mi pregunta: ¿por qué es esto? Leí otra pregunta sobre stackoverflow donde alguien pregunta por qué std::tr1::unordered_map es más lento que su propia implementación. Allí, la respuesta mejor calificada establece que std::tr1::unordered_map necesita implementar una interfaz más complicada. Pero no puedo ver este argumento: usamos un enfoque de cubo en nuestro google::dense_hash_map concurrente, std::unordered_map usa un enfoque de cubo ( google::dense_hash_map no, pero std::unordered_map debe ser al menos tan rápido como nuestra mano ¿versión respaldada compatible con concurrencia?). Aparte de eso, no puedo ver nada en la interfaz que fuerce una característica que hace que el mapa hash funcione mal ...

Entonces mi pregunta: ¿es cierto que std::unordered_map parece ser muy lento? Si no, ¿qué está mal? En caso afirmativo, ¿cuál es el motivo de eso?

Y mi pregunta principal: ¿por qué es tan costoso insertar un valor en std::unordered_map (Incluso si reservamos suficiente espacio al principio, no funciona mucho mejor, entonces el problema no parece ser el reinicio).

EDITAR:

Primero que nada: sí, el benchmark presentado no es perfecto, esto es porque jugamos mucho con él y es solo un truco (por ejemplo, la distribución de uint64 para generar ints en la práctica no sería una buena idea, excluir 0 en una loop es algo estúpido, etc. ...).

Por el momento, la mayoría de los comentarios explican que puedo hacer que el mapa no ordenado sea más rápido al asignarle espacio suficiente. En nuestra aplicación esto simplemente no es posible: estamos desarrollando un sistema de administración de bases de datos y necesitamos un mapa hash para almacenar algunos datos durante una transacción (por ejemplo, información de bloqueo). Así que este mapa puede ser todo desde 1 (el usuario solo hace una inserción y confirmaciones) hasta miles de millones de entradas (si se realizan escaneos completos de tablas). Es simplemente imposible preasignar suficiente espacio aquí (y solo asignar un montón al principio consumirá demasiada memoria).

Además, me disculpo por no haber aclarado lo suficiente mi pregunta: no estoy realmente interesado en hacer un mapa desordenado rápido (el uso del mapa hash denso de Google funciona bien para nosotros), realmente no entiendo de dónde vienen estas enormes diferencias de rendimiento. . No puede ser solo una asignación previa (incluso con suficiente memoria preasignada, el mapa denso es un orden de magnitud más rápido que unordered_map, nuestro mapa simultáneo respaldado a mano comienza con una matriz de tamaño 64, por lo tanto, una más pequeña que unordered_map).

Entonces, ¿cuál es el motivo de este mal rendimiento de std::unordered_map ? O preguntado de manera diferente: ¿Podría uno escribir una implementación de la interfaz std::unordered_map que sea estándar y (casi) tan rápido como Google hash map denso? ¿O hay algo en el estándar que obligue al implementador a elegir una forma ineficiente de implementarlo?

EDICION 2:

Al hacer un perfil, veo que se usa mucho tiempo para las divisiones enteras. std::unordered_map usa números primos para el tamaño de la matriz, mientras que las otras implementaciones usan potencias de dos. ¿Por qué std::unordered_map usa números primos? Para funcionar mejor si el hash es malo? Para los buenos hashes, no importa.

EDIT 3:

Estos son los números para std::map :

inserts: 16462 get : 16978

Sooooooo: ¿por qué las inserciones en un std::map más rápidas que las inserciones en un std::unordered_map ... me refiero a WAT? std::map tiene una localidad peor (tree vs array), necesita hacer más asignaciones (por inserción vs por rehash + más ~ 1 por cada colisión) y, lo más importante: tiene otra complejidad algorítmica (O (logn) vs O ( 1))!

He ejecutado su código usando una computadora de 64 bits / AMD / 4 núcleos (2.1 GHz) y me dio los siguientes resultados:

MinGW-W64 4.9.2:

Usando std :: unordered_map:

inserts: 9280 get: 3302

Usando std :: map:

inserts: 23946 get: 24824

VC 2015 con todas las banderas de optimización que conozco:

Usando std :: unordered_map:

inserts: 7289 get: 1908

Usando std :: map:

inserts: 19222 get: 19711

No he probado el código usando GCC, pero creo que puede ser comparable al rendimiento de VC, por lo que si eso es cierto, entonces GCC 4.9 std :: unordered_map aún está roto.

[EDITAR]

Así que sí, como alguien dijo en los comentarios, no hay ninguna razón para pensar que el rendimiento de GCC 4.9.x sea comparable al rendimiento de VC. Cuando tenga el cambio, probaré el código en GCC.

Mi respuesta es solo establecer algún tipo de base de conocimiento para otras respuestas.

Supongo que no ha dimensionado correctamente su mapa unordered_map , como sugirió Ylisar. Cuando las cadenas crecen demasiado tiempo en unordered_map , la implementación de g ++ volverá automáticamente a convertirse en una tabla hash más grande, y esto supondría un gran lastre para el rendimiento. Si recuerdo correctamente, unordered_map predeterminado a (primo más pequeño mayor que) 100 .

No tenía chrono en mi sistema, así que sincronicé con los times() .

template <typename TEST> void time_test (TEST t, const char *m) { struct tms start; struct tms finish; long ticks_per_second; times(&start); t(); times(&finish); ticks_per_second = sysconf(_SC_CLK_TCK); std::cout << "elapsed: " << ((finish.tms_utime - start.tms_utime + finish.tms_stime - start.tms_stime) / (1.0 * ticks_per_second)) << " " << m << std::endl; }

SIZE un SIZE de 10000000 , y tuve que cambiar un poco las cosas para mi versión de boost . También tenga en cuenta que pretitubeé la tabla hash para que coincida con SIZE/DEPTH , donde DEPTH es una estimación de la longitud de la cadena del cucharón debido a las colisiones hash.

Editar: Howard me señala en comentarios que el factor de carga máximo para unordered_map es 1 . Por lo tanto, el DEPTH controla cuántas veces se volverá a generar el código.

#define SIZE 10000000 #define DEPTH 3 std::vector<uint64_t> vec(SIZE); boost::mt19937 rng; boost::uniform_int<uint64_t> dist(std::numeric_limits<uint64_t>::min(), std::numeric_limits<uint64_t>::max()); std::unordered_map<int, long double> map(SIZE/DEPTH); void test_insert () { for (int i = 0; i < SIZE; ++i) { map[vec[i]] = 0.0; } } void test_get () { long double val; for (int i = 0; i < SIZE; ++i) { val = map[vec[i]]; } } int main () { for (int i = 0; i < SIZE; ++i) { uint64_t val = 0; while (val == 0) { val = dist(rng); } vec[i] = val; } time_test(test_insert, "inserts"); std::random_shuffle(vec.begin(), vec.end()); time_test(test_insert, "get"); }

Editar:

Modifiqué el código para poder cambiar la DEPTH más fácilmente.

#ifndef DEPTH #define DEPTH 10000000 #endif

Por lo tanto, de forma predeterminada, se elige el peor tamaño para la tabla hash.

elapsed: 7.12 inserts, elapsed: 2.32 get, -DDEPTH=10000000 elapsed: 6.99 inserts, elapsed: 2.58 get, -DDEPTH=1000000 elapsed: 8.94 inserts, elapsed: 2.18 get, -DDEPTH=100000 elapsed: 5.23 inserts, elapsed: 2.41 get, -DDEPTH=10000 elapsed: 5.35 inserts, elapsed: 2.55 get, -DDEPTH=1000 elapsed: 6.29 inserts, elapsed: 2.05 get, -DDEPTH=100 elapsed: 6.76 inserts, elapsed: 2.03 get, -DDEPTH=10 elapsed: 2.86 inserts, elapsed: 2.29 get, -DDEPTH=1

Mi conclusión es que no hay mucha diferencia significativa en el rendimiento para cualquier tamaño de tabla hash inicial que no sea igual a la cantidad total esperada de inserciones únicas. Además, no veo la diferencia de rendimiento de orden de magnitud que estás observando.