¿Ejemplos convincentes de asignadores de C ++ personalizados?

Question

¿Cuáles son algunas razones realmente buenas para deshacerse de std :: allocator a favor de una solución personalizada? ¿Ha encontrado alguna situación en la que fuera 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 necesitado mucho. Me preguntaba si alguien aquí en SO podría proporcionar algunos ejemplos convincentes para justificar su existencia.

Answer 1

Como menciono aquí , he visto el STL personalizado de Intel TBB el asignador mejora significativamente el rendimiento de una aplicación multiproceso simplemente cambiando una sola

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 montones de hilos privados del TBB; consulte página 7 en este documento )

Answer 2

Un área donde los asignadores personalizados pueden ser útiles es el desarrollo de juegos, especialmente en consolas de juegos, ya que solo tienen una pequeña cantidad de memoria y no tienen intercambio. 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

Answer 3

Estoy trabajando en un asignador de mmap que permite que los vectores usen la memoria de un archivo mapeado en memoria. El objetivo es tener vectores que usen almacenamiento que Se encuentran directamente en la memoria virtual mapeada por mmap. Nuestro problema es mejora la lectura de archivos realmente grandes (> 10GB) en la memoria sin copia sobrecarga, por lo tanto necesito este asignador personalizado.

Hasta ahora tengo el esqueleto de un asignador personalizado (que deriva de std :: allocator), creo que es un buen comienzo Punto para escribir asignadores propios. Siéntete libre de usar este pedazo de código en la forma que quieras:

#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 de 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 registrar cada vez que se asigna memoria. Lo que es necesario es la estructura de revinculación; de lo contrario, el contenedor vectorial utiliza las superclases asignar / desasignar métodos.

Actualización: el asignador de mapeo de memoria ahora está disponible en https://github.com/johannesthoma/mmap_allocator y es LGPL. Siéntete libre de usarlo para tus proyectos.

Answer 4

Estoy trabajando con un motor de almacenamiento MySQL que usa c ++ para su código. Estamos usando 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 la memoria como el usuario configuró MySQL para su uso, y no " extra " ;.

Answer 5

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.).

Answer 6

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

Otro posible caso de uso para un asignador personalizado (que he usado) es escribir una prueba de unidad 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.

Answer 7

Cuando se trabaja con GPU u otros co-procesadores, a veces es beneficioso asignar estructuras de datos en la memoria principal de una forma especial . Esta forma especial de asignar memoria puede implementarse 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, se notifica al bloque de memoria el tiempo de ejecución del acelerador o el controlador
2. además, el sistema operativo puede asegurarse de que el bloque de memoria asignado esté bloqueado en la página (algunos llaman a esto pinned memory ), es decir, el subsistema de memoria virtual del sistema operativo puede no moverse o eliminar la página dentro o desde la memoria
3. si 1. y 2. se retienen y se solicita una transferencia de datos entre un bloque de memoria bloqueado por 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 está funcionando. El sistema no se movió / eliminó
4. esto guarda una copia de la memoria que se produciría con la memoria que se asignó de forma no bloqueada en la página: los datos deben copiarse en la memoria principal a un área de almacenamiento de páginas bloqueadas con el acelerador para inicializar la transferencia de datos (a través de DMA)

Answer 8

Estoy usando asignadores personalizados aquí; incluso podría decir que fue para trabajar alrededor de 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 vinculador hace que STL los use por nosotros. Esto nos permite hacer cosas como la agrupación automática de pequeños objetos, la detección de fugas, el relleno de asignación, el relleno libre, la asignación de relleno con centinelas, la alineación de la línea de caché para determinadas asignaciones y la demora gratuita.

El problema es que nos estamos ejecutando en un entorno integrado: no hay suficiente memoria para realizar 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 otro lugar, a través de funciones de asignación personalizadas.

Solución: escriba un asignador personalizado que use el montón extendido, y utilícelo solo en la parte interna de la arquitectura de seguimiento de fugas de memoria ... Todo lo demás se establece de manera predeterminada en las sobrecargas normales nuevas / eliminadas que hace seguimiento de fugas. Esto evita el seguimiento del rastreador en sí (y también proporciona un poco de funcionalidad de empaquetado adicional, sabemos el tamaño de los nodos del rastreador).

