Estamos desenvolvendo um software crítico de alto desempenho em C ++. Precisamos de um mapa hash concorrente e um implementado. Então, nós escrevemos um benchmark para descobrir, quanto mais lento nosso mapa hash simultâneo é comparado std::unordered_map.

Mas, std::unordered_mapparece ser incrivelmente lento ... Portanto, este é o nosso micro-benchmark (para o mapa simultâneo, geramos um novo thread para garantir que o bloqueio não seja otimizado e observe que eu nunca insiro 0 porque também faço o benchmark com google::dense_hash_map, que precisa de um 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: o código-fonte completo pode ser encontrado aqui: http://pastebin.com/vPqf7eya )

O resultado para std::unordered_mapé:

inserts: 35126
get    : 2959

Para google::dense_map:

inserts: 3653
get    : 816

Para o nosso mapa simultâneo apoiado manualmente (que bloqueia, embora o benchmark seja de thread único - mas em um thread de spawn separado):

inserts: 5213
get    : 2594

Se eu compilar o programa de benchmark sem suporte pthread e executar tudo no thread principal, obtenho os seguintes resultados para nosso mapa simultâneo apoiado manualmente:

inserts: 4441
get    : 1180

Eu compilo com o seguinte comando:

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

Então, especialmente as inserções std::unordered_mapparecem ser extremamente caras - 35 segundos contra 3-5 segundos para outros mapas. Além disso, o tempo de consulta parece ser bastante alto.

Minha pergunta: por que isso? Eu li outra pergunta sobre stackoverflow onde alguém pergunta, por que std::tr1::unordered_mapé mais lento do que sua própria implementação. Lá, a resposta com classificação mais alta afirma que é std::tr1::unordered_mapnecessário implementar uma interface mais complicada. Mas não consigo ver este argumento: usamos uma abordagem de balde em nosso concurrent_map, também std::unordered_mapusa uma abordagem de balde ( google::dense_hash_mapnão, mas std::unordered_mapdeveria ser pelo menos tão rápido quanto nossa versão segura para simultaneidade com suporte manual?). Tirando isso, não consigo ver nada na interface que force um recurso que faz o hash map funcionar mal ...

Então minha pergunta: é verdade que std::unordered_mapparece muito lento? Se não: o que há de errado? Se sim: qual a razão disso.

E minha principal pergunta: por que inserir um valor em um std::unordered_maptão caro é tão caro (mesmo se reservarmos espaço suficiente no início, ele não funciona muito melhor - então refazer parece não ser o problema)?

EDITAR:

Primeiro de tudo: sim, o benchmark apresentado não é perfeito - isso é porque nós brincamos muito com ele e é apenas um hack (por exemplo, a uint64distribuição para gerar ints na prática não seria uma boa ideia, excluir 0 em um loop é meio estúpido, etc ...).

No momento, a maioria dos comentários explica que posso tornar o unordered_map mais rápido ao pré-alocar espaço suficiente para ele. Em nossa aplicação, isso simplesmente não é possível: estamos desenvolvendo um sistema de gerenciamento de banco de dados e precisamos de um mapa hash para armazenar alguns dados durante uma transação (por exemplo, informações de bloqueio). Portanto, este mapa pode ser tudo de 1 (o usuário apenas faz uma inserção e confirma) a bilhões de entradas (se ocorrerem varreduras completas da tabela). É simplesmente impossível pré-alocar espaço suficiente aqui (e apenas alocar muito no início consumirá muita memória).

Além disso, peço desculpas por não ter formulado minha pergunta com clareza suficiente: não estou realmente interessado em tornar o unordered_map rápido (usar o mapa hash denso do Google funciona bem para nós), simplesmente não entendo de onde vêm essas enormes diferenças de desempenho . Não pode ser apenas pré-alocação (mesmo com memória pré-alocada suficiente, o mapa denso é uma ordem de magnitude mais rápido do que unordered_map, nosso mapa simultâneo apoiado manualmente começa com uma matriz de tamanho 64 - portanto, menor que unordered_map).

Então, qual é a razão para esse mau desempenho de std::unordered_map? Ou de outra forma: std::unordered_mapseria possível escrever uma implementação da interface em conformidade com o padrão e (quase) tão rápida quanto o denso mapa hash do Google? Ou há algo no padrão que força o implementador a escolher uma forma ineficiente de implementá-lo?

EDIT 2:

Ao fazer o perfil, vejo que muito tempo é usado para divisões inteiras. std::unordered_mapusa números primos para o tamanho do array, enquanto as outras implementações usam potências de dois. Por que std::unordered_mapusa números primos? Para ter um melhor desempenho se o hash estiver ruim? Para bons hashes, isso não faz diferença.

EDITAR 3:

Estes são os números de std::map:

inserts: 16462
get    : 16978

Sooooooo: por que as inserções em um são std::mapmais rápidas do que as inserções em um std::unordered_map... quero dizer WAT? std::maptem uma localidade pior (árvore vs array), precisa fazer mais alocações (por inserção vs por rehash + mais ~ 1 para cada colisão) e, o mais importante: tem outra complexidade algorítmica (O (logn) vs O (1))!

Encontrei o motivo: é um problema do gcc-4.7 !!

Com gcc-4.7

inserts: 37728
get    : 2985

Com gcc-4.6

inserts: 2531
get    : 1565

Portanto std::unordered_map, o gcc-4.7 está quebrado (ou minha instalação, que é uma instalação do gcc-4.7.0 no Ubuntu - e outra instalação, que é o gcc 4.7.1 no teste debian).

Vou enviar um relatório de bug ... até então: NÃO use std::unordered_mapcom gcc 4.7!

Eu estou supondo que você não dimensionou adequadamente o seu unordered_map, como Ylisar sugeriu. Quando as cadeias ficam muito longas em unordered_map, a implementação do g ++ será automaticamente refeita para uma tabela de hash maior, e isso seria um grande obstáculo no desempenho. Se bem me lembro, o unordered_mappadrão é (menor número maior que) 100.

Eu não tenho chronono meu sistema, então eu cronometrado com 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;
}

