boost :: flat_map y su rendimiento en comparación con map y unordered_map

Es de conocimiento común en programación que la ubicación de la memoria mejora mucho el rendimiento debido a los aciertos de caché. Recientemente descubrí boost::flat_mapcuál es una implementación basada en vectores de un mapa. No parece ser tan popular como el típico, mappor unordered_maplo que no he podido encontrar ninguna comparación de rendimiento. ¿Cómo se compara y cuáles son los mejores casos de uso para él?

¡Gracias!

Recientemente he ejecutado un punto de referencia en diferentes estructuras de datos en mi empresa, así que siento que necesito decir algo. Es muy complicado comparar algo correctamente.

Benchmarking

En la web rara vez encontramos (si acaso alguna vez) un punto de referencia bien diseñado. Hasta el día de hoy, solo encontré puntos de referencia que se hicieron a la manera de los periodistas (bastante rápido y barriendo docenas de variables debajo de la alfombra).

1) Debe tener en cuenta el calentamiento de la caché

La mayoría de las personas que ejecutan puntos de referencia temen la discrepancia del temporizador, por lo tanto, ejecutan sus cosas miles de veces y se toman todo el tiempo, solo tienen cuidado de tomar las mismas miles de veces para cada operación y luego consideran que es comparable.

La verdad es que, en el mundo real, tiene poco sentido, porque su caché no estará caliente y su operación probablemente se llamará solo una vez. Por lo tanto, necesita comparar usando RDTSC y cronometrar las cosas llamándolos una sola vez. Intel ha elaborado un documento que describe cómo usar RDTSC (usando una instrucción cpuid para limpiar la tubería y llamándola al menos 3 veces al comienzo del programa para estabilizarla).

2) medida de precisión RDTSC

También recomiendo hacer esto:

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 es un medidor de discrepancias, y tomará el mínimo de todos los valores medidos, para evitar obtener un -10 ** 18 (primeros valores negativos de 64 bits) de vez en cuando.

Observe el uso de intrínsecos y no ensamblaje en línea. El primer ensamblaje en línea rara vez es compatible con los compiladores de hoy en día, pero lo peor de todo es que el compilador crea una barrera de ordenación completa alrededor del ensamblaje en línea porque no puede analizar estáticamente el interior, por lo que este es un problema para comparar cosas del mundo real, especialmente cuando se llaman cosas simplemente una vez. Entonces, un intrínseco es adecuado aquí, porque no interrumpe el reordenamiento libre de instrucciones del compilador.

3) parámetros

El último problema es que la gente suele probar muy pocas variaciones del escenario. El rendimiento de un contenedor se ve afectado por:

1. Asignador
2. tamaño del tipo contenido
3. costo de implementación de la operación de copia, operación de asignación, operación de movimiento, operación de construcción, del tipo contenido.
4. número de elementos en el contenedor (tamaño del problema)
5. tipo tiene operaciones triviales
6. el tipo es POD

El punto 1 es importante porque los contenedores se asignan de vez en cuando, y es muy importante si asignan utilizando el CRT "nuevo" o alguna operación definida por el usuario, como la asignación de grupos o la lista gratuita u otra ...

( para las personas interesadas en el punto 1, únase al hilo misterioso en gamedev sobre el impacto en el rendimiento del asignador del sistema )

El punto 2 se debe a que algunos contenedores (por ejemplo, A) perderán tiempo copiando cosas, y cuanto más grande sea el tipo, mayor será la sobrecarga. El problema es que cuando se compara con otro contenedor B, A puede ganarle a B para tipos pequeños y perder para tipos más grandes.

El punto 3 es el mismo que el punto 2, excepto que multiplica el costo por algún factor de ponderación.

El punto 4 es una cuestión de gran O mezclada con problemas de caché. Algunos contenedores de mala complejidad pueden superar en gran medida a los contenedores de baja complejidad para una pequeña cantidad de tipos (como mapvs. vector, porque su localidad de caché es buena, pero mapfragmenta la memoria). Y luego, en algún punto de cruce, perderán, porque el tamaño total contenido comienza a "filtrarse" a la memoria principal y provocar errores de caché, además del hecho de que la complejidad asintótica puede comenzar a sentirse.

El punto 5 trata de que los compiladores puedan eludir cosas vacías o triviales en el momento de la compilación. Esto puede optimizar en gran medida algunas operaciones, ya que los contenedores tienen plantilla, por lo que cada tipo tendrá su propio perfil de rendimiento.

El punto 6 al igual que el punto 5, los POD pueden beneficiarse del hecho de que la construcción de copias es solo una memoria, y algunos contenedores pueden tener una implementación específica para estos casos, utilizando especializaciones de plantilla parciales, o SFINAE para seleccionar algoritmos de acuerdo con los rasgos de T.

Sobre el mapa plano

Aparentemente, el mapa plano es un contenedor vectorial ordenado, como Loki AssocVector, pero con algunas modernizaciones complementarias que vienen con C ++ 11, explotando la semántica de movimiento para acelerar la inserción y eliminación de elementos individuales.

Este sigue siendo un contenedor ordenado. La mayoría de las personas generalmente no necesitan la parte de pedido, por lo tanto, la existencia de unordered...

¿Has considerado que quizás necesites un flat_unorderedmap? que sería algo así google::sparse_mapo algo así: un mapa hash de direcciones abierto.

El problema de los mapas hash de direcciones abiertos es que en el momento de rehashtener que copiar todo en la nueva zona plana extendida, mientras que un mapa desordenado estándar solo tiene que volver a crear el índice hash, mientras que los datos asignados permanecen donde están. La desventaja, por supuesto, es que la memoria está muy fragmentada.

El criterio de un refrito en un mapa hash de direcciones abiertas es cuando la capacidad excede el tamaño del vector de cubeta multiplicado por el factor de carga.

Un factor de carga típico es 0.8; por lo tanto, debe preocuparse por eso, si puede pre-dimensionar su mapa hash antes de llenarlo, siempre pre-dimensione a: intended_filling * (1/0.8) + epsilonesto le dará la garantía de no tener que volver a copiar y volver a copiar todo de manera falsa durante el llenado.

La ventaja de los mapas de direcciones cerrados ( std::unordered..) es que no tiene que preocuparse por esos parámetros.

Pero boost::flat_mapes un vector ordenado; por lo tanto, siempre tendrá una complejidad log (N) asintótica, que es menos buena que el mapa hash de direcciones abiertas (tiempo constante amortizado). Deberías considerar eso también.

Resultados comparativos

Esta es una prueba que involucra diferentes mapas (con intclave y __int64/ somestructcomo valor) y std::vector.

información de tipos probados:

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

Inserción

EDITAR:

Mis resultados anteriores incluyeron un error: en realidad probaron la inserción ordenada, que mostró un comportamiento muy rápido para los mapas planos.
Dejé esos resultados más adelante en esta página porque son interesantes.
Esta es la prueba correcta:

He comprobado la implementación, no existe tal cosa como una clasificación diferida implementada en los mapas planos aquí. Cada inserción se ordena sobre la marcha, por lo tanto, este punto de referencia exhibe las tendencias asintóticas:

mapa: O (N * log (N))
hashmaps: O (N)
vector y mapas planos: O (N * N)

Advertencia : de ahora en adelante, las 2 pruebas para std::mapy ambos flat_maps tienen errores y en realidad prueban la inserción ordenada (frente a la inserción aleatoria para otros contenedores. Sí, es confuso, lo siento):

Podemos ver que la inserción ordenada resulta en retroceso y es extremadamente rápida. Sin embargo, a partir de los resultados no graficados de mi punto de referencia, también puedo decir que esto no está cerca de la optimización absoluta para una inserción posterior. En 10k elementos, se obtiene una optimización de inserción posterior perfecta en un vector reservado previamente. Lo que nos da 3 millones de ciclos; observamos 4.8M aquí para la inserción ordenada en el flat_map(por lo tanto, 160% del óptimo).

Análisis: recuerde que esto es una 'inserción aleatoria' para el vector, por lo que los mil millones de ciclos masivos provienen de tener que cambiar la mitad (en promedio) de los datos hacia arriba (un elemento por un elemento) en cada inserción.

Búsqueda aleatoria de 3 elementos (relojes renormalizados a 1)

en tamaño = 100

en tamaño = 10000

Iteración

sobre el tamaño 100 (solo tipo MediumPod)

sobre el tamaño 10000 (solo tipo MediumPod)

Grano de sal final

Al final, quería volver a "Benchmarking §3 Pt1" (el asignador del sistema). En un experimento reciente que estoy haciendo sobre el rendimiento de un mapa hash de direcciones abiertas que desarrollé , medí una brecha de rendimiento de más del 3000% entre Windows 7 y Windows 8 en algunos std::unordered_mapcasos de uso ( discutidos aquí ).
Lo que me hace querer advertir al lector sobre los resultados anteriores (se hicieron en Win7): su kilometraje puede variar.

atentamente

Según los documentos, parece que esto es análogo a Loki::AssocVectorlo que soy un usuario bastante pesado. Al estar basado en un vector tiene las características de un vector, es decir:

• Los iteradores se invalidan cada vez que sizecrece más allá capacity.
• Cuando crece más allá capacity, necesita reasignar y mover objetos, es decir, no se garantiza un tiempo constante de inserción, excepto en el caso especial de insertar en endcuandocapacity > size
• La búsqueda es más rápida que std::mapdebido a la localidad de la caché, una búsqueda binaria que tiene las mismas características de rendimiento que de std::mapotra manera
• Utiliza menos memoria porque no es un árbol binario vinculado
• Nunca se encoge a menos que se lo indique a la fuerza (ya que eso desencadena la reasignación)

El mejor uso es cuando conoce la cantidad de elementos de antemano (para que pueda hacerlo por reserveadelantado), o cuando la inserción / eliminación es rara pero la búsqueda es frecuente. La invalidación del iterador lo hace un poco engorroso en algunos casos de uso, por lo que no son intercambiables en términos de corrección del programa.