c++ - sistemas - Comprensión de objetos y manejadores orientados a datos y que son fáciles de almacenar en caché

principales manejadores de base de datos

Question

using namespace std;

Considere un enfoque OOP tradicional para la gestión de entidades / objetos:

struct Entity { bool alive{true}; }

struct Manager {        
    vector<unique_ptr<Entity>> entities; // Non cache-friendly

    void update() {
        // erase-remove_if idiom: remove all !alive entities
        entities.erase(remove_if(begin(entities), end(entities),
            [](const unique_ptr<Entity>& e){ return !e->alive; }));
    }
};

struct UserObject {
    // Even if Manager::entities contents are re-ordered
    // this reference is still valid (if the entity was not deleted)
    Entity& entity;
};

Sin embargo, me gustaría probar un enfoque orientado a los datos : no asignar dinámicamente instancias de Entity , sino almacenarlas en una memoria lineal compatible con caché.

struct Manager {
    vector<Entity> entities; // Cache-friendly
    void update() { /* erase-remove_if !alive entities */ }
};

struct UserObject {
    // This reference may unexpectedly become invalid
    Entity& entity;
};

Parece agradable. Pero ... si std::vector necesita reasignar su matriz interna, todas las referencias a las entidades dejarán de ser válidas.

La solución está utilizando una clase de identificador.

struct Entity { bool alive{true}; };
struct EntityHandle { int index; };

struct Manager {
    vector<Entity> entities; // Cache-friendly      
    void update() { /* erase-remove_if !alive entities */ }
    Entity& getEntity(EntityHandle h) { return entities[h.index]; }
};

struct UserObject { EntityHandle entity; };

Si solo estoy agregando / eliminando entidades en la parte posterior del vector, parece funcionar. Puedo usar el método getEntity para recuperar la entidad que quiero.

Pero, ¿qué pasa si elimino una Entity de la mitad del vector? Todas EntityHandle instancias de EntityHandle ahora contendrán el índice incorrecto, ya que todo fue cambiado. Ejemplo:

El mango apunta al índice: 2.

La entidad A se elimina durante la actualización ()

Ahora el identificador apunta a la entidad incorrecta.

¿Cómo se trata este problema generalmente?

¿Se actualizan los índices de manejo?

¿Se sustituye la entidad muerta por un marcador de posición?

Para aclarar:

This y this son ejemplos de lo que quiero decir con diseño compatible con caché .

Además, los sistemas de componentes como Artemis afirman estar en un diseño lineal compatible con caché , y usan soluciones similares a los manejadores. ¿Cómo abordan el problema que describo en esta pregunta?

Answer 1

Hay un gran powerpoint hecho por insomnio, su solución fue algo como esto

template<typename T, int SIZE>
class ResourceManager
{
    T data[SIZE];
    int indices[SIZE];
    int back;

    ResourceManager() : back(0)
    {
        for(int i=0; i<SIZE; i++)
            indices[i] = i;
    }

    int Reserve()
    { return indices[back++]; }

    void Release(int handle)
    {
        for(int i=0; i<back; i++)
        {
            if(indices[i] == handle)
            {
                back--;
                std::swap(indices[i], indices[back]);
                return;
            }
        }
    }

    T GetData(int handle)
    { return data[handle]; }
};

Espero que este ejemplo demuestre claramente la idea.

Answer 2

Me centraré en el caso de que requiera un tamaño variable para su vector, por ejemplo, los datos a menudo se insertan y, a veces, se limpian. En este caso, el uso de datos ficticios o agujeros en su vector es casi tan "malo" como el uso de datos de pila como su primera solución.

Si a menudo recorre directamente todos los datos y usa solo algunos accesos aleatorios "UsersObject", la siguiente solución podría ser una solución. Utiliza, como lo proponen otros y usted mismo, un nivel de direccionamiento indirecto que debe actualizarse en cada paso de eliminación / actualización. Esto toma tiempo lineal y definitivamente no es un caché óptimo. Además, e incluso peor, una solución de este tipo no se puede hacer sin hilos sin bloqueos.

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <mutex>

using namespace std;

typedef __int64 EntityId;

