Блог

Я хочу создать хранилище данных, которое выглядит следующим образом:

1. У меня есть массив структур, которые являются своего рода интеллектуальными указателями. Каждый указатель содержит информацию о перемещении объекта в стековом массиве (хранилище, содержащее все объекты), размере объекта и количестве владельцев:

 struct ObjPtr {
    int disp;  // displacement
    int size;  // size of an object
    int count; // number of holders
}

// somewhere in code...
// Assume I can create only 1024 objects just for example.
ObjPtr* smart_pointers = (ObjPtr*)calloc(1024, sizeof(ObjPtr)); 
 

2. У меня есть массив стека, который содержит все объекты:

 // Assume 64 MB is enough
char* obj_stack = (char*)calloc(64 * 1024 * 1024, sizeof(char))
int stack_top; // displacement of the top of the obj_stack
 

Это просто простой массив байтов. Каждый объект выделяется в верхней части стека, а затем мы делаем stack_top = sizeof(allocated_type) . Если памяти недостаточно, мы сжимаем obj_stack .
Абсолютно везде в моей программе я использую индекс ObjPtr в smart_pointers массиве вместо указателей:

 // Access an object:
SomeObject* some_object = (SomeObject*)(obj_stack   pointers[objPointer_index].disp)
 

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

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