boost :: flat_map e seu desempenho em comparação com map e unordered_map

É de conhecimento comum em programação que a localidade da memória melhora muito o desempenho devido aos acessos do cache. Recentemente, descobri boost::flat_mapqual é a implementação de um mapa baseada em vetor. Não parece ser tão popular quanto o seu típico map/ unordered_mapentão não consegui encontrar nenhuma comparação de desempenho. Como ele se compara e quais são os melhores casos de uso para ele?

Obrigado!

Eu executei um benchmark em diferentes estruturas de dados muito recentemente em minha empresa, então sinto que preciso dizer uma palavra. É muito complicado avaliar algo corretamente.

avaliação comparativa

Na web, raramente encontramos (ou nunca) um benchmark bem projetado. Até hoje só encontrei benchmarks que foram feitos do jeito jornalístico (bem rápido e varrendo dezenas de variáveis ​​para debaixo do tapete).

1) Você precisa considerar o aquecimento do cache

A maioria das pessoas que executam benchmarks tem medo de discrepância de cronômetro, portanto, executam suas coisas milhares de vezes e levam o tempo todo, apenas tomam o cuidado de fazer as mesmas milhares de vezes para cada operação, e então consideram isso comparável.

A verdade é que, no mundo real, isso faz pouco sentido, porque seu cache não estará quente e sua operação provavelmente será chamada apenas uma vez. Portanto, você precisa fazer o benchmark usando RDTSC e cronometrar as chamadas apenas uma vez. A Intel fez um artigo descrevendo como usar RDTSC (usando uma instrução cpuid para liberar o pipeline e chamando-o pelo menos 3 vezes no início do programa para estabilizá-lo).

2) Medida de precisão RDTSC

Eu também recomendo fazer isso:

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

Este é um medidor de discrepância e levará o mínimo de todos os valores medidos para evitar obter -10 ** 18 (primeiros valores negativos de 64 bits) de tempos em tempos.

Observe o uso de intrínsecos e não de montagem embutida. O primeiro assembly embutido raramente é suportado por compiladores hoje em dia, mas muito pior de tudo, o compilador cria uma barreira de ordenação completa em torno do assembly embutido porque ele não pode analisar estática no interior, então este é um problema para comparar coisas do mundo real, especialmente ao chamar coisas apenas uma vez. Portanto, um intrínseco é adequado aqui, porque não interrompe a reordenação livre de instruções do compilador.

3) parâmetros

O último problema é que as pessoas geralmente testam poucas variações do cenário. O desempenho de um contêiner é afetado por:

1. Allocator
2. tamanho do tipo contido
3. custo de implementação da operação de cópia, operação de atribuição, operação de movimentação, operação de construção, do tipo contido.
4. número de elementos no contêiner (tamanho do problema)
5. tipo tem operações 3. triviais
6. tipo é POD

O ponto 1 é importante porque os contêineres se alocam de vez em quando, e é muito importante se eles alocam usando o CRT "novo" ou alguma operação definida pelo usuário, como alocação de pool ou freelist ou outro ...

( para pessoas interessadas no ponto 1, junte-se ao tópico misterioso no gamedev sobre o impacto no desempenho do alocador do sistema )

O ponto 2 é porque alguns contêineres (digamos A) perderão tempo copiando coisas ao redor, e quanto maior o tipo, maior o overhead. O problema é que, ao comparar com outro contêiner B, A pode vencer B para tipos pequenos e perder para tipos maiores.

O ponto 3 é igual ao ponto 2, exceto que multiplica o custo por algum fator de ponderação.

O ponto 4 é uma questão de grande O misturado com problemas de cache. Alguns contêineres de complexidade ruim podem superar amplamente os contêineres de baixa complexidade para um pequeno número de tipos (como mapvs. vector, porque sua localização de cache é boa, masmap fragmenta a memória). E então, em algum ponto de cruzamento, eles perderão, porque o tamanho total contido começa a "vazar" para a memória principal e causar perdas de cache, além do fato de que a complexidade assintótica pode começar a ser sentida.

O ponto 5 é sobre os compiladores serem capazes de eliminar coisas que estão vazias ou triviais em tempo de compilação. Isso pode otimizar bastante algumas operações, pois os contêineres são modelados, portanto cada tipo terá seu próprio perfil de desempenho.

Ponto 6 igual ao ponto 5, os PODs podem se beneficiar do fato de que a construção da cópia é apenas um memcpy, e alguns contêineres podem ter uma implementação específica para esses casos, usando especializações de template parciais, ou SFINAE para selecionar algoritmos de acordo com características de T.

Sobre o mapa plano

Aparentemente, o mapa plano é um empacotador de vetor classificado, como Loki AssocVector, mas com algumas modernizações suplementares que vêm com o C ++ 11, explorando a semântica de movimento para acelerar a inserção e exclusão de elementos únicos.