template<class Entity>
struct Manager {        
    vector<Entity>          m_entities; // Cache-friendly
    map<EntityId, size_t>   m_id_to_idx;
    mutex                   g_pages_mutex;
public:
    Manager() :
        m_entities(),
        m_id_to_idx(),
        m_remove_counter(0),
        g_pages_mutex()
    {}
    void update()
    {
        g_pages_mutex.lock();
        m_remove_counter = 0;
        // erase-remove_if idiom: remove all !alive entities

        for (vector<Entity>::iterator i = m_entities.begin(); i <  m_entities.end(); )
        {
            Entity &e = (*i);
            if (!e.m_alive)
            { 
                m_id_to_idx.erase(m_id_to_idx.find(e.m_id)); 
                i = m_entities.erase(i);
                m_remove_counter++;
                return true;
            } 
            else
            {
                m_id_to_idx[e.m_id] -= m_remove_counter;
                i++;
            }                    
        }
        g_pages_mutex.unlock();
    }
    Entity& getEntity(EntityId h)
    { 
        g_pages_mutex.lock();
        map<EntityId, size_t>::const_iterator it = m_id_to_idx.find(h);


        if (it != m_id_to_idx.end())
        {
            Entity& et =  m_entities[(*it).second];
            g_pages_mutex.unlock();
            return et;
        }
        else
        {
            g_pages_mutex.unlock();
            throw std::exception();
        }
    }
    EntityId inserEntity(const Entity& entity) 
    {
        g_pages_mutex.lock();
        size_t idx = m_entities.size();
        m_id_to_idx[entity.m_id]  = idx;
        m_entities.push_back(entity);
        g_pages_mutex.unlock();
        return entity.m_id;
    }
};

class Entity { 
    static EntityId  s_uniqeu_entity_id;
public:
    Entity (bool alive) :  m_id (s_uniqeu_entity_id++), m_alive(alive) {}
    Entity () :  m_id (s_uniqeu_entity_id++), m_alive(true) {}
    Entity (const Entity &in) : m_id(in.m_id), m_alive(in.m_alive) {}
    EntityId  m_id;
    bool m_alive; 
};

EntityId  Entity::s_uniqeu_entity_id = 0;

struct UserObject
{ 
    UserObject(bool alive, Manager<Entity>& manager) : 
        entity(manager.inserEntity(alive)) 
    {}
    EntityId entity; 
};

int main(int argc, char* argv[])
{
    Manager<Entity> manager;
    UserObject obj1(true, manager);
    UserObject obj2(false, manager);
    UserObject obj3(true, manager);
    cout << obj1.entity << "," << obj2.entity << "," << obj3.entity;
    manager.update();
    manager.getEntity(obj1.entity);
    manager.getEntity(obj3.entity);
    try
    {
        manager.getEntity(obj2.entity);
        return -1;
    }
    catch (std::exception ex)
    {
        // obj 2 should be invalid
    }
    return 0;
}

No estoy seguro, si especificó suficientes condiciones secundarias por las que desea resolver su problema teniendo estos dos supuestos contradictorios: tenga una lista de iteración rápida y tenga una referencia estable a los elementos de esta lista. Esto me suena a dos casos de uso que deberían estar separados también en el nivel de datos (por ejemplo, copiar al leer, confirmar los cambios).

Answer 3

Para cambiar las entidades vectoriales de referencia sobre la marcha, modifique su diseño para almacenar índices en el UserObject en lugar de punteros directos. De esta manera, puede cambiar el vector de referencia, copiar los valores anteriores y todo seguirá funcionando. En cuanto al caché, los índices fuera de un solo puntero son insignificantes y en cuanto a instrucciones es lo mismo.

Para tratar con las eliminaciones, ignórelas (si sabe que hay una cantidad fija de ellas) o mantenga una lista gratuita de índices. Utilice esta lista gratuita cuando agregue elementos, y luego aumente el vector solo cuando la lista libre esté vacía.

Answer 4

Revisemos tu frase

memoria lineal compatible con caché.

¿Cuál es el requisito para ''lineal''? Si realmente tiene tal requisito, consulte las respuestas de @seano y @Mark B. Si no le importa la memoria lineal, aquí vamos.

std::map , std::set , std::list proporciona iteradores que son estables (tolerantes) para la modificación del contenedor. Es decir que en lugar de mantener la referencia puede mantener el iterador:

struct UserObject {
    // This reference may unexpectedly become invalid
    my_container_t::iterator entity;
};

