Работа с фрагментацией в пуле памяти?

Я хотел добавить свои 2 цента только потому, что никто другой не указал, что из вашего описания это звучит так, как будто вы реализуете стандартный распределитель кучи (то есть то, что все мы уже используем каждый раз, когда мы вызываем malloc() или оператор new).

Куча - это именно такой объект, который обращается к диспетчеру виртуальной памяти и запрашивает большой кусок памяти (то, что вы называете "пулом"). Затем у него есть всевозможные различные алгоритмы для работы с наиболее эффективным способом выделения фрагментов разного размера и их освобождения. Кроме того, многие люди модифицировали и оптимизировали эти алгоритмы на протяжении многих лет. Долгое время Windows поставлялась с опцией, называемой кучей с низкой фрагментацией (LFH), которую вам приходилось включать вручную. Начиная с Vista, LFH используется для всех куч по умолчанию.

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

При выделении памяти единственный раз, когда вы можете повысить производительность, не просто используя кучу, — это отказаться от какого-либо другого аспекта (накладные расходы на выделение, время жизни выделения ....), который не важен для вашего конкретного приложения.

Например, в нашем приложении требовалось много выделений размером менее 1 КБ, но эти выделения использовались только в течение очень коротких периодов времени (миллисекунд). Чтобы оптимизировать приложение, я использовал библиотеку Boost Pool, но расширил ее так, что мой «распределитель» фактически содержал набор объектов boost pool, каждый из которых отвечал за выделение одного определенного размера от 16 до 1024 байт (с шагом 4). Это обеспечило почти свободное (сложность O (1)) выделение/свободное от этих объектов, но загвоздка в том, что а) использование памяти всегда велико и никогда не снижается, даже если у нас нет ни одного выделенного объекта, б) Boost Pool никогда освобождает память, которую он использует (по крайней мере, в том режиме, в котором мы его используем), поэтому мы используем это только для объектов, которые не задерживаются очень долго.

Итак, от каких аспектов нормального распределения памяти вы готовы отказаться в своем приложении?

В зависимости от системы есть несколько способов сделать это.

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

Другой способ - передать указатели на указатели ваших данных (например: int **). Затем вы можете переупорядочить память под программой (я надеюсь, что это будет безопасно для потоков) и сжать выделения, чтобы вы могли выделять новые блоки и по-прежнему сохранять данные из старых блоков (хотя, как только система переходит в это состояние, это становится тяжелым накладным, но редко должно быть сделано).

Существуют также способы «объединения» памяти, чтобы у вас были смежные страницы, например, одна страница выделялась только для выделений 512 и меньше, другая — для 1024 и меньше и т. д. Это упрощает принятие решений о том, какую ячейку использовать. и в худшем случае вы отделяетесь от следующей по величине корзины или объединяете из нижней корзины, что снижает вероятность фрагментации на нескольких страницах.

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

Было бы полезно знать более точно, что вы на самом деле пытаетесь сделать, потому что есть много способов справиться с этим.
Но первый вопрос: происходит ли это на самом деле или это теоретическая проблема?

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

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

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