Понимание ориентированных на кеширование, ориентированных на данные объектов и ручек

Ответ 1

Там отличная powerpoint, сделанная insomniac, их решение было чем-то вроде этого

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]; }
};

Надеюсь, что этот пример явно демонстрирует идею

Ответ 2

Если вам нужны стабильные индексы или указатели, тогда ваши требования к структуре данных начинают напоминать требования к распределению памяти. Распределители памяти также являются особым типом структуры данных, но сталкиваются с тем требованием, что они не могут перемешать память или перераспределять память, поскольку это приведет к недействительности указателей, хранящихся клиентом. Поэтому я рекомендую взглянуть на реализации распределителя памяти, начиная с классического бесплатного списка.

Бесплатный список

Вот простая реализация C, которую я написал, чтобы проиллюстрировать идею коллегам (не беспокоит нитки синхронизации):

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;
}

Последовательность произвольного доступа, вложенные бесплатные списки

С понятием свободного списка понимается одно из возможных решений:

Этот тип структуры данных даст вам устойчивые указатели, которые не являются недействительными, а не только индексы. Тем не менее, это увеличивает стоимость случайного доступа, а также последовательный доступ, если вы хотите использовать для него итератор. Он может выполнять последовательный доступ по аналогии с vector, используя что-то вроде метода for_each.

Идея состоит в том, чтобы использовать концепцию бесплатного списка выше, за исключением того, что каждый блок хранит собственный собственный список, а внешняя структура данных, объединяющая блоки, хранит свободный список блоков. Блок полностью выгружается из свободного стека, когда он полностью заполняется.

Параллельные биты занятости

Другим является использование параллельного массива бит для указания того, какие части массива заняты/пусты. Преимущество здесь в том, что во время последовательной итерации вы можете проверить, занято ли сразу несколько индексов (сразу 64 бита, после чего вы можете получить доступ ко всем 64 смежным элементам цикла без индивидуальной проверки, чтобы убедиться, что они занято). Если не все 64 индекса заняты, вы можете использовать FFS, чтобы быстро определить, какие биты установлены.

Вы можете комбинировать это со свободным списком, чтобы затем использовать биты, чтобы быстро определить, какие индексы заняты во время итерации, при быстрой установке и удалении постоянной времени.

Фактически вы можете получить более быстрый последовательный доступ, чем std::vector, со списком индексов/указателей сбоку, так как снова мы можем делать такие вещи, как проверка 64-бит сразу, чтобы увидеть, какие элементы пересекаются внутри структуры данных, и поскольку шаблон доступа всегда будет последовательным (аналогично использованию отсортированного списка индексов в массиве).

Все эти понятия вращаются вокруг того, что оставляют свободные пространства в массиве для восстановления после последующих вставок, что становится практическим требованием, если вы не хотите, чтобы индексы или указатели были недействительными к элементам, которые не были удалены из контейнера.

Одиночный список индексов

Другим решением является использование односвязного списка, который большинство людей может подумать о том, что оно связано с отдельным распределением кучи на node, а кеш пропустит вслух на обход, но этого не должно быть. Мы можем просто хранить узлы смежно в массиве и связывать их вместе. Мир возможностей оптимизации фактически открывается, если вы не думаете о связанном списке как о контейнере, чтобы просто связать существующие элементы вместе, хранящиеся в другом контейнере, например массиве, чтобы разрешить разные шаблоны обхода и поиска. Пример со всем, что хранится в смежном массиве с индексами, чтобы связать их:

С данными, хранящимися так:

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;
};

Это не допускает случайный доступ, и его пространственная локальность ухудшается, если вы удаляете из середины и часто вставляете. Но достаточно легко восстановить его с помощью копии после обработки. Он может быть подходящим, если вам нужен только последовательный доступ и требуется постоянное удаление и вставка. Если вам нужны стабильные указатели, а не только индексы, вы можете использовать указанную выше структуру с вложенным свободным списком.

Индексированный SLL имеет тенденцию делать все хорошо, когда у вас много маленьких списков, которые очень динамичны (постоянные удаления и вставки). Другой пример с частицами, хранящимися последовательно, но 32-битные индексные ссылки, которые просто используются для разбиения их на сетку для быстрого обнаружения столкновений, позволяя частицам перемещать каждый отдельный кадр и только изменять пару целых чисел для переноса частицы из одной ячейка сетки в другую:

В этом случае вы можете хранить сетку 1000x1000 под 4 мегабайтами - определенно выигрывает, сохраняя миллион экземпляров std::list или std::vector, и им приходится постоянно удалять и вставлять из/в них по мере перемещения частиц.

Показатели занятости

Еще одно простое решение, если вам нужны только стабильные индексы, просто используется, скажем, std::vector с std::stack<int> бесплатных индексов для восстановления/перезаписывания при вставках. Это следует за принципом свободного списка удаления посто нного времени, но он менее эффективен, так как он требует, чтобы память хранила стек бесплатных индексов. Свободный список позволяет стеку получить бесплатно.

Однако, если вы не ругаете его и не используете только std::vector<T>, вы не можете эффективно заставить его вызвать деструктор типа элемента, который вы храните при удалении (я не поддерживал С++, больше программист на C в наши дни, но может быть способ сделать это красиво, что по-прежнему уважает ваши деструкторы элементов, не сворачивая собственный эквивалент std::vector - может быть, может быть опробован специалист по С++). Это может быть хорошо, хотя если ваши типы являются тривиальными типами POD.

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);
    }
};

Что-то в этом роде. Это оставляет нам дилемму, хотя мы не можем сказать, какие элементы были удалены из контейнера, чтобы пропустить во время итерации. Здесь вы также можете использовать параллельные битовые массивы или вы также можете просто сохранить список допустимых индексов сбоку.

Если вы это сделаете, список допустимых индексов может ухудшиться с точки зрения шаблонов доступа к памяти в массив, поскольку они со временем становятся несортированными. Быстрый способ восстановления - это преобразовать индексы времени от времени, после чего вы восстановили шаблон последовательного доступа.

Ответ 3

Если вы действительно измерили, что местонахождение кеша дает вам преимущества, тогда я бы предложил использовать подход к пулам памяти: на самом базовом уровне, если вы знаете максимальное количество элементов спереди, вы можете просто создать три вектора, один с объектами, один с активными указателями объектов и один со свободными указателями объектов. Первоначально бесплатный список имеет указатели на все объекты в контейнере элементов, а затем элементы перемещаются в активный список по мере их активации, а затем обратно в свободный список по мере их удаления.

Объекты никогда не меняют местоположение, даже когда указатели добавляются/удаляются из соответствующих контейнеров, поэтому ваши ссылки никогда не становятся недействительными.

Ответ 4

Чтобы изменить привязанные векторные объекты на лету, измените свой дизайн, чтобы хранить индексы в UserObject вместо прямых указателей. Таким образом, вы можете изменить ссылочный вектор, скопировать старые значения и затем все будет работать. Кэш-память, индексы от одного указателя незначительны, а инструкции - одинаковые.

Чтобы справиться с удалением, либо игнорируйте их (если вы знаете, что их фиксированная сумма), либо сохраняйте бесплатный список индексов. Используйте этот freelist при добавлении элементов, а затем только увеличивайте вектор, когда freelist пуст.

Ответ 5

Я сосредоточусь на том, что вам нужен переменный размер для вашего вектора, например. данные часто вставляются и иногда очищаются. В этом случае использование фиктивных данных или отверстий в вашем векторе почти так же плохо, как использование данных кучи, таких как ваше первое решение.

Если вы часто повторяете прямо по всем данным и используете только несколько случайных запросов "UsersObject", то ниже может быть решение. Он использует, как и другие, и вас самих, уровень косвенности, который необходимо обновить на каждом этапе удаления/обновления. Это занимает линейное время и, безусловно, не является оптимальным для кэшей. Кроме того, и это еще хуже, такое решение не может быть выполнено в потоковом режиме без блокировок.

#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;
}

Я не уверен, если вы указали достаточно боковых условий, почему вы хотите решить свою проблему, имея два противоречащих друг другу предположения: иметь список быстрого перехода и иметь стабильную ссылку на элементы этого списка. Это звучит для меня как два варианта использования, которые должны быть разделены также на уровне данных (например, копировать на чтение, фиксировать изменения).

Ответ 6

У меня есть два пути. Первый способ - обновить ваши дескрипторы при стирании объекта из контейнера http://www.codeproject.com/Articles/328365/Understanding-and-Implementing-Observer-Pattern-in , во-вторых, использовать контейнер key/value, такой как map/hash table, и ваш дескриптор должен содержать ключ вместо индекса

изменить:

первый пример решения

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
    }

};

Надеюсь, этого достаточно, чтобы получить идею

Ответ 7

Давайте рассмотрим вашу фразу

для хранения данных, совместимых с кэшем.

Каково требование "линейного"? Если у вас действительно есть такое требование, обратитесь к ответам @seano и @Mark B. Если вам не нужна линейная память, тогда мы идем.

std::map, std::set, std::list предоставляет итераторы, которые являются устойчивыми (толерантными) к модификации контейнера - это означает, что вместо сохранения ссылки вы можете сохранить итератор:

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

Специальные заметки на std::list - на какой-то лекции на http://isocpp.org/ Бьярне Страуструп не рекомендовал использовать связанный список, но для вашего дела вы может быть уверен, что Entity внутри Manager будет защищен от изменений - поэтому ссылка там применима.

P.S. Быстрый поиск в googling Я не нашел, если unordered_map предоставляет стабильные итераторы, поэтому мой список выше может быть неполным.

P.P.S После публикации я вспоминаю интересную структуру данных - список каналов. Связанный список линейных массивов - поэтому вы сохраняете линейные фиксированные куски в связанном порядке.