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

100

Estamos desarrollando un software crítico de alto rendimiento en C ++. Allí necesitamos un mapa hash concurrente y uno implementado. Así que escribimos un punto de referencia para averiguar con qué velocidad se compara nuestro mapa hash concurrente std::unordered_map.

Pero, std::unordered_mapparece ser increíblemente lento ... Así que este es nuestro micro-benchmark (para el mapa concurrente generamos un nuevo hilo para asegurarnos de que el bloqueo no se optimice y tenga en cuenta que nunca inser 0 porque también comparo 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 de std::unordered_mapes:

inserts: 35126
get    : 2959

Para google::dense_map:

inserts: 3653
get    : 816

Para nuestro mapa concurrente respaldado a mano (que se bloquea, aunque el punto de referencia es de un solo hilo, pero en un hilo de generación separado):

inserts: 5213
get    : 2594

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

inserts: 4441
get    : 1180

Yo 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 std::unordered_mapparecen ser extremadamente caras: 35 segundos frente a 3-5 segundos para otros mapas. Además, el tiempo de búsqueda parece ser bastante elevado.

Mi pregunta: ¿por qué es esto? Leí otra pregunta en stackoverflow donde alguien pregunta por qué std::tr1::unordered_mapes más lento que su propia implementación. Allí, la respuesta mejor calificada dice que es std::tr1::unordered_mapnecesario implementar una interfaz más complicada. Pero no puedo ver este argumento: usamos un enfoque de cubo en nuestro concurrent_map, también std::unordered_mapusa un enfoque de cubo ( google::dense_hash_mapno lo hace, pero std::unordered_mapdebería ser al menos tan rápido que nuestra versión segura de concurrencia respaldada a mano). 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_mapparece ser muy lento? Si no, ¿qué pasa? Si es así: ¿cuál es la razón?

Y mi pregunta principal: ¿por qué es std::unordered_maptan caro insertar un valor en un valor tan terrible (incluso si reservamos suficiente espacio al principio, no funciona mucho mejor, por lo que el refrito no parece ser el problema)?

EDITAR:

En primer lugar: sí, el punto de referencia presentado no es impecable, esto se debe a que jugamos mucho con él y es solo un truco (por ejemplo, la uint64distribución para generar ints en la práctica no sería una buena idea, excluir 0 en un bucle es algo estúpido, etc.).

Por el momento, la mayoría de los comentarios explican que puedo hacer que unordered_map sea más rápido asignando previamente suficiente espacio para él. 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). Por lo tanto, este mapa puede ser de todo, desde 1 (el usuario solo hace una inserción y confirma) hasta miles de millones de entradas (si se realizan escaneos completos de la tabla). Es simplemente imposible preasignar suficiente espacio aquí (y simplemente asignar mucho al principio consumirá demasiada memoria).

Además, me disculpo por no haber planteado mi pregunta lo suficientemente clara: no estoy realmente interesado en hacer un mapa ordenado rápido (usar mapas hash densos de Google funciona bien para nosotros), simplemente no entiendo de dónde vienen estas enormes diferencias de rendimiento . No puede ser solo una preasignación (incluso con suficiente memoria preasignada, el mapa denso es un orden de magnitud más rápido que unordered_map, nuestro mapa concurrente con respaldo manual comienza con una matriz de tamaño 64, por lo que una más pequeña que unordered_map).

Entonces, ¿cuál es la razón de este mal desempeño std::unordered_map? O preguntado de otra manera: ¿Se podría escribir una implementación de la std::unordered_mapinterfaz que sea estándar y (casi) tan rápida como el mapa de hash denso de Google? ¿O hay algo en el estándar que obliga al implementador a elegir una forma ineficiente de implementarlo?

EDITAR 2:

Al crear perfiles, veo que se usa mucho tiempo para divisiones enteras. std::unordered_mapusa números primos para el tamaño de la matriz, mientras que las otras implementaciones usan potencias de dos. ¿Por qué std::unordered_maputiliza números primos? ¿Funcionar mejor si el hash es malo? Para buenos hashes, en mi humilde opinión, no hace ninguna diferencia.

EDITAR 3:

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

inserts: 16462
get    : 16978

Sooooooo: ¿por qué se insertan en un std::mapmás rápido que se inserta en un std::unordered_map... quiero decir WAT? std::maptiene una localidad peor (árbol vs matriz), necesita hacer más asignaciones (por inserción vs por repetición + más ~ 1 por cada colisión) y, lo más importante: tiene otra complejidad algorítmica (O (logn) vs O (1))!

