Вопрос эффективного перераспределения памяти

Question

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

У меня также есть область (я назову ее«страница») в куче (выделенная, скажем, с помощью malloc (REGION_SIZE), где REGION_SIZE> = MAX_OBJECT_SIZE).
Я сохраняю место на этой странице до тех пор, пока заполненное пространство не будет равно PAGE_SIZE (или, по крайней мере, не получит> PAGE_SIZE -MAX_OBJECT_SIZE).

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

1. Использовать realloc (page, NEW_SIZE), где NEW_SIZE> PAGE_SIZE;
2. Выделить новую "страницу" (page2) и поместить новый объекттам.

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

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

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

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

Answer 1

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

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

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

ALLOCS:

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

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

2 искать в справочной таблице и, если не найден

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

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

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

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

для объектов более некоторого размера X, не храните массив, просто выделяйте новый объект.

освобождает:

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

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

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

Answer 2

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

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

Вариант 2. Он должен быть более оптимальным, как большинство современных ОС (благодаряST ++ C ++ уже хорошо оптимизированы для небольшого количества памяти.А небольшие выделения имеют меньше шансов вызвать фрагментацию памяти.

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

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

В конце вы также должны рассмотреть вариант № 3: libc.Я думаю, что malloc () в libc достаточно эффективен для многих задач.Пожалуйста, проверьте это, прежде чем тратить больше времени.Если вы не застряли в какой-то отсталой * NIX, не должно быть проблем с использованием malloc () для каждого небольшого объекта.Я использовал настраиваемое управление памятью только тогда, когда мне нужно было поместить объекты в экзотические места (например, shm или mmap).Не забывайте и о многопоточности: malloc () / realloc () / free () обычно уже оптимизированы и готовы к MT;вам придется заново реализовать оптимизацию, чтобы избежать постоянного столкновения потоков при управлении памятью.И если вы хотите иметь пулы или зоны памяти, для этого уже есть несколько библиотек.

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Я бы предложил использовать второй подход или использовать собственный распределитель (вы можете реализовать простой распределитель друзей [2] ).

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

• Пулы памяти APR
• Google TCMalloc

Answer 6

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

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

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

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