¿Ejemplos convincentes de asignadores personalizados de C ++?

176

¿Cuáles son algunas razones realmente buenas para deshacerse std::allocatorde una solución personalizada? ¿Te has encontrado con situaciones en las que era absolutamente necesario para la corrección, el rendimiento, la escalabilidad, etc.? ¿Algún ejemplo realmente inteligente?

Los asignadores personalizados siempre han sido una característica de la Biblioteca estándar que no he tenido mucha necesidad. Me preguntaba si alguien aquí en SO podría proporcionar algunos ejemplos convincentes para justificar su existencia.

Naaff
fuente

Respuestas:

121

Como mencioné aquí , he visto que el asignador STL personalizado de Intel TBB mejora significativamente el rendimiento de una aplicación multiproceso simplemente cambiando un solo

std::vector<T>

a

std::vector<T,tbb::scalable_allocator<T> >

(esta es una forma rápida y conveniente de cambiar el asignador para usar los ingeniosos montones de subprocesos privados de TBB; consulte la página 7 de este documento )

día
fuente
3
Gracias por ese segundo enlace. El uso de asignadores para implementar montones privados de hilos es inteligente. Me gusta que este sea un buen ejemplo de que los asignadores personalizados tienen una clara ventaja en un escenario que no tiene recursos limitados (incrustación o consola).
Naaff
77
El enlace original ahora está desactivado
Arto Bendiken
1
Tengo que preguntar: ¿Puede mover de manera confiable ese vector a otro hilo? (Supongo que no)
sellibitze
@sellibitze: Dado que los vectores se manipulaban desde dentro de las tareas de TBB y se reutilizaban en múltiples operaciones paralelas y no hay garantía de qué subproceso de trabajo TBB recogerá las tareas, concluyo que funciona bien. Aunque tenga en cuenta que ha habido algunos problemas históricos con TBB liberando cosas creadas en un hilo en otro hilo (aparentemente un problema clásico con montones privados de hilos y patrones de asignación y desasignación productor-consumidor. TBB afirma que su asignador evita estos problemas, pero he visto lo contrario Tal vez arreglado en versiones más recientes.)
Timday
@ArtoBendiken: el enlace de descarga en su enlace no parece ser válido.
einpoklum
81

Un área donde los asignadores personalizados pueden ser útiles es el desarrollo de juegos, especialmente en consolas de juegos, ya que tienen solo una pequeña cantidad de memoria y no se intercambian. En dichos sistemas, debe asegurarse de tener un control estricto sobre cada subsistema, de modo que un sistema no crítico no pueda robar la memoria de uno crítico. Otras cosas como los asignadores de grupos pueden ayudar a reducir la fragmentación de la memoria. Puede encontrar un documento largo y detallado sobre el tema en:

EASTL - Biblioteca de plantillas estándar de Electronic Arts

Grumbel
fuente
14
+1 para el enlace EASTL: "Entre los desarrolladores de juegos, la debilidad más fundamental [de la STL] es el diseño del asignador estándar, y esta debilidad fue el factor que más contribuyó a la creación de EASTL".
Naaff
65

Estoy trabajando en un mmap-allocator que permite a los vectores usar la memoria de un archivo mapeado en memoria. El objetivo es tener vectores que usen almacenamiento que estén directamente en la memoria virtual mapeados por mmap. Nuestro problema es mejorar la lectura de archivos realmente grandes (> 10 GB) en la memoria sin sobrecarga de copia, por lo tanto, necesito este asignador personalizado.

Hasta ahora tengo el esqueleto de un asignador personalizado (que se deriva de std :: allocator), creo que es un buen punto de partida para escribir asignadores propios. Siéntase libre de usar este código de la forma que desee:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Para usar esto, declare un contenedor STL de la siguiente manera:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Se puede usar, por ejemplo, para iniciar sesión cada vez que se asigna memoria. Lo que es necesario es la estructura de reenlace, de lo contrario, el contenedor de vectores utiliza los métodos de asignación / desasignación de superclases.

Actualización: El asignador de asignación de memoria ahora está disponible en https://github.com/johannesthoma/mmap_allocator y es LGPL. Siéntase libre de usarlo para sus proyectos.