Este ainda é um contêiner encomendado. A maioria das pessoas geralmente não precisa da peça de pedido, portanto, a existência de unordered...

Você já pensou que talvez precise de um flat_unorderedmap? que seria algo parecido google::sparse_mapou algo parecido - um mapa hash de endereço aberto.

O problema dos mapas hash de endereço aberto é que, no momento em que rehasheles têm que copiar tudo ao redor para o novo terreno plano estendido, um mapa não ordenado padrão apenas tem que recriar o índice hash, enquanto os dados alocados permanecem onde estão. A desvantagem, claro, é que a memória está fragmentada como o inferno.

O critério de um novo hash em um mapa de hash de endereço aberto é quando a capacidade excede o tamanho do vetor de balde multiplicado pelo fator de carga.

Um fator de carga típico é 0.8; portanto, você precisa se preocupar com isso, se você pode pré-dimensionar seu hash map antes de preenchê-lo, sempre pré-dimensionar para: intended_filling * (1/0.8) + epsilonisso lhe dará a garantia de nunca ter que refazer espúrio e recopiar tudo durante o preenchimento.

A vantagem dos mapas de endereços fechados ( std::unordered..) é que você não precisa se preocupar com esses parâmetros.

Mas o boost::flat_mapé um vetor ordenado; portanto, ele sempre terá uma complexidade assintótica log (N), que é menos boa do que o hash map de endereço aberto (tempo constante amortizado). Você deve considerar isso também.

Resultados de referência

Este é um teste envolvendo diferentes mapas (com intchave e __int64/ somestructcomo valor) e std::vector.

informações de tipos testados:

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

Inserção

EDITAR:

Meus resultados anteriores incluíram um bug: eles realmente testaram a inserção ordenada, que exibiu um comportamento muito rápido para os mapas planos.
Deixei esses resultados mais tarde nesta página porque são interessantes.
Este é o teste correto:

Eu verifiquei a implementação, não existe uma classificação adiada implementada nos mapas planos aqui. Cada inserção é classificada em tempo real, portanto, este benchmark exibe as tendências assintóticas:

map: O (N * log (N))
hashmaps: O (N)
vetor e flatmaps: O (N * N)

Aviso : daqui em diante, os 2 testes para std::mape ambos flat_mapsão com erros e, na verdade, testam a inserção solicitada (versus a inserção aleatória para outros contêineres. Sim, é confuso, desculpe):

Podemos ver que a inserção ordenada resulta em empurrar para trás e é extremamente rápida. No entanto, a partir de resultados não mapeados de meu benchmark, também posso dizer que isso não está perto da otimização absoluta para uma inserção de volta. Em 10k elementos, a otimização de inserção traseira perfeita é obtida em um vetor pré-reservado. O que nos dá 3 milhões de ciclos; observamos 4,8M aqui para a inserção ordenada no flat_map(portanto, 160% do ótimo).

Análise: lembre-se de que esta é uma 'inserção aleatória' para o vetor, então o massivo 1 bilhão de ciclos vem de ter que deslocar metade (em média) os dados para cima (um elemento por elemento) em cada inserção.

Pesquisa aleatória de 3 elementos (relógios renormalizados para 1)

em tamanho = 100

em tamanho = 10000

Iteração

acima do tamanho 100 (apenas tipo MediumPod)

acima do tamanho 10000 (apenas tipo MediumPod)

Grão final de sal

No final, eu queria voltar ao "Benchmarking §3 Pt1" (o alocador do sistema). Em um experimento recente que estou fazendo em torno do desempenho de um mapa hash de endereço aberto que desenvolvi , medi uma lacuna de desempenho de mais de 3.000% entre o Windows 7 e o Windows 8 em alguns std::unordered_mapcasos de uso ( discutidos aqui ).
O que me faz querer alertar o leitor sobre os resultados acima (foram feitos no Win7): sua milhagem pode variar.

Cumprimentos

Pelos documentos, parece que é análogo ao Loki::AssocVectorqual eu sou um usuário bastante pesado. Por se basear em um vetor, possui características de vetor, ou seja:

• Os iteradores são invalidados sempre que sizecrescem além capacity.
• Quando ele cresce, capacityele precisa realocar e mover objetos, ou seja, a inserção não é garantida em tempo constante, exceto para o caso especial de inserir em endquandocapacity > size
• A pesquisa é mais rápida do que std::mapdevido à localidade do cache, uma pesquisa binária que tem as mesmas características de desempenho de std::mapoutra forma
• Usa menos memória porque não é uma árvore binária vinculada
• Nunca encolhe, a menos que você o diga à força (uma vez que aciona a realocação)

O melhor uso é quando você sabe o número de elementos com antecedência (para que você possa reserveantecipar) ou quando a inserção / remoção é rara, mas a pesquisa é frequente. A invalidação do iterador torna-o um pouco complicado em alguns casos de uso, portanto, eles não são intercambiáveis ​​em termos de correção do programa.