Предотвращение фрагментации памяти в полиморфном контейнере - PullRequest
Новая
       11

Предотвращение фрагментации памяти в полиморфном контейнере

3 голосов
/ 21 марта 2012

Этот вопрос требует некоторого объяснения, так что если вы не пропустите пример: «

* 1002» Я недавно прочитал книгу, описывающую фрагментацию памяти (в куче) в некоторых деталях, и это заставило меня задуматьсямои собственные проекты.Например, при использовании ptr_container (из Boost) следующим образом 
ptr_array<A> arr;       // 
arr.push_back(new A()); // a1.
arr.push_back(new A()); // a2.
arr.push_back(new A()); // a3.
....

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

[arr_array][a1][a2][a3]...[aN]

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

[arr_array][xx][a2][xx][a4]...[aN][b1][b3]...[bN]

, где [xx] обозначает неиспользуемое пространство, а b1 ... bN - новые объекты.

Поэтому мне нужен контейнер, который хранит объекты (как в STL-контейнерах), но поддерживает полиморфное хранилище.Я знаю, как реализовать этот вид контейнера, но я предпочитаю использовать «экспертные» библиотеки (Boost, STL, ...).Подводя итог, мой вопрос:

Существует ли контейнер, который поддерживает (динамически распределяемые) полиморфные объекты, сохраненные в непрерывной последовательности памяти?

Например,макет памяти может выглядеть так: 

[arr_array] = [ptr_lookup_table][storage]
            = [p1, p2, ..., pn][b1, a2, b3, ..., aN]

Спасибо за ваши ответы / комментарии!

Ответы [ 3 ]

2 голосов
/ 21 марта 2012

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

Выделение памяти

Когда вы вызываете оператор new (который по умолчанию будет часто вызывать malloc за кулисами), вы напрямую не запрашиваете память у ОС, вместо этого (как правило) происходит следующее:

  • вы вызываете malloc для 76 байтов, он выглядит, если таковой имеется:
    • , если это не так, он запрашивает страницу (обычно 4 КБ) из ОС, и подготовит это
  • он затем обслуживает 76 байтов, которые вы запрашивали

Фрагментация памяти может происходить на двух уровнях:

  • Вы можете исчерпать свое виртуальное адресное пространство (не так просто с64-битные платформы)
  • У вас могут быть почти пустые страницы, которые не могут быть восстановлены и, тем не менее, не могут обслуживать ваши запросы

Как правило, поскольку malloc должен вызывать страницы по 4 КБ за раз (если вы не попросите больший кусок в этом случаеон выберет большее 4KB), вы никогда не должны исчерпывать свое адресное пространство.Это произошло на 32-битной машине (ограничено 4 ГБ) для необычно больших выделений.

С другой стороны, если ваша реализация malloc слишком наивна, вы можете получить фрагментированные блоки памяти и, таким образом, иметьгораздо больше памяти, чем то, что вы действительно используете.Обычно это то, к чему относится термин фрагментация памяти .

Типичная стратегия

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

Вместо этого хорошие реализации malloc сегодня используют пулы.

Как правило, они будут иметь пулы на размер * 1054.*:

  • 1 байт
  • 2 байта
  • 4 байта
  • ...
  • 512 байтов
  • ...
  • 4 КБ и более обрабатываются специально (напрямую)

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

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

Итак, фрагментация?

В настоящее время вы не должны наблюдать фрагментацию как таковую.

Однако вы все еще можете наблюдать дыры в памяти.Предположим, что пул обрабатывает объекты размером от 9 до 16 байтов, и вы выделяете, скажем, 4 000 000 из них.Для этого требуется не менее 16 000 страниц размером 4 КБ.Теперь предположим, что вы освободили все, кроме 16 000 из них, но коварно, так что один объект все еще живет для каждой страницы.Страницы не могут быть восстановлены ОС, так как вы все еще используете их, однако, поскольку вы используете только 4 байта из 4 КБ, пространство довольно потрачено (пока).

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

Волшебный контейнер

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

TL; DR

Не беспокойтесь о фрагментации.

Примечание:«Эксперты» могут захотеть написать собственный механизм распределения пула, я хотел бы напомнить им, чтобы они не забывали о выравнивании

0 голосов
/ 21 марта 2012

Фрагментация происходит , а не из-за использования повышающего контейнера. Это произойдет, когда вы часто выделяете и освобождаете объекты разных размеров с new и delete. ptr_array просто хранит указатели на эти выделенные объекты и, вероятно, не будет заметно способствовать фрагментации.

Если вы хотите противостоять фрагментации памяти, вы можете перегрузить свои объекты operator new и внедрить собственную систему управления памятью. Я предлагаю вам прочитать темы пулы памяти и свободные списки .

0 голосов
/ 21 марта 2012

(Изменить: извините, неправильно прочитал ваш вопрос; предыдущий ответ удален.)

Вы можете использовать любой пул памяти для своих объектов. Обычно вы группируете объекты одного (или аналогичного) размера в одном пуле. Поскольку вам обычно приходится вызывать специальную функцию delete в пуле, я предлагаю вам использовать shared_ptr с пользовательским средством удаления. Затем вы можете использовать это shared_ptr с любым стандартным контейнером, который вам нравится.

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

#include <boost/pool.hpp>
#include <memory>

class A;
class B; // B inherits from A

int main() {
  // could be global
  boost::object_pool<A> a_pool;
  boost::object_pool<B> b_pool;

  std::vector<std::shared_ptr<A>> v;

  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));
  v.push_back(std::shared_ptr<A>(a_pool.construct(), [&](A*p) { a_pool.free(p); }));

  v[2] = std::shared_ptr<B>(b_pool.construct(), [&](B*p) { b_pool.free(p); });

  return 0;
}

Это будет работать даже в том случае, если B намного больше A. Это также не зависит от автоматического освобождения пула, что, на мой взгляд, опасно. Структура памяти не плотная, потому что пул всегда будет перераспределяться, но у него не будет фрагментации, и это то, что вам нужно, если я понял ваш вопрос.

...