Johannes Thoma
fuente
17
Solo un aviso, derivado de std :: allocator no es realmente la forma idiomática de escribir asignadores. En su lugar, debe mirar allocator_traits, que le permite proporcionar el mínimo de funcionalidad, y la clase de rasgos proporcionará el resto. Tenga en cuenta que el STL siempre usa su asignador a través de allocator_traits, no directamente, por lo que no necesita referirse a allocator_traits usted mismo. No hay muchos incentivos para derivar de std :: allocator (aunque este código puede ser un punto de partida útil independientemente).
Nir Friedman
25

Estoy trabajando con un motor de almacenamiento MySQL que usa c ++ para su código. Estamos utilizando un asignador personalizado para usar el sistema de memoria MySQL en lugar de competir con MySQL por la memoria. Nos permite asegurarnos de que estamos usando memoria como el usuario configuró MySQL para usar, y no "extra".

Thomas Jones-Low
fuente
21

Puede ser útil usar asignadores personalizados para usar un grupo de memoria en lugar del montón. Ese es un ejemplo entre muchos otros.

Para la mayoría de los casos, esta es ciertamente una optimización prematura. Pero puede ser muy útil en ciertos contextos (dispositivos integrados, juegos, etc.).

Martin Cote
fuente
3
O, cuando ese grupo de memoria se comparte.
Anthony
9

No he escrito código C ++ con un asignador STL personalizado, pero puedo imaginar un servidor web escrito en C ++, que utiliza un asignador personalizado para la eliminación automática de datos temporales necesarios para responder a una solicitud HTTP. El asignador personalizado puede liberar todos los datos temporales a la vez una vez que se ha generado la respuesta.

Otro posible caso de uso para un asignador personalizado (que he usado) es escribir una prueba unitaria para demostrar que el comportamiento de una función no depende de alguna parte de su entrada. El asignador personalizado puede llenar la región de memoria con cualquier patrón.

pts
fuente
55
Parece que el primer ejemplo es el trabajo del destructor, no el asignador.
Michael Dorst
2
Si le preocupa que su programa dependa del contenido inicial de la memoria del montón, una ejecución rápida (es decir, ¡durante la noche!) En valgrind le permitirá saber de una forma u otra.
cdyson37
3
@anthropomorphic: el destructor y el asignador personalizado funcionarían juntos, el destructor se ejecutaría primero, luego la eliminación del asignador personalizado, que aún no llamará a free (...), pero se llamará a free (...) más tarde, cuando se entregue la solicitud ha finalizado. Esto puede ser más rápido que el asignador predeterminado y reducir la fragmentación del espacio de direcciones.
pts
8

Cuando se trabaja con GPU u otros coprocesadores, a veces es beneficioso asignar estructuras de datos en la memoria principal de una manera especial . Esta forma especial de asignar memoria se puede implementar en un asignador personalizado de manera conveniente.

La razón por la cual la asignación personalizada a través del tiempo de ejecución del acelerador puede ser beneficiosa cuando se usan aceleradores es la siguiente:

  1. a través de la asignación personalizada, el tiempo de ejecución del acelerador o el controlador reciben una notificación del bloqueo de memoria
  2. Además, el sistema operativo puede asegurarse de que el bloque de memoria asignado esté bloqueado en la página (algunos llaman a esta memoria fijada ), es decir, el subsistema de memoria virtual del sistema operativo no puede mover o eliminar la página dentro o fuera de la memoria
  3. si 1. y 2. se mantienen y se solicita una transferencia de datos entre un bloque de memoria bloqueado en la página y un acelerador, el tiempo de ejecución puede acceder directamente a los datos en la memoria principal ya que sabe dónde está y puede estar seguro de que el sistema operativo no mover / eliminarlo
  4. esto ahorra una copia de la memoria que ocurriría con la memoria que se asignó de una manera sin bloqueo de página: los datos deben copiarse en la memoria principal en un área de almacenamiento bloqueada desde el acelerador puede inicializar la transferencia de datos (a través de DMA )
Sebastian
fuente
1
... para no olvidar los bloques de memoria alineados con la página. Esto es especialmente útil si está hablando con un controlador (es decir, con FPGA a través de DMA) y no desea la molestia y la sobrecarga de calcular las compensaciones in-page para sus listas de dispersión de DMA.
Jan
7

Estoy usando asignadores personalizados aquí; incluso podrías decir que fue para evitar otra administración de memoria dinámica personalizada.

