Enlaces externos
- CodeGuru: Allocators (STL) (en inglés)
- Implementación de un asignador personalizado basado en malloc (en inglés)
| Control de autoridades |
|
|---|
Datos: Q1869009
En la programación en C++, los asignadores (en inglés, allocators) son un componente de la biblioteca estándar de C++. La biblioteca estándar ofrece varias estructuras de datos, como la lista y el conjunto, a las que se suele llamar contenedores. Un rasgo común a estos contenedores es que pueden cambiar de tamaño durante la ejecución del programa. Para ello suele hacer falta algún tipo de asignación dinámica de memoria. Los asignadores atienden todas las peticiones de asignación y liberación de memoria de un contenedor dado. La biblioteca estándar de C++ proporciona asignadores de uso general que se emplean por defecto, aunque el programador también puede suministrar asignadores personalizados.
Los asignadores los inventó Alexander Stepanov como parte de la Standard Template Library (STL). En un principio se concibieron como un medio para que la biblioteca fuera más flexible e independiente del modelo de memoria subyacente, de modo que los programadores pudieran usar con ella tipos de puntero y de referencia personalizados. Sin embargo, al incorporar la STL a la norma de C++, el comité de normalización se dio cuenta de que una abstracción completa del modelo de memoria supondría una pérdida de rendimiento inaceptable. Para evitarlo, se endurecieron los requisitos de los asignadores. Como consecuencia, el grado de personalización que permiten los asignadores es más limitado de lo que Stepanov había previsto en un principio.
Aun así, hay muchas situaciones en las que conviene usar asignadores personalizados. Entre los motivos más habituales para escribirlos están mejorar el rendimiento de las asignaciones mediante pools de memoria y encapsular el acceso a distintos tipos de memoria, como la memoria compartida o la memoria gestionada por un recolector de basura. En particular, los programas que realizan con frecuencia muchas asignaciones de pequeñas cantidades de memoria pueden beneficiarse mucho de asignadores especializados, tanto en tiempo de ejecución como en consumo de memoria.
En la biblioteca estándar, los asignadores se encuentran en las siguientes cabeceras:
<memory>, para el tipo de asignador por defecto std::allocator<T><memory_resource>, para el asignador polimórfico en tiempo de ejecución std::pmr::polymorphic_allocator<T><scoped_allocator>, para el asignador multinivel std::scoped_allocator_adaptor<Out, In...>Alexander Stepanov y Meng Lee presentaron la Standard Template Library al comité de normalización de C++ en marzo de 1994. La biblioteca obtuvo una aprobación preliminar, aunque se plantearon objeciones. En concreto, se pidió a Stepanov que hiciera los contenedores de la biblioteca independientes del modelo de memoria subyacente, lo que dio lugar a la creación de los asignadores. Esto tuvo consecuencias para todos los componentes de la biblioteca.
Para adaptar la STL a la biblioteca estándar de C++, Stepanov trabajó estrechamente con varios miembros del comité de normalización, entre ellos Andrew Koenig y Bjarne Stroustrup. Stroustrup observó que los asignadores personalizados podrían servir para implementar contenedores de la STL con almacenamiento persistente, algo que Stepanov consideró entonces una idea «importante e interesante».
Desde el punto de vista de la portabilidad, todo lo que es específico de la máquina y se relaciona con la noción de dirección, puntero, etc., queda encapsulado en un mecanismo diminuto y bien comprendido. |
La propuesta original de los asignadores recurría a algunas características del lenguaje que el comité aún no había aceptado, en concreto la posibilidad de usar argumentos de plantilla que fueran a su vez plantillas. Como ningún compilador existente implementaba aún estas características, hubo, según Stepanov, «una enorme demanda del tiempo de Bjarne [Stroustrup] y Andy [Koenig] para comprobar que usábamos correctamente estas características no implementadas». Allí donde la biblioteca había usado directamente tipos de puntero y de referencia, pasó a referirse solo a los tipos definidos por el asignador. Stepanov describió más tarde los asignadores así: «Una buena característica de la STL es que el único lugar que menciona los tipos relacionados con la máquina (...) está encapsulado en unas 16 líneas de código».
Aunque Stepanov había querido en un principio que los asignadores encapsularan por completo el modelo de memoria, el comité de normalización se dio cuenta de que ese enfoque provocaría una pérdida de eficiencia inaceptable. Para evitarlo, se añadió texto a los requisitos de los asignadores. En particular, las implementaciones de los contenedores pueden suponer que las definiciones de tipo (typedef) del asignador para punteros y para los tipos enteros relacionados son equivalentes a las del asignador por defecto, y que todas las instancias de un mismo tipo de asignador son siempre iguales al compararlas, lo que en la práctica contradecía los objetivos de diseño originales de los asignadores y limitaba la utilidad de los asignadores con estado.
Stepanov comentó más tarde que, aunque los asignadores «no son tan mala idea en teoría (...) por desgracia no pueden funcionar en la práctica». Observó que, para que los asignadores fueran realmente útiles, era necesario cambiar la forma en que el núcleo del lenguaje trata las referencias.
La revisión de 2011 de la norma de C++ eliminó la redacción ambigua que permitía suponer que los asignadores de un mismo tipo siempre son iguales al compararlos y que usan punteros normales. Estos cambios hacen mucho más útiles los asignadores con estado y permiten que los asignadores gestionen memoria compartida. El propósito actual de los asignadores es dar al programador control sobre la asignación de memoria dentro de los contenedores, más que adaptar el modelo de direcciones del hardware subyacente. De hecho, la norma revisada eliminó la capacidad de los asignadores para representar extensiones del modelo de direcciones de C++, con lo que suprimió formalmente (y de forma deliberada) su propósito original.
Cualquier clase que cumpla los requisitos de asignador puede usarse como asignador. En particular, según la norma C++03, una clase A capaz de asignar memoria para un objeto de tipo T debe proporcionar los tipos A::pointer, A::const_pointer, A::reference, A::const_reference y A::value_type para declarar de forma genérica objetos y referencias (o punteros) a objetos de tipo T. También debe proporcionar el tipo A::size_type, un tipo sin signo que puede representar el tamaño máximo de un objeto en el modelo de asignación definido por A, y, de forma análoga, un tipo entero con signo A::difference_type que puede representar la diferencia entre dos punteros cualesquiera del modelo de asignación.
Aunque una implementación conforme de la biblioteca estándar puede suponer que A::pointer y A::const_pointer del asignador son simplemente typedef de T* y const T*, se anima a los implementadores de bibliotecas a admitir asignadores más generales.
Un asignador A para objetos de tipo T debe tener una función miembro con la firma
A::pointer A::allocate(A::size_type n, A<void>::const_pointer hint = 0);
Esta función devuelve un puntero al primer elemento de un array recién asignado con espacio suficiente para n objetos de tipo T; solo se asigna la memoria, y los objetos no se construyen. Además, un argumento opcional de tipo puntero (que apunta a un objeto ya asignado por A) puede servir de indicación a la implementación sobre dónde asignar la nueva memoria para mejorar la localidad. No obstante, la implementación puede ignorar este argumento.
La función miembro correspondiente, void A::deallocate(A::pointer p, A::size_type n), acepta cualquier puntero devuelto por una llamada anterior a la función miembro A::allocate y el número de elementos que se deben liberar (pero no destruir).
La función miembro A::max_size() devuelve el número máximo de objetos de tipo T que cabe esperar que una llamada a A::allocate asigne con éxito; el valor devuelto suele ser A::size_type(-1) / sizeof(T). Por otra parte, la función miembro A::address devuelve un A::pointer que indica la dirección de un objeto, dado un A::reference.
La construcción y destrucción de objetos se realizan por separado de la asignación y la liberación de memoria. El asignador debe tener dos funciones miembro, A::construct y A::destroy, que se encargan, respectivamente, de construir y destruir objetos (ambas funciones quedaron obsoletas en C++17 y se eliminaron en C++20). La semántica de estas funciones debe ser equivalente a la siguiente:
template <typename T>
void A::construct(A::pointer p, A::const_reference t) {
new ((void*) p) T(t);
}
template <typename T>
void A::destroy(A::pointer p){
((T*)p)->~T();
}
El código anterior usa la sintaxis de placement new y llama directamente al destructor.
Los asignadores deben poder construirse por copia. Un asignador para objetos de tipo T puede construirse a partir de un asignador para objetos de tipo U. Si un asignador A asigna una región de memoria R, entonces R solo puede liberarla un asignador que sea igual a A al compararlos.
Los asignadores deben proporcionar una plantilla de clase miembro rebind:
template <typename U>
struct A::rebind {
using other = A<U>;
};
que permite obtener un asignador relacionado, parametrizado con otro tipo. Por ejemplo, dado un tipo de asignador IntAllocator para objetos de tipo int, se podría obtener un tipo de asignador relacionado para objetos de tipo long mediante IntAllocator::rebind<long>::other.
Uno de los principales motivos para escribir un asignador personalizado es el rendimiento. Un asignador personalizado especializado puede mejorar notablemente el rendimiento del programa, su uso de memoria o ambos. El asignador por defecto usa operator new para asignar memoria. Este suele implementarse como una capa fina sobre las funciones de asignación del montón de C, que suelen estar optimizadas para asignaciones poco frecuentes de bloques de memoria grandes. Este enfoque puede funcionar bien con contenedores que asignan sobre todo grandes porciones de memoria, como std::vector y std::deque. Sin embargo, en los contenedores que necesitan asignar con frecuencia objetos pequeños, como std::map (un mapa implementado como árbol rojo-negro) y std::list (una lista doblemente enlazada), usar el asignador por defecto suele ser lento. Otros problemas habituales de los asignadores basados en malloc son una mala localidad de referencia y una excesiva fragmentación de la memoria.
Un enfoque muy extendido para mejorar el rendimiento es crear un asignador basado en un pool de memoria. En lugar de asignar memoria cada vez que se inserta o elimina un elemento de un contenedor, se asigna de antemano un gran bloque de memoria (el pool), posiblemente al iniciar el programa. El asignador personalizado atiende cada petición de asignación devolviendo simplemente un puntero a memoria del pool. La liberación efectiva de la memoria puede aplazarse hasta que termine el tiempo de vida del pool. Las bibliotecas Boost incluyen ejemplos de asignadores basados en pools de memoria.
Otro uso de los asignadores personalizados es la depuración de errores relacionados con la memoria. Para ello se puede escribir un asignador que asigne memoria adicional en la que guarde información de depuración. Un asignador así podría usarse para comprobar que la memoria se asigna y se libera con el mismo tipo de asignador, y también ofrecería una protección limitada frente a los desbordamientos.
En resumen, este párrafo (...) es el discurso de «Yo tengo un sueño» de la norma para los asignadores. Hasta que ese sueño se haga realidad, los programadores preocupados por la portabilidad se limitarán a asignadores personalizados sin estado. —Scott Meyers, Effective STL |
Numerosos expertos y autores de C++ han tratado el tema de los asignadores personalizados, entre ellos Scott Meyers en Effective STL y Andrei Alexandrescu en Modern C++ Design. Meyers subraya que C++98 exige que todas las instancias de un asignador sean equivalentes y señala que, en la práctica, esto obliga a que los asignadores portables no tengan estado. Aunque la norma C++98 animaba a los implementadores de bibliotecas a admitir asignadores con estado, Meyers califica el párrafo correspondiente de «un sentimiento encantador» que «no ofrece casi nada» y describe la restricción como «draconiana».
En su libro The C++ Programming Language, Bjarne Stroustrup sostiene, en cambio, que la «restricción aparentemente draconiana contra la información por objeto en los asignadores no es especialmente grave», y señala que la mayoría de los asignadores no necesitan estado y rinden mejor sin él. Menciona tres casos de uso de los asignadores personalizados: asignadores con pool de memoria, asignadores de memoria compartida y asignadores de memoria gestionada por recolección de basura. Presenta una implementación de asignador que usa un pool de memoria interno para asignar y liberar rápidamente pequeñas porciones de memoria, pero advierte que el asignador proporcionado por la implementación puede realizar ya esa optimización.
Al instanciar uno de los contenedores estándar, el asignador se especifica mediante un argumento de plantilla, cuyo valor por defecto es std::allocator<T>, mientras que los del espacio de nombres std::pmr usan el asignador std::pmr::polymorphic_allocator<T>.
namespace std {
template <typename T, typename Alloc = allocator<T>>
class vector;
// ...
namespace pmr {
template <typename T>
using vector = ::std::vector<T, polymorphic_allocator<T>>;
// ...
}
}
Como ocurre con todas las plantillas de clase de C++, las instancias de los contenedores de la biblioteca estándar con distintos argumentos de asignador son tipos distintos. Por tanto, una función que espere un argumento std::vector<int> solo aceptará un vector instanciado con el asignador por defecto.
La norma C++11 mejoró la interfaz de los asignadores para admitir asignadores «con ámbito» (scoped), de modo que los contenedores con asignaciones de memoria «anidadas», como un vector de cadenas o un mapa de listas de conjuntos de tipos definidos por el usuario, puedan garantizar que toda la memoria procede del asignador del contenedor.
El siguiente ejemplo usa la cabecera <bits/new_allocator.h> de la biblioteca libstdc++ de GNU Compiler Collection.
import <bits/new_allocator.h>;
import std;
using std::bad_alloc;
using std::string;
using std::string_view;
using __gnu_cxx::new_allocator;
class RequiredAllocation {
private:
static constexpr string_view DEFAULT_NAME = "Hello, world!\n";
public:
const string name;
RequiredAllocation(string_view name = DEFAULT_NAME):
name{string(name)} {
std::println("RequiredAllocation constructor");
}
~RequiredAllocation() {
std::println("RequiredAllocation destructor");
}
};
void alloc(new_allocator<RequiredAllocation>& all, size_t size, void* p, RequiredAllocation& t) {
try {
all.allocate(size, p);
std::println("{}", all.max_size());
for (char c : t.name) {
std::println("{}", c);
}
} catch (const bad_alloc& e) {
std::println(stderr, "Bad allocation exception: {}", e.what());
}
}
int main() {
new_allocator<RequiredAllocation> all;
RequiredAllocation t;
void* pt = &t;
// Cuando new no encuentra memoria que asignar,
// el asignador lanza por defecto std::bad_alloc
constexpr size_t BAD_SIZE = 1073741824;
alloc(all, BAD_SIZE, &pt, t);
constexpr size_t SMALL_SIZE = 1;
alloc(all, SMALL_SIZE, &pt, t);
return 0;
}
| Control de autoridades |
|
|---|
Datos: Q1869009