estrategia para asignar/liberar lotes de objetos pequeños

Question

Estoy jugando con cierto algoritmo de almacenamiento en caché, lo cual es un tanto desafiante. Básicamente, necesita asignar muchos objetos pequeños (matrices dobles, de 1 a 256 elementos), con objetos accesibles a través del valor asignado, map[key] = array. el tiempo para la matriz inicializada puede ser bastante grande, generalmente más de 10 mil ciclos de CPU.

Por lotes me refiero a alrededor de gigabytes en total. Es posible que sea necesario hacer estallar/empujar objetos según sea necesario, generalmente en lugares aleatorios, un objeto a la vez. la vida útil de un objeto es generalmente larga, de minutos o más, sin embargo, el objeto puede estar sujeto a asignación/desasignación varias veces durante la duración del programa.

¿Cuál sería una buena estrategia para evitar la fragmentación de la memoria, mientras se mantiene una asignación razonable de la velocidad de desasignación?

Estoy usando C++, entonces puedo usar new y malloc. Gracias.

Sé que hay preguntas similares en el sitio web, Efficiently allocating many short-lived small objects, son algo diferentes, la seguridad del hilo no es un problema inmediato para mí.

mi plataforma de desarrollo es Intel Xeon, sistema operativo Linux. Idealmente, me gustaría trabajar en PPC Linux también, pero no es lo más importante para mí.

Answer 1

Crear un asignador de ranurado:

Allocator se crea con muchas páginas de memoria, cada uno de igual tamaño (512k, 256k, el tamaño deberá estar sintonizado para su uso).

La primera vez que un objeto le pide a este asignador la memoria, asigna una página. La asignación de una página consiste en eliminarla de la lista gratuita (sin búsqueda, todas las páginas tienen el mismo tamaño) y establecer el tamaño de los objetos que se asignarán en esta página. Por lo general, este tamaño se calcula tomando el tamaño solicitado y redondeándolo a la potencia más cercana de 2. Las asignaciones posteriores del mismo tamaño solo requieren un poco de cálculo de puntero e incrementan el número de objetos en la página.

La fragmentación se evita porque las ranuras son todas del mismo tamaño y se pueden rellenar en asignaciones posteriores. La eficiencia se mantiene (en algunos casos mejorada) porque no hay ningún encabezado por asignación (lo que hace una gran diferencia cuando las asignaciones son pequeñas, una vez que las asignaciones se vuelven grandes, este asignador comienza a desperdiciar casi el 50% de la memoria disponible).

Ambas asignaciones y desasignaciones se pueden realizar en tiempo constante (no se realizan búsquedas en la lista gratuita de ranuras correctas). La única parte difícil de una desasignación es que normalmente no quieres un encabezado de archivo que preceda a la asignación, por lo que debes averiguar la página y el índice en la página tú mismo ... Es sábado y no he tomado mi café, así que No tengo ningún buen consejo sobre cómo hacer eso, sin embargo, es bastante fácil de descifrar a partir de la dirección desasignada.

Editar: Esta respuesta es un poco larga. Como de costumbre, boost tiene la espalda.

Answer 2

Si conoce el tamaño máximo de sus matrices, puede usar un asignador personalizado. Deberá escribir la clase de asignador usted mismo. Lo que debería hacer es asignar una gran cantidad de memoria a la vez y convertirla en una lista vinculada. Cada vez que se necesita crear una instancia de objeto, elimina la cola de la lista. Cada vez que se necesita liberar el objeto, agrega una entrada a la lista.

EDIT: he aquí una muestra de Bjarne Stroustrup de El C++ Programming Language, 3ª edición:

class Pool 
{ 
private: 
    struct Link 
    { Link * next; }; 

    struct Chunk 
    { 
    enum {size = 8*1024-16}; 

    Chunk * next; 
    char mem[size]; 
    }; 

private: 
    Chunk * chunks; 
    const unsigned int esize; 
    Link * head; 

private: 
    Pool (const Pool &) { }  // copy protection 
    void operator = (Pool &) { } // copy protection 

public: 
    // sz is the size of elements 
    Pool(unsigned int sz) 
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz), 
     head(0), chunks(0) 
    { } 

    ~Pool() 
    { 
    Chunk * n = chunks; 

    while(n) 
    { 
     Chunk * p = n; 
     n = n->next; 
     delete p; 
    } 
    } 


public: 

    // allocate one element 
    void * alloc() 
    { 
    if(head == 0) 
     grow(); 

    Link * p = head; 
    head = p->next; 

    return p; 
    } 

    // put an element back into the pool 
    void free(void * b) 
    { 
    Link * p = static_cast<Link*>(b); 
    p->next = head; //put b back as first element 
    head = p; 
    } 

private: 
    // make pool larger 
    void grow() 
    { 
    Chunk* n = new Chunk; 
    n->next = chunks; 
    chunks = n; 

    const int nelem = Chunk::size/esize; 
    char * start = n->mem; 
    char * last = &start [ (nelem - 1) * esize ]; 

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize 
     reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize); 

    reinterpret_cast<Link *>(last)->next = 0; 
    head = reinterpret_cast<Link *>(start); 
    } 
}; 

Answer 3

Si se puede predecir el tamaño del objeto asignado de antemano que probablemente será mejor ir con un trozo de memoria asignado linealmente y su propio asignador personalizado (como se sugirió @Kerido). A eso, agregaría que el método más eficiente sería poner a cero y cambiar las posiciones dentro de la asignación, y no preocuparse por reparticionar y compactar la matriz (deje espacio muerto entre las asignaciones) para que no tenga que lidiar con las actualizaciones de índice y el índice mantenimiento.

Si puede particionar sus objetos antes de tiempo (es decir, sabe que tiene elementos de tamaño no fijo, pero el grupo fácilmente) divídalos en cubos y preasigne porciones de memoria en cada cubeta y cambie los elementos en los correspondientes cangilón. Si sus objetos pueden cambiar el tamaño a lo largo de su vida y pueden ser difíciles de manejar, considere este enfoque cuidadosamente.