std :: map rendimiento del asignador estándar versus asignador de bloque

Question

He leído en un libro de recetas de optimización C++ que el asignador estándar para contenedores STL como std :: list, std :: set, std :: multi_set, std :: map , e std :: multi_map puede ser reemplazado por un asignador de bloque más eficaz.

Un asignador de bloques tiene un mayor rendimiento, baja fragmentación y almacenamiento de datos eficiente.

He encontrado en la web el FSBAllocator que dice ser más rápido que el estándar. http://warp.povusers.org/FSBAllocator/

Yo lo he probado con std :: mapa y encontrar el más rápido parece ser cierto, pero mi pregunta es ¿cómo puede ser la implementación STL sea tan lento que un asignador específica y cuáles son los inconvenientes de otro asignador que el estándar, en términos de portabilidad y robustez? Mi código debe compilarse en una variedad de arquitecturas (win32, osx, linux). ¿Alguien tiene experiencia con ese tipo de asignador de bloque de tamaño fijo?

Answer 1

Un asignador de bloque hace una gran asignación a la tienda/montón libre, a continuación, internamente divide esta memoria en trozos. Una desventaja aquí es que asigna este trozo (que debe ser grande, y a menudo especificado por el usuario por caso de uso) hacia arriba, por lo que incluso si no lo usa todo, esa memoria está atada. En segundo lugar, el asignador de memoria estándar está construido encima de nuevo/eliminar, que a su vez a menudo se construye encima de malloc/free. Aunque no recuerdo si malloc/free garantiza la seguridad de subprocesos en cualquier circunstancia, generalmente lo es.

Pero, por último, la razón por la que los asignadores de bloque funcionan tan bien es porque tienen información que no está presente en los asignadores estándar, y no necesitan cubrir un amplio conjunto de casos de uso. Por ejemplo, si hiciste std::map< int, int >() y asignó 1mb probablemente te cabrearías, pero si lo haces std::map< int, int, std::less<int>, block_alloc< 1024 * 1024 > >() lo estarías esperando. Los asignadores estándar no se asignan en bloques, solicitan nueva memoria a través de nuevos, los nuevos a su vez no tienen ningún contexto. Obtiene una solicitud de memoria de un tamaño arbitrario y necesita encontrar un número contiguo de bytes para devolver. Lo que hacen la mayoría de las implementaciones es que tienen un conjunto de áreas de memoria que mantienen de diferentes múltiplos (por ejemplo, una región de 4 bytes probablemente está garantizada, ya que las solicitudes de 4 bytes son muy comunes). Si una solicitud no es un múltiplo par, es más difícil devolver un buen pedazo sin perder espacio y causar fragmentación. Básicamente, la administración de memoria de tamaños arbitrarios es muy difícil de hacer si quiere que esté cerca del tiempo constante, baja fragmentación, seguridad de subprocesos, etc.

La documentación de Boost pool allocator contiene información sobre cómo puede funcionar un buen asignador de bloque.