También utilizamos esto para mantener los datos de perfiles de costo de la función, por el mismo motivo; escribir una entrada para cada llamada de función y retorno, así como los cambios de hilos, 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.

Answer 9

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 en que esto podría lograrse, 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.

Answer 10

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 era 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, que se produzcan reasignaciones de la cadena desde el montón desde donde se originó, NO la pila en la DLL, que puede ser diferente *.

* En realidad, es más complicado que esto, ya que si está enlazando dinámicamente con el 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 ocurren errores de asignación fantasma.

Answer 11

Un ejemplo de tiempo en que los he usado fue trabajar con sistemas embebidos con recursos muy limitados. Digamos que tienes 2k de ram libre 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, necesita tener un acceso muy preciso sobre dónde se almacenan estas cosas, esta es una situación en la que podría querer escribir su propio asignador. Las implementaciones predeterminadas pueden fragmentar la memoria, esto podría 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 de la biblioteca estándar de la gestión de memoria es una envoltura delgada malloc / free, que mantiene un registro de dónde colocar los elementos, al anteponer cada bloque de memoria asignado con un puntero hasta el final de la memoria asignada. Al asignar una nueva pieza de memoria, el asignador estándar tiene que caminar sobre cada una de las piezas de la memoria para encontrar el siguiente bloque que está disponible donde se ajustará el tamaño solicitado de la memoria. En una plataforma de escritorio, esto sería muy rápido para estos pocos elementos, pero hay que 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 masivo que significaba que realmente no teníamos otra opción más que adoptar un enfoque diferente.

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

Hay muchas otras veces que puedo ver escribiendo su propio asignador personalizado en el contexto de sistemas integrados, por ejemplo, si la memoria de la secuencia no está en el ram principal como suele ser el caso en estas plataformas .

Answer 12

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

El asignador de Boost :: Interproceso es un buen ejemplo. Sin embargo, como puede leer aquí esta opción no es suficiente para hacer que todos los contenedores STL sean compatibles con la memoria compartida (debido a las diferentes compensaciones de mapeo en diferentes procesos, los punteros podrían "romperse").

Answer 13

Enlace obligatorio a la charla CppCon 2015 de Andrei Alexandrescu sobre asignadores:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Lo bueno es que el hecho de idearlos te hace pensar en ideas de cómo los usarías :-)

Answer 14

Hace algún tiempo encontré esta solución muy útil para mí: asignador rápido de 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 el conjunto de memoria. Solo se puede utilizar con contenedores STL gracias al mecanismo que solicita.

Answer 15

Personalmente uso Loki :: Allocator / SmallObject para optimizar el uso de la memoria para objetos pequeños: muestra una buena eficiencia y un desempeño 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 de nuevos / borrados de C ++ estándar si hablamos de asignar cantidades moderadas de objetos pequeños de diferentes tamaños. Además, hay una solución específica de VC llamada "QuickHeap", que ofrece 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 hasta 99. (9)% 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 uno extra por cada nuevo bloque de memoria. Es la solución más rápida posible para trabajar con grandes cantidades (10 000 ++) de objetos que se crean y eliminan si no necesita una gran variedad de tamaños de objetos (crea un grupo individual para cada tamaño de objeto, de 1 a 1023 bytes) en la implementación actual, por lo que los costos de inicialización pueden minimizar el aumento general del rendimiento, pero uno puede continuar y asignar / desasignar algunos objetos ficticios antes de que la aplicación ingrese en su (s) fase (s) críticas para el rendimiento).

El problema con la implementación estándar de C ++ new / delete es que generalmente es solo un contenedor para la asignación de 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, también se utiliza memoria adicional para la asignació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 extra necesaria para asignar objetos pequeños (=1024 bytes).

Answer 16

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

1. Restricciones de alineación que std :: allocator no admitían directamente.
2. Minimizar la fragmentación utilizando grupos separados para asignaciones de corta duración (solo este marco) y de larga duración.