c++ - sistemas - primer ajuste mejor ajuste peor ajuste
Un mapa y un conjunto que usa memoria contigua y tiene una función de reserva (5)
Boost.Interprocess y Boost.Container proporcionan un conjunto plano y plano que podría ayudarlo a mejorar el rendimiento de su aplicación.
Yo uso varios mapas y conjuntos. La falta de memoria contigua y el alto número de (des) asignaciones es un cuello de botella de rendimiento. Necesito un mapa compatible principalmente con STL y una clase configurada que puede usar un bloque contiguo de memoria para objetos internos (o múltiples bloques). También necesita tener una función de reserve para poder preasignar los tamaños esperados.
Antes de escribir el mío, me gustaría verificar primero qué está disponible. ¿Hay algo en Boost que hace esto? ¿Alguien sabe de una implementación disponible en otro lugar?
Los tipos de colección intrusiva no se pueden usar aquí, ya que los mismos objetos deben existir en varias colecciones. Por lo que sé, las agrupaciones de memoria STL son por tipo, no por instancia (tipo de tipo, no, muchas advertencias). Estas agrupaciones globales no son eficientes con respecto a la localidad de memoria en el procesamiento mutli-cpu / core.
Los grupos de objetos no funcionan, ya que los tipos se compartirán entre instancias, pero su grupo no debería ser compartido.
En muchos casos, un mapa hash puede ser una opción.
Eche un vistazo a esto: Google Sparse Hash Map . Ha sido mi biblioteca favorita de C ++ desde que me encontré con ella hace algunos años.
Su rendimiento es increíble, tiene un mapa y una clase establecida, y tiene las funciones de reserva solicitadas. Cambié innumerables proyectos de otras estructuras de datos tipo mapa a google sparsehash con resultados increíbles. La sintaxis es compatible con C ++ 0x unordered_map (¡terrible, terrible nombre!), Pero también tiene funciones y características adicionales.
Internamente, se implementa con una tabla hash utilizando la técnica de sparsehashing.
EDITAR (13 de mayo de 2015)
Como esto se ha convertido en una respuesta popular, solo quería señalar otras dos estructuras tipo mapa que he estado usando en los últimos años. La biblioteca M varios Container T emplate (MCT) proporciona implementaciones de alto rendimiento unorderd_map de alto rendimiento en algunas variedades:
Proporciona seis contenedores de tabla hash de uso general: closed_hash_set, closed_hash_map, linked_hash_set, linked_hash_map, forward_hash_set y forward_hash_map. Los dos primeros son muy similares a TR1 unordered_set y unordered_map. Los vinculados proporcionan funcionalidad adicional, mientras que las tablas directas de hash son más eficientes que los vinculados, pero tienen una interfaz restringida. En algunos casos, el rendimiento de los contenedores closed_hash_ * se puede mejorar aún más con soporte de intrusividad opcional.
Y la folly de Facebook tiene algunas estructuras realmente geniales. No tienen un reemplazo de fbvector per-se, pero hay una implementación sin bloqueo / thread-safe de unordered_map y construir cosas alrededor de fbvector puede resultar en grandes ganancias de rendimiento debido a un mejor uso de memoria y diseño.
En mis pruebas, para el código de un solo subproceso, el dense_hash_map de Google dense_hash_map siendo mi opción preferida para obtener el máximo rendimiento.
Es posible que desee echar un vistazo a TCMalloc de Google. Es un reemplazo directo para malloc, que podría acelerar su programa. TCMalloc está específicamente diseñado para múltiples hilos.
Podrías usar un vector y una búsqueda binaria para almacenamiento contiguo y reserva () así como para mantener O (logn). Insertar sería más caro, sin embargo.
Una post reciente en la lista de correo de Boost discutió algo similar a esto.
Howard Hinnant ha creado un asignador que puede usar la pila en lugar del montón.