Эффективная память Reallocation Вопрос

Question

Допустим, у меня есть программа (например, C ++), которая выделяет несколько объектов, никогда не больше, чем данный размер (давайте назовем его max_object_size).

У меня также есть регион (я назову его «страницу») на куче (выделенном, скажем, malloc (Region_size), где регион_size> = max_object_size).
Я держу резервное пространство на этой странице до тех пор, пока заполненное пространство не равно Page_size (или, по крайней мере, получает> Page_size - max_object_size).

Теперь я хочу выделить больше памяти. Очевидно, что моя предыдущая «страница» не будет достаточно. Поэтому у меня есть как минимум два варианта:

1. Используйте RealLoc (Page, New_size), где New_size> Page_Size;
2. Выделите новую «страницу» (стр .2) и поставьте там новый объект.

Если я хотел иметь функцию пользовательской выделения, то:

1. Используя первый метод, я бы увидел, сколько я заполнил, а затем поставил свой новый объект там (и добавить размер объекта в мою заполненную переменную памяти).
2. Используя второй метод, у меня будет список (вектор? Массив?) Страниц, затем ищите текущую страницу, а затем использовать метод, аналогичный 1 на выбранной странице.

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

Итак, мой вопрос: Какой самый эффективный способ решить эту проблему? Это вариант 1, вариант 2 или некоторый другой вариант, который я здесь не рассматривал? Требуется ли небольшой ориентир / достаточно, чтобы сделать выводы для реальных ситуаций?Я понимаю, что разные операции могут выполнять по-разному, но ищу общую метрику.

Answer 1

В моем опыте вариант 2 гораздо проще работать с минимальными накладными расходами. Realloc. не Гарантия Это увеличит размер существующей памяти. И на практике это почти никогда не делает. Если вы используете его, вам нужно будет вернуться и перенаправить все старые предметы. Это потребовало бы, чтобы вы помнили, где каждый объект выделен ... это может быть тонна над накладными расходами.

Но трудно квалифицировать «наиболее эффективным», не зная, какие метрики вы используете.

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

allocs:

Для каждого выделения определяют размер объекта, выделенного.

1 Посмотрите список ссылок на освобождения для объектов этого размера, чтобы увидеть, если бы что-то было освобождено, если бы воспользоваться первым бесплатным

2 Ищите в посмотрите на стол и если не найден

2.1 Выделите массив N объектов размера.

3 Верните следующий свободный объект нужного размера.

3.1 Если массив заполнен, добавьте новую страницу.

N Объекты могут быть программистскими онлайн. Если вы знаете, у вас есть миллион 16 байтовных объектов, которые вы можете быть немного выше.

Для объектов над некоторым размером X не поддерживайте массив просто выделить новый объект.

Frees:

Определите размер объекта, добавьте его в список ссылок о Frees.

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

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

Answer 2

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

Если это действительно действует как массив,malloc--очередь другой блок дает вам еще один кусок памяти, который вы должны получить доступ через другой указатель (в вашем случае page2). Таким образом, он больше не на смежном блоке, и вы не можете использовать два блока как часть одного массива.

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

Итак, если вы используете это как массив, realloc в основном лучший вариант. В противном случае нет ничего плохого в malloc. Отказ На самом деле, вы можете использовать malloc Для каждого объекта вы создаете, а не на необходимость отслеживания блоков памяти Micro-Manage.

Answer 3

Вы не дали никаких деталей на какой платформе вы экспериментируете. Есть некоторые различия в производительности для realloc между Linux а также Windows, Например.

В зависимости от ситуации, realloc возможно, чтобы выделить новый Блок памяти, если он не может расти Текущий и Скопируйте старую память на новый, который дорогоОтказ Если вам это не нужно непременно Блок памяти вы должны избегать использования realloc.

Моя последовательность будет использовать второй подход или использовать пользовательский распределитель (вы могли бы реализовать простой Бадди Аллекатор [2]).

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

• Апр Память Пула
• Google TCMalloc

Answer 4

В худшем случае вариант 1 может привести к «движению» исходной памяти, то есть дополнительный предел. Если память не перемещается, в любом случае, «Extra» размер инициализируется, что тоже другая работа. Так realloc Было бы «побеждено» методом MALLOC, но сказать, насколько вы должны делать тесты (и я думаю, что есть предвзятость к тому, как выполняется система, когда выполняются запросы на память).

В зависимости от того, сколько раз вы ожидаете, что realloc / malloc должен быть выполнен, это может быть полезная идея или невероятно. Я бы все равно использовал Malloc.

Свободная стратегия зависит от реализации. Чтобы освободить все страницы в целом, этого достаточно, чтобы «пройти» их; Вместо массива я бы использовал связанные «страницы»: добавить sizeof (void *) на размер "страницы", и вы можете использовать дополнительные байты для хранения указателя на следующую страницу.

Если вы должны освободить один объект, расположенный в любом месте одной из страниц, он становится немного сложнее. Моя идея состоит в том, чтобы сохранить список нерешительных бесплатных «блок» / «слота» (подходит для удержания любого объекта). Когда запрашивается новый «блок», сначала вы поплушите значение из этого списка; Если он пуст, то вы получите следующий «слот» в последней на странице использования, и в конечном итоге появляется новая страница. Удаление объекта означает просто для установки пустого адреса слота в стеке / список (все, что вы предпочитаете использовать).

Answer 5

В Linux (и, вероятно, другие системы POSIX) существует третья возможность, то есть использование памяти спущенной области с shm_open. Отказ Такой регион инициализируется нулями, как только вы доступаете в него, но страницы AFAIK, которые вы никогда не получаете доступа к без расходов, если это не просто диапазон адресов в виртуальной памяти, который вы зарезервироваете. Таким образом, вы могли бы просто зарезервировать большой кусок памяти в начале (больше, чем вы когда-либо понадобились) вашего исполнения, а затем постепенно заполняют его с самого начала.

Answer 6

Какой самый эффективный способ решить эту проблему? Это вариант 1, вариант 2 или некоторый другой вариант, который я здесь не рассматривал? Требуется ли небольшой ориентир / достаточно, чтобы сделать выводы для реальных ситуаций?

Вариант 1. Для этого необходимо эффективно, New_size должен зависеть от старого размера нелинейно. В противном случае вы рискуете запустить o (n ^ 2) производительность Realloc () из-за избыточного копирования. Я вообще делаю new_size = old_size + old_size/4 (увеличение на 25% процентов) как теоретически лучшее new_size = old_size*2 может в худшем случае резервировать слишком много неиспользованной памяти.

Вариант 2. Это должно быть более оптимально, так как большинство современных OSS (благодаря STL C ++ STL) уже хорошо оптимизированы для наводнения малых распределений памяти. И небольшие ассигнования имеют меньший шанс вызвать фрагментацию памяти.

В конце концов все зависит, как часто вы выделяете новые объекты и как вы обрабатываете освобождение. Если вы распределите много с # 1, у вас будет немного избыточное копирование при расширении, но освобождение мертв, так как все объекты находятся на одной странице. Если вам нужно будет освободить / повторно использовать объекты, с # 2 вы будете проводить время прогуляться по списку страниц.

Из моего опыта № 2 лучше, поскольку перемещение вокруг больших блоков памяти может увеличить скорость фрагментации кучи. № 2 также позволяет использовать указатели, поскольку объекты не изменяют их местоположение в память (хотя для некоторых приложений я предпочитаю использовать пары POUNER_ID / INDEX вместо сырого указателей). Если прогулка по страницам становится проблемой позже, она может быть слишком оптимизирована.

В конце концов вы также должны рассмотреть вариант № 3: libc. Я думаю, что Malloc () Libc () достаточно эффективно для многих многочисленных задач. Пожалуйста, проверьте его, прежде чем инвестировать больше вашего времени. Если вы не застряли на некотором обратной стороне * NIX, не должно быть проблем с использованием malloc () для каждого маленького объекта. Я использовал пользовательские управлению памятью только тогда, когда мне нужно было поставить объекты в экзотических местах (например, SHM или MMAP). Имейте в виду многопоточенность тоже: MALLOC () / REALLOC () / Free () Как правило, уже оптимизированы и готовятся MT; Вы должны были бы переоценить оптимизацию, чтобы избежать постоянно столкновения потоков по управлению памятью. И если вы хотите иметь пулы или зоны памяти, уже есть куча библиотек для этого тоже.