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))!

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!

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.

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.