Antecedentes: tenemos sobrecargas para malloc, calloc, free y las diversas variantes de operador new y delete, y el enlazador felizmente hace que STL las use para nosotros. Esto nos permite hacer cosas como la agrupación automática de objetos pequeños, detección de fugas, relleno de asignación, relleno libre, asignación de relleno con centinelas, alineación de línea de caché para ciertas asignaciones y liberación retardada.

El problema es que estamos funcionando en un entorno incrustado: no hay suficiente memoria para hacer la contabilidad de detección de fugas correctamente durante un período prolongado. Al menos, no en la RAM estándar: hay otro montón de RAM disponible en otros lugares, a través de funciones de asignación personalizadas.

Solución: escriba un asignador personalizado que use el montón extendido y úselo solo en la parte interna de la arquitectura de seguimiento de fugas de memoria ... Todo lo demás se predetermina a las sobrecargas normales nuevas / eliminadas que hacen el seguimiento de fugas. Esto evita que el rastreador se rastree a sí mismo (y también proporciona un poco de funcionalidad de empaque adicional, sabemos el tamaño de los nodos del rastreador).

También usamos esto para mantener los datos de perfiles de costos de funciones, por la misma razón; escribir una entrada para cada llamada de función y devolución, así como los conmutadores de subprocesos, puede ser costoso rápidamente. El asignador personalizado nuevamente nos da asignaciones más pequeñas en un área de memoria de depuración más grande.

leander
fuente
5

Estoy usando un asignador personalizado para contar el número de asignaciones / desasignaciones en una parte de mi programa y medir cuánto tiempo lleva. Hay otras formas de lograrlo, pero este método es muy conveniente para mí. Es especialmente útil que pueda usar el asignador personalizado solo para un subconjunto de mis contenedores.

Jørgen Fogh
fuente
4

Una situación esencial: al escribir código que debe funcionar a través de los límites del módulo (EXE / DLL), es esencial mantener sus asignaciones y eliminaciones en un solo módulo.

Donde me encontré con esto fue una arquitectura de complemento en Windows. Es esencial que, por ejemplo, si pasa una cadena std :: a través del límite de la DLL, cualquier reasignación de la cadena se produzca desde el montón de donde se originó, NO el montón en la DLL que puede ser diferente *.

* En realidad, es más complicado que esto, ya que si se está vinculando dinámicamente al CRT, esto podría funcionar de todos modos. Pero si cada DLL tiene un enlace estático al CRT, se dirige a un mundo de dolor, donde continuamente ocurren errores de asignación fantasma.

Stephen
fuente
Si pasa objetos a través de los límites de la DLL, debe usar la configuración de DLL (/ MD (d)) multiproceso (Debug) para ambos lados. C ++ no fue diseñado teniendo en cuenta el soporte de módulos. Alternativamente, podría proteger todo detrás de las interfaces COM y usar CoTaskMemAlloc. Esta es la mejor manera de utilizar interfaces de complementos que no están vinculadas a un compilador, STL o proveedor específico.
gast128
La regla de los viejos es: no lo hagas. No use tipos STL en la API DLL. Y no pase la responsabilidad de la memoria dinámica a través de los límites de la API DLL. No hay ABI de C ++, por lo que si trata cada DLL como una API de C, evitará toda una clase de problemas potenciales. A expensas de "c ++ beauty", por supuesto. O como sugiere el otro comentario: use COM. Simplemente C ++ es una mala idea.
BitTickler
3

Un ejemplo de tiempo cuando los he usado fue trabajar con sistemas embebidos con recursos limitados. Digamos que tienes 2k de RAM gratis y tu programa tiene que usar algo de esa memoria. Debe almacenar, por ejemplo, 4-5 secuencias en algún lugar que no esté en la pila y, además, debe tener un acceso muy preciso sobre dónde se almacenan estas cosas, esta es una situación en la que es posible que desee escribir su propio asignador. Las implementaciones predeterminadas pueden fragmentar la memoria, esto puede ser inaceptable si no tiene suficiente memoria y no puede reiniciar su programa.

