Выравнивание указателей после выравнивания памяти

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

Я выделяю память из своего пула, возвращая void* в пространство в памяти, давайте предположим, что размер моего пула соответствует размеру 2*sizeof(Data).

Data* poolTest = new(pool->GetMemory(sizeof(Data))) Data(5, 5, 5);

Таким образом, пул не имеет ссылки на указатель poolTest.

Итак, теперь, если я сделаю это:

pool->Free(poolTest);
Data* poolTest2 = new(pool->GetMemory(sizeof(Data))) Data(4, 5, 5);
Data* poolTest3 = new(pool->GetMemory(sizeof(Data))) Data(3, 5, 5);

Создание poolTest3 вызывает перераспределение памяти, и теперь poolTest2 указывает на тот же адрес, что и poolTest3, а poolTest1 указывает на адрес, на который должен указывать poolTest2.

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


c++ memory-management pointers memory-alignment memory-pool
person Calum McManus    schedule 08.11.2018    source источник
comment
Зачем перераспределять память, а не просто заставлять механизм выделения напрямую возвращать освобожденную память? Ручное сжатие памяти при каждом выделении памяти после освобождения приведет к снижению производительности (и, как вы заметили, делает недействительными существующие указатели, если только вы не приложите немало усилий, чтобы исправить их или заставить их работать через дополнительный слой косвенности).   -  person ShadowRanger    schedule 08.11.2018
comment
Это максимальное использование доступного пространства. Можно передать любой тип данных, поэтому вы можете передать структуру, которая занимает 2,5 сегмента. Поэтому, если я запрашиваю некоторые данные, которым требуется больше, чем доступные сегменты, я перестраиваю их, чтобы сделать как минимум 3 выровненных сегмента (если они доступны), я не перестраиваю каждый раз, когда выделяю. Если я этого не сделаю, у меня могут остаться целые сегменты, которые будут потрачены впустую, поскольку я смогу их использовать.   -  person Calum McManus    schedule 08.11.2018
comment
Кроме того, я перемещаю данные с помощью memmove на char*, который составляет всего O (n) (n — количество сегментов после удаленных сегментов), поэтому на самом деле это довольно эффективно, и его не нужно будет вызывать так часто.   -  person Calum McManus    schedule 08.11.2018
comment
Типичные распределители решают проблему потерянных фрагментов, просто откладывая их использование до тех пор, пока не появится выделение, достаточно малое для его использования (и если только что освобожденный блок находится рядом с другим освобожденным блоком, присоединяясь к ним). O(n) работа, где n - размер любого сегмента памяти разумного размера, на самом деле является довольно высокой стоимостью; обход свободного списка составляет всего O(n) по количеству блоков в свободном списке (и на практике вам редко приходится проходить очень далеко), где memmove составляет O(n) с точки зрения размера сегмента (и средний случай включает перемещение половины ваших данных).   -  person ShadowRanger    schedule 08.11.2018
comment
Теперь я вижу, что перевыравнивание происходит только в том случае, если ваша куча фиксированного размера на самом деле недостаточно памяти, поэтому, если у вас есть свободный список, и вы на самом деле сначала повторно используете память, и только перевыравниваете, если фрагментация сделал всю оставшуюся память непригодной для использования, возможно, вы не так часто перенастраиваете, как я думаю. Но с этим все еще будет трудно правильно обращаться; пока разрешены необработанные неуправляемые указатели, практически невозможно дефрагментировать кучу. Вам нужна гораздо более сложная система управления памятью, чтобы позволить это.   -  person ShadowRanger    schedule 08.11.2018
comment
Мысль, которую я попробую завтра, заключается в том, можно ли хранить ссылки на указатели void в массиве, а затем уменьшать их, когда мне нужно, но я не знаю, возможно ли это и будет ли это работать.   -  person Calum McManus    schedule 08.11.2018

Ответы (1)


arrow_upward
2
arrow_downward

Перефразируя ваш вопрос:

Я хочу перемещать данные в памяти, чтобы освободить место для новых выделений. Как сделать так, чтобы существующие указатели по-прежнему указывали на нужные места?

Вы не можете, если только вы не отслеживаете все указатели, скажем, с помощью массива и вместо доступа к своим данным следующим образом:

*direct_ptr

теперь вам нужно сделать это:

*ptr_map[indirect_ptr]

Каждый раз, когда вы что-то перемещаете, вам нужно соответствующим образом модифицировать ptr_map.

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

Это может сэкономить немного места, но совершенно неэффективно для компьютера и грязно для программиста.

Если вы хотите самостоятельно управлять памятью, обязательно ознакомьтесь с:

https://en.wikipedia.org/wiki/Buddy_memory_allocation

https://en.wikipedia.org/wiki/Slab_allocation

И хороший обзор существующих техник:

http://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf

person Thinking Torus    schedule 08.11.2018
comment
разрушитель LMAX также может быть альтернативой. У них есть много кода, чтобы показать, почему он работает. . - person Ted Lyngmo; 08.11.2018