Markus Pilman
fuente
1
La mayoría de los contenedores en std son MUY conservadores con sus estimaciones, echaría un vistazo al recuento de cubos que está usando (especificado en el constructor) y lo aumentaría a una mejor estimación para su SIZE.
Ylisar
¿Ha probado concurrent_hash_map de Intel TBB? threadingbuildingblocks.org/docs/help/reference/…
MadScientist
1
@MadScientist Consideramos TBB. El problema es la concesión de licencias: es un proyecto de investigación y todavía no estamos seguros de cómo lo publicaremos (definitivamente de código abierto, pero si queremos permitir el uso en un producto comercial, GPLv2 es demasiado restrictivo). También es otra dependencia. Pero puede ser que lo usemos en un momento posterior, hasta ahora podemos vivir bien sin él.
Markus Pilman
1
Ejecutarlo bajo un generador de perfiles, por ejemplo, valgrind, puede ser revelador.
Maxim Egorushkin
1
La localidad en una tabla hash es, en el mejor de los casos, ligeramente mejor que la localidad en un árbol, al menos si la función hash es "aleatoria". Esa función hash garantiza que rara vez acceda a elementos cercanos en momentos cercanos. La única ventaja que tiene es que la matriz de tabla hash es un bloque contiguo. Eso puede ser cierto para un árbol de todos modos, si el montón no está fragmentado y construyes el árbol de una vez. Una vez que el tamaño es mayor que el caché, las diferencias en la localidad harán poca o ninguna diferencia en el rendimiento.
Steve 314

Respuestas:

87

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_mapen 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 las pruebas de Debian).

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

Markus Pilman
fuente
¿Hay algo en el delta de 4.6 que pueda causar eso?
Mark Canlas
30
Ya hay un informe en la lista de correo. La discusión parece apuntar a "arreglos" en el max_load_factormanejo, lo que llevó a la diferencia en el desempeño.
jxh
¡Mal momento para este error! Obtuve un rendimiento muy bajo con unordered_map, pero me alegro de que se haya informado y "arreglado".
Bo Lu
+1 - Qué mierda BBBBBUG .. Me pregunto qué pasa con gcc-4.8.2
ikh
2
¿Alguna actualización sobre este error? ¿Todavía existe para versiones posteriores de GCC (5+)?
rph
21

Supongo que no has dimensionado correctamente el tuyo unordered_map, como sugirió Ylisar. Cuando las cadenas crecen demasiado unordered_map, la implementación de g ++ automáticamente se volverá a convertir en una tabla hash más grande, y esto sería un gran obstáculo para el rendimiento. Si no recuerdo mal, el valor unordered_mappredeterminado es (menor primo mayor que) 100.

No tenía chronoen mi sistema, así que cronometré 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;
}

Usé un SIZEde 10000000y tuve que cambiar un poco las cosas para mi versión de boost. También tenga en cuenta que pre-dimensioné la tabla hash para que coincida SIZE/DEPTH, donde DEPTHes una estimación de la longitud de la cadena de cubos debido a colisiones hash.

Editar: Howard me señala en los comentarios que el factor de carga máximo para unordered_mapes 1. Entonces, DEPTHcontrola cuántas veces se repetirá 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 cambiarlo DEPTHmás fácilmente.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Entonces, 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 de rendimiento significativa para cualquier tamaño de tabla hash inicial que no sea igual al número total esperado de inserciones únicas. Además, no veo el orden de magnitud de la diferencia de rendimiento que está observando.

jxh
fuente
6
std::unordered_maptiene un factor de carga máximo predeterminado de 1. Por lo tanto, excepto por el número inicial de cubos, se ignora su PROFUNDIDAD. Si lo desea, puede hacerlo map.max_load_factor(DEPTH).
Howard Hinnant
@HowardHinnant: Gracias por esa información. Por lo tanto, DEPTHse ignora, pero aún controla la frecuencia con la que el mapa se volverá a convertir en un mapa más grande. La respuesta ha sido actualizada y gracias de nuevo
jxh
@ user315052 Sí, sé que puedo mejorarlo dándole un tamaño sensato al principio, pero no puedo hacer eso en nuestro software (es un proyecto de investigación, un DBMS, y allí no puedo saber cuánto insertaré) puede variar entre 0 y mil millones ...). Pero incluso con la reproducción previa es más lento que nuestro mapa y mucho más lento que el dense_map de Google. Todavía me pregunto qué es lo que marca la gran diferencia.
Markus Pilman
@MarkusPilman: No sé cómo se comparan mis resultados con los suyos, porque nunca proporcionó el tamaño con el SIZEque estaba trabajando. Puedo decir que unordered_mapes dos veces más rápido si está DEPTHconfigurado 1y preasignado correctamente.
jxh
1
@MarkusPilman: Mis tiempos ya están en segundos. Pensé que tus tiempos estaban en milisegundos. Si las inserciones con DEPTHestablecido en 1toman menos de 3segundos, ¿cómo es esto un orden de magnitud más lento?
jxh
3

He ejecutado su código usando una computadora de 64 bits / AMD / 4 núcleos (2.1GHz) 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 todavía está roto.

[EDITAR]

Entonces, sí, como alguien dijo en los comentarios, no hay 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 simplemente establecer algún tipo de base de conocimientos para otras respuestas.

Christian Leon
fuente
"No he probado el código con GCC, pero creo que puede ser comparable al rendimiento de VC". Reclamación totalmente infundada, sin ningún benchmarking comparable al encontrado en el post original. Esta "respuesta" no responde a la pregunta en ningún sentido, y mucho menos responde a la pregunta "por qué".
4ae1e1
2
"No he probado el código usando GCC" ... ¿cómo es que lograste adquirir y usar MinGW sabiendo tan poco sobre él? MinGW es fundamentalmente un puerto de seguimiento de cerca de GCC.
underscore_d