Понимание кеш-ориентированных, ориентированных на данные объектов и дескрипторов

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

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

Вот простая реализация 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-битных сразу, чтобы увидеть, какие элементы для перемещения внутри структуры данных, и потому что шаблон доступа всегда будет последовательным (аналогично использованию отсортировал список индексов в массив).

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

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

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

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

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-битные индексные ссылки просто используются для разделения их на сетку для быстрого обнаружения столкновений, позволяя частицам перемещаться в каждом отдельном кадре, и нужно всего лишь изменить пару целых чисел для переноса частицы из одного ячейка сетки в другую:

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

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

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

Однако, если вы не свернули его вручную и не используете std::vector<T>Вы не можете очень эффективно заставить его запускать деструктор типа элемента, который вы сохраняете при удалении (я не следил за C ++, больше программистом на C в наши дни, но мог бы быть способ сделать это хорошо, что все еще уважает ваши деструкторы элемента без скручивания вручную своего собственного эквивалента std::vector — может быть, эксперт C ++ мог бы принять участие). Это может быть хорошо, если ваши типы являются тривиальными типами 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);
}
};

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

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

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

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

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

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

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

Если вы часто выполняете итерации по всем данным и используете только несколько случайных обращений «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;
}

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

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

Кэш-дружественная линейная память.

Каково требование для «линейного»? Если у вас действительно есть такое требование, пожалуйста, обратитесь к ответам @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 будет в безопасности от модификаций — поэтому ссылка там применима.

Постскриптум Погуглил быстро я не нашел если unordered_map обеспечить стабильные итераторы, поэтому мой список выше может быть неполным.

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

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

редактировать:

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

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
}

};

Я надеюсь, что этого достаточно, чтобы понять