Notas especiales en std::list : en alguna conferencia en http://isocpp.org/ Bjarne Stroustrup no recomendó usar la lista enlazada, pero para su caso, puede estar seguro de que la Entity dentro del Manager estará a salvo de las modificaciones, por lo que consulte Es aplicable allí.

PS Googlear rápido No he encontrado si unordered_map proporciona iteradores estables, por lo que mi lista anterior puede no estar completa.

PPS Después de la publicación, recuerdo una interesante estructura de datos - lista fragmentada. La lista enlazada de matrices lineales - para que pueda mantener los trozos lineales de tamaño fijo en el orden vinculado.

Answer 5

Si necesita índices o punteros estables, los requisitos de la estructura de datos comienzan a parecerse a los de un asignador de memoria. Los asignadores de memoria también son un tipo particular de estructura de datos pero enfrentan el requisito de que no pueden reorganizar la memoria o reasignarla, ya que esto invalidaría los punteros almacenados por el cliente. Por lo tanto, recomiendo mirar las implementaciones de los asignadores de memoria, comenzando con la lista gratuita clásica.

Lista gratis

Aquí hay una implementación de C simple que escribí para ilustrar la idea a los colegas (no se molesta con la sincronización de subprocesos):

typedef struct FreeList FreeList;

struct FreeList
{
    /// Stores a pointer to the first block in the free list.
    struct FlBlock* first_block;

    /// Stores a pointer to the first free chunk.
    struct FlNode* first_node;

    /// Stores the size of a chunk.
    int type_size;

    /// Stores the number of elements in a block.
    int block_num;
};

/// @return A free list allocator using the specified type and block size, 
/// both specified in bytes.
FreeList fl_create(int type_size, int block_size);

/// Destroys the free list allocator.
void fl_destroy(FreeList* fl);

/// @return A pointer to a newly allocated chunk.
void* fl_malloc(FreeList* fl);

/// Frees the specified chunk.
void fl_free(FreeList* fl, void* mem);

// Implementation:   
typedef struct FlNode FlNode;
typedef struct FlBlock FlBlock;
typedef long long FlAlignType;

struct FlNode
{
    // Stores a pointer to the next free chunk.
    FlNode* next;
};

struct FlBlock
{
    // Stores a pointer to the next block in the list.
    FlBlock* next;

    // Stores the memory for each chunk (variable-length struct).
    FlAlignType mem[1];
};

static void* mem_offset(void* ptr, int n)
{
    // Returns the memory address of the pointer offset by ''n'' bytes.
    char* mem = ptr;
    return mem + n;
}

FreeList fl_create(int type_size, int block_size)
{
    // Initialize the free list.
    FreeList fl;
    fl.type_size = type_size >= sizeof(FlNode) ? type_size: sizeof(FlNode);
    fl.block_num = block_size / type_size;
    fl.first_node = 0;
    fl.first_block = 0;
    if (fl.block_num == 0)
        fl.block_num = 1;
    return fl;
}

void fl_destroy(FreeList* fl)
{
    // Free each block in the list, popping a block until the stack is empty.
    while (fl->first_block)
    {
        FlBlock* block = fl->first_block;
        fl->first_block = block->next;
        free(block);
    }
    fl->first_node = 0;
}

void* fl_malloc(FreeList* fl)
{
    // Common case: just pop free element and return.
    FlNode* node = fl->first_node;
    if (node)
    {
        void* mem = node;
        fl->first_node = node->next;
        return mem;
    }
    else
    {
        // Rare case when we''re out of free elements.
        // Try to allocate a new block.
        const int block_header_size = sizeof(FlBlock) - sizeof(FlAlignType);
        const int block_size = block_header_size + fl->type_size*fl->block_num;
        FlBlock* new_block = malloc(block_size);

        if (new_block)
        {
            // If the allocation succeeded, initialize the block.
            int j = 0;
            new_block->next = fl->first_block;
            fl->first_block = new_block;

            // Push all but the first chunk in the block to the free list.
            for (j=1; j < fl->block_num; ++j)
            {
                FlNode* node = mem_offset(new_block->mem, j * fl->type_size);
                node->next = fl->first_node;
                fl->first_node = node;
            }

            // Return a pointer to the first chunk in the block.
            return new_block->mem;
        }

        // If we failed to allocate the new block, return null to indicate failure.
        return 0;
    }
}