Usei um SIZEde 10000000e tive que mudar um pouco as coisas para a minha versão de boost. Observe também que eu pré-dimensionei a tabela de hash para corresponder SIZE/DEPTH, onde DEPTHé uma estimativa do comprimento da cadeia de balde devido a colisões de hash.

Edit: Howard aponta para mim em comentários que o fator de carga máximo para unordered_mapé 1. Portanto, os DEPTHcontroles de quantas vezes o código será refeito.

#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:

Modifiquei o código para que pudesse mudar DEPTHmais facilmente.

#ifndef DEPTH
#define DEPTH 10000000
#endif

Portanto, por padrão, o pior tamanho para a tabela hash é escolhido.

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

Minha conclusão é que não há muita diferença significativa de desempenho para qualquer tamanho de tabela de hash inicial, exceto torná-lo igual ao número inteiro esperado de inserções exclusivas. Além disso, não vejo a ordem de magnitude da diferença de desempenho que você está observando.

Executei seu código usando um computador de 64 bits / AMD / 4 núcleos (2,1 GHz) e ele me deu os seguintes resultados:

MinGW-W64 4.9.2:

Usando std :: unordered_map:

inserts: 9280 
get: 3302

Usando std :: map:

inserts: 23946
get: 24824

VC 2015 com todos os sinalizadores de otimização que conheço:

Usando std :: unordered_map:

inserts: 7289
get: 1908

Usando std :: map:

inserts: 19222 
get: 19711

Eu não testei o código usando o GCC, mas acho que pode ser comparável ao desempenho do VC, então se isso for verdade, então o GCC 4.9 std :: unordered_map ainda está quebrado.

[EDITAR]

Então sim, como alguém disse nos comentários, não há razão para pensar que o desempenho do GCC 4.9.x seria comparável ao desempenho do VC. Quando eu tiver a mudança, testarei o código no GCC.

Minha resposta é apenas estabelecer algum tipo de base de conhecimento para outras respostas.