Un proyecto en el que estaba trabajando era usar AVR-GCC en algunos chips de baja potencia. Tuvimos que almacenar 8 secuencias de longitud variable pero con un máximo conocido. La implementación estándar de la biblioteca de la gestión de memoria.es un envoltorio delgado alrededor de malloc / free que realiza un seguimiento de dónde colocar los elementos al anteponer cada bloque de memoria asignado con un puntero justo más allá del final de ese pedazo de memoria asignado. Al asignar una nueva pieza de memoria, el asignador estándar tiene que caminar sobre cada una de las piezas de memoria para encontrar el siguiente bloque que esté disponible donde se ajuste el tamaño de memoria solicitado. En una plataforma de escritorio, esto sería muy rápido para estos pocos elementos, pero debe tener en cuenta que algunos de estos microcontroladores son muy lentos y primitivos en comparación. Además, el problema de la fragmentación de la memoria era un problema enorme que significaba que realmente no teníamos más remedio que adoptar un enfoque diferente.

Entonces, lo que hicimos fue implementar nuestro propio grupo de memoria . Cada bloque de memoria era lo suficientemente grande como para ajustarse a la secuencia más grande que necesitaríamos en él. Esto asignó bloques de memoria de tamaño fijo con anticipación y marcó qué bloques de memoria estaban actualmente en uso. Lo hicimos manteniendo un número entero de 8 bits donde cada bit representaba si se usaba un determinado bloque. Intercambiamos el uso de memoria aquí por intentar acelerar todo el proceso, lo que en nuestro caso se justificó porque estábamos empujando este chip microcontrolador cerca de su capacidad máxima de procesamiento.

Hay varias otras veces que puedo ver escribir su propio asignador personalizado en el contexto de los sistemas integrados, por ejemplo, si la memoria para la secuencia no está en el RAM principal, como podría ser el caso en estas plataformas .

lanzadera87
fuente
2

Para la memoria compartida es vital que no solo la cabeza del contenedor, sino también los datos que contiene se almacenen en la memoria compartida.

El asignador de Boost :: Interprocess es un buen ejemplo. Sin embargo, como puede leer aquí, todo esto no es suficiente para que todos los contenedores STL sean compatibles con la memoria compartida (debido a las diferentes compensaciones de mapeo en diferentes procesos, los punteros pueden "romperse").

ted
fuente
2

Hace algún tiempo encontré esta solución muy útil para mí: asignador rápido C ++ 11 para contenedores STL . Acelera ligeramente los contenedores STL en VS2017 (~ 5x) así como en GCC (~ 7x). Es un asignador de propósito especial basado en un grupo de memoria. Se puede usar con contenedores STL solo gracias al mecanismo que está solicitando.

nadie especial
fuente
1

Personalmente uso Loki :: Allocator / SmallObject para optimizar el uso de la memoria para objetos pequeños: muestra una buena eficiencia y un rendimiento satisfactorio si tiene que trabajar con cantidades moderadas de objetos realmente pequeños (1 a 256 bytes). Puede ser hasta ~ 30 veces más eficiente que la asignación nueva / eliminación estándar de C ++ si hablamos de asignar cantidades moderadas de objetos pequeños de muchos tamaños diferentes. Además, hay una solución específica de VC llamada "QuickHeap", que brinda el mejor rendimiento posible (las operaciones de asignación y desasignación solo leen y escriben la dirección del bloque que se asigna / devuelve al montón, respectivamente en hasta 99. (9)% de los casos - depende de la configuración y la inicialización), pero a un costo de una sobrecarga notable - necesita dos punteros por extensión y un extra por cada nuevo bloque de memoria. Eso'

El problema con la implementación estándar de C ++ new / delete es que generalmente es solo un contenedor para la asignación C malloc / free, y funciona bien para bloques de memoria más grandes, como 1024+ bytes. Tiene una sobrecarga notable en términos de rendimiento y, a veces, memoria adicional utilizada para el mapeo también. Por lo tanto, en la mayoría de los casos, los asignadores personalizados se implementan para maximizar el rendimiento y / o minimizar la cantidad de memoria adicional necesaria para asignar objetos pequeños (≤1024 bytes).

Multiversidad Fractal
fuente
1

En una simulación de gráficos, he visto asignadores personalizados utilizados para

  1. Restricciones de alineación que std::allocator no eran directamente compatibles.
  2. Minimizar la fragmentación mediante el uso de agrupaciones separadas para asignaciones de corta duración (solo este marco) y de larga duración.
Adrian McCarthy
fuente