void fl_free(FreeList* fl, void* mem)
{
    // Just push a free element to the stack.
    FlNode* node = mem;
    node->next = fl->first_node;
    fl->first_node = node;
}

Secuencia de acceso aleatorio, listas anidadas gratuitas

Con la idea de lista libre entendida, una posible solución es esta:

Este tipo de estructura de datos le dará punteros estables que no invalidan y no solo índices. Sin embargo, aumenta el costo del acceso aleatorio y el acceso secuencial si desea utilizar un iterador para él. Puede hacer acceso secuencial a la par con el vector usando algo como un método for_each .

La idea es utilizar el concepto de la lista libre anterior, excepto que cada bloque almacena una lista libre propia, y la estructura de datos externa que agrega los bloques almacena una lista libre de bloques. Un bloque solo se extrae de la pila libre cuando se llena por completo.

Brocas paralelas de ocupación

Otra es usar una matriz paralela de bits para indicar qué partes de una matriz están ocupadas / vacías. El beneficio aquí es que puede, durante la iteración secuencial, verificar si hay muchos índices ocupados a la vez (64 bits a la vez, momento en el que puede acceder a los 64 elementos contiguos en un bucle sin verificar individualmente si están ocupado). Cuando no están ocupados los 64 índices, puede usar las instrucciones de FFS para determinar rápidamente qué bits se configuran.

Puede combinar esto con la lista libre para luego usar los bits para determinar rápidamente qué índices están ocupados durante la iteración mientras tiene una rápida inserción y eliminación de tiempo constante.

De hecho, puede obtener un acceso secuencial más rápido que std::vector con una lista de índices / punteros en el lateral, ya que, nuevamente, podemos hacer cosas como verificar 64 bits a la vez para ver qué elementos se deben recorrer dentro de la estructura de datos y porque el patrón de acceso siempre será secuencial (similar a usar una lista ordenada de índices en la matriz).

Todos estos conceptos giran en torno a dejar espacios vacíos en una matriz para recuperarlos en inserciones posteriores, lo que se convierte en un requisito práctico si no desea que se invaliden los índices o los punteros a elementos que no se hayan eliminado del contenedor.

Lista de índice de enlace único

Otra solución es usar una lista de enlaces individuales que la mayoría de la gente podría considerar como una asignación de almacenamiento dinámico separada por nodo y caché que no se encuentra en el cruce, pero no es así. Solo podemos almacenar los nodos de forma contigua en una matriz y vincularlos entre sí. Un mundo de oportunidades de optimización se abre realmente si no piensa en una lista enlazada como un contenedor, sino como una manera de vincular elementos existentes almacenados en otro contenedor, como una matriz, para permitir diferentes patrones de búsqueda y recorrido. Ejemplo con todo solo almacenado en una matriz contigua con índices para vincularlos entre sí:

Con datos almacenados así:

struct Bucket
{
    struct Node
    {
         // Stores the element data.
         T some_data;

         // Points to either the next node in the bucket
         // or the next free node available if this node
         // has been removed.
         int next;
    };
    vector<Node> data;

    // Points to first node in the bucket.
    int head;

    // Points to first free node in the bucket.
    int free_head;
};

Esto no permite el acceso aleatorio y su localidad espacial se degrada si se quita del medio y se inserta con frecuencia. Pero es bastante fácil restaurarlo con una copia de post-procesamiento. Puede ser adecuado si solo necesita acceso secuencial y desea una extracción e inserción de tiempo constante. Si necesita punteros estables y no solo índices, puede utilizar la estructura anterior con la lista libre anidada.

El SLL indexado tiende a funcionar bastante bien cuando tiene muchas listas pequeñas que son muy dinámicas (eliminaciones e inserciones constantes). Otro ejemplo con partículas almacenadas de forma contigua, pero los enlaces de índice de 32 bits solo se utilizan para particionarlas en una cuadrícula para una rápida detección de colisiones mientras permiten que las partículas se muevan cada cuadro y solo tienen que cambiar un par de enteros para transferir una partícula de uno celda de cuadrícula a otra:

En este caso, puede almacenar una cuadrícula de 1000x1000 en menos de 4 megabytes; definitivamente, supera el almacenamiento de un millón de instancias de std::list o std::vector y tiene que eliminarlas e insertarlas constantemente a medida que las partículas se mueven.

Indices de ocupación

Otra solución simple si solo necesita índices estables es simplemente usar, digamos, std::vector con un std::stack<int> de índices libres para reclamar / sobrescribir en las inserciones. Eso sigue el principio de lista libre de eliminación constante, pero es un poco menos eficiente, ya que requiere memoria para almacenar la pila de índices libres. La lista gratuita hace que la pila sea gratuita.

Sin embargo, a menos que lo hagas con la mano y evites usar std::vector<T> , no puedes hacer que active el destructor del tipo de elemento que estás almacenando en la eliminación (no he estado al día con C ++, más de un programador de C en estos días, pero podría haber una manera de hacerlo bien que aún respete sus elementos destructores sin lanzar su propio equivalente de std::vector (quizás un experto en C ++ podría colaborar). Eso puede estar bien si tus tipos son tipos de POD triviales.

template <class T>
class ArrayWithHoles
{
private:
    std::vector<T> elements;
    std::stack<size_t> free_stack;

public:
    ...

    size_t insert(const T& element)
    {
        if (free_stack.empty())
        {
            elements.push_back(element);
            return elements.size() - 1;
        }
        else
        {
            const size_t index = free_stack.top();
            free_stack.pop();
            elements[index] = element;
            return index;
        }
    }

    void erase(size_t n)
    {
        free_stack.push(n);
    }
};

Algo en este sentido. Eso nos deja con un dilema, ya que no podemos decir qué elementos se han eliminado del contenedor para saltar durante la iteración. De nuevo, puede utilizar matrices de bits paralelas o también puede almacenar una lista de índices válidos en el lateral.

Si lo hace, la lista de índices válidos puede degradarse en términos de patrones de acceso a la memoria en la matriz a medida que se desordena con el tiempo. Una forma rápida de reparar es realizar una clasificación de los índices de vez en cuando, momento en el que ha restaurado el patrón de acceso secuencial.

Answer 6

Si realmente ha medido que la localidad de caché le brinda beneficios, le sugiero que utilice un método de agrupación de memoria: en el nivel más básico, si conoce un número máximo de elementos desde el principio, puede crear simplemente tres vectores, uno con objetos, uno con punteros de objeto activo y otro con punteros de objeto libre. Inicialmente, la lista libre tiene punteros a todos los objetos en el contenedor de elementos y luego los elementos se mueven a la lista activa a medida que se activan, y luego regresan a la lista libre a medida que se eliminan.

Los objetos nunca cambian de ubicación, incluso cuando los punteros se agregan / eliminan de los contenedores respectivos, por lo que sus referencias nunca se invalidan.

Answer 7

Tengo dos maneras en mi mente. La primera forma es actualizar los identificadores cuando borre la entidad del contenedor http://www.codeproject.com/Articles/328365/Understanding-and-Implementing-Observer-Pattern-in , la segunda es usar el contenedor de clave / valor como mapa / hash La tabla y su identificador deben contener clave en lugar de índice.

editar:

primer ejemplo de solución

class Manager:

class Entity { bool alive{true}; };
class EntityHandle 
{
public:
    EntityHandle(Manager *manager)
    {
        manager->subscribe(this);
        // need more code for index
    }

    ~EntityHandle(Manager *manager)
    {
        manager->unsubscribe(this);
    }

    void update(int removedIndex)
    {
        if(removedIndex < index)
        {
            --index;
        }
    }

    int index; 
};

class Manager {
    vector<Entity> entities; // Cache-friendly
    list<EntityHandle*> handles;

    bool needToRemove(const unique_ptr<Entity>& e)
    {
        bool result = !e->alive;

        if(result )
            for(auto handle: handles)
            {
                handle->update(e->index);
            }

        return result;
    }

    void update() 
    {
        entities.erase(remove_if(begin(entities), end(entities),
        needToRemove);
    }
    Entity& getEntity(EntityHandle h) { return entities[h.index]; }

    subscribe(EntityHandle *handle)
    {
        handles.push_back(handle);
    }

    unsubscribe(EntityHandle *handle)
    {
        // find and remove
    }

};

Espero que esto sea suficiente para tener la idea.