Проектирование и кодирование нефрагментирующего статического пула памяти
Я слышал термин раньше, и я хотел бы знать, как разработать и кодировать один.
Должен ли я использовать распределитель STL, если он доступен?
Как это можно сделать на устройствах без ОС?
Каковы компромиссы между его использованием и использованием обычного компилятора, реализованного malloc/new?
2 ответа
Попробую описать то, что по сути является пулом памяти - я просто набираю это из головы, уже давно, как я его реализовал, если что-то явно глупое, это всего лишь предложение!:)
1. Чтобы уменьшить фрагментацию, необходимо создать пул памяти, соответствующий типу объекта, который вы выделяете в нем. По сути, вы затем ограничиваете размер каждого выделения до размера интересующего вас объекта. Вы можете реализовать шаблонный класс, который имеет список динамически распределенных блоков (причина в том, что вы можете увеличить объем пространства имеется в наличии). Каждый динамически выделенный блок будет по существу массивом T.
Тогда у вас будет "свободный" список, представляющий собой односвязный список, в котором заголовок указывает на следующий доступный блок. Распределение тогда просто возвращает голову. Вы можете наложить связанный список в самом блоке, то есть каждый "блок" (который представляет выровненный размер T), по сути, будет объединением T и узла в связанном списке, когда он выделен, это T, когда освобожден, узел в списке. Есть очевидные опасности! В качестве альтернативы, вы можете выделить отдельный (и защищенный блок, который добавляет дополнительные издержки) для хранения массива адресов в блоке.
Выделение является тривиальным, перебирает список блоков и выделяет из первого доступного, освобождение также тривиально, дополнительная проверка, которую вы должны сделать, - найти блок, из которого это выделено, и затем обновить указатель заголовка. (обратите внимание, что вам нужно использовать либо новое место размещения, либо переопределить оператор new/delete в T - есть способы обойти это, Google - ваш друг)
Я полагаю, что "статический" подразумевает пул одноэлементной памяти для всех объектов типа T. Недостатком является то, что для каждого T необходимо иметь отдельный пул памяти. Вы можете быть умным и иметь один объект, который управляет пулами разного размера (например, используя массив указателей для объединения объектов, где индекс - это размер объекта).
Весь смысл предыдущего параграфа состоит в том, чтобы точно указать, насколько это сложно, и, как говорит RC выше, убедитесь, что вам это нужно, прежде чем делать это - так как это может вызвать больше боли, чем может быть необходимо!
2. Если распределитель STL отвечает вашим потребностям, используйте его, он разработан некоторыми очень умными людьми, которые знают, что они делают - однако это для общего случая, и если вы знаете, как распределяются ваши объекты, вы могли бы заставить вышеуказанное выполнить Быстрее.
3. Вы должны иметь возможность распределять память каким-либо образом (аппаратная поддержка или какой-то HAL - что угодно) - иначе я не уверен, как ваша программа будет работать?
4. Обычный malloc/new делает намного больше вещей под прикрытием (google - твой друг, мой ответ - уже эссе!). Простой распределитель, который я описал выше, не является повторным, конечно, вы можете обернуть его мьютекс, чтобы обеспечить немного прикрытия, и даже тогда, я бы рискнул, что простой распределитель будет работать на порядки быстрее, чем обычный malloc / free.
Но если вы находитесь на этой стадии оптимизации - возможно, вы исчерпали возможность оптимизации ваших алгоритмов и использования структуры данных?
Я бы посоветовал вам знать, что вам нужен не фрагментирующий распределитель памяти, прежде чем вы приложите много усилий для написания своего собственного. Достаточно того, что предоставлено библиотекой std.
Если вам это нужно, общая идея уменьшения фрагментации состоит в том, чтобы сразу захватывать большие блоки памяти и выделять их из пула, а не просить ОС предоставлять вам кучу памяти спорадически и в сильно меняющихся местах в куче и чередовать со многими другими объекты с различными размерами. Поскольку автор специализированного распределителя памяти имеет больше знаний о размере объектов, выделенных из пула, и о том, как эти распределения происходят, распределитель может использовать память более эффективно, чем распределитель общего назначения, такой как тот, который предоставляется STL.
Вы можете взглянуть на распределители памяти, такие как Hoard, которые, хотя и уменьшают фрагментацию памяти, также могут повысить производительность, предоставляя кучи для конкретных потоков, которые уменьшают конфликты. Это может помочь вашему приложению масштабироваться более линейно, особенно на многоядерных платформах.
Больше информации о многопоточных распределителях можно найти здесь.