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

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

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

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

выделяет:

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

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

2 ищите в справочной таблице и если не найдёте

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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