Найти следующий доступный блок в пуле памяти
Итак, я потратил некоторое время на реализацию класса пула памяти в C++. За исключением некоторых мелких проблем на этом пути, все прошло довольно хорошо. Однако, когда я попытался протестировать его сегодня, выделив 1000 чанков, сначала используя пул памяти, а затем сравнив его с использованием new, я фактически приблизился к производительности, которая в три раза снизилась (в наносекундах) при использовании пула памяти. Мой метод размещения выглядит так:
template <class T> T* MemPool<T>::allocate()
{
Chunk<T>* tempChunk = _startChunk;
while (tempChunk->_free == false)
{
if (tempChunk->_nextChunk == NULL)
throw std::runtime_error("No available chunks");
tempChunk = tempChunk->_nextChunk;
}
tempChunk->_free = false;
return &tempChunk->object;
}
Я начинаю с первого чанка в пуле и выполняю поиск по связанному списку пула, пока не найду свободный чанк или не достигну конца пула. Теперь, чем больше пул, тем дольше это займет, так как поиск имеет O(n) сложность по времени, где n - это количество чанков в пуле.
Поэтому мне было любопытно, есть ли у кого-нибудь мысли о том, как улучшить распределение? Сначала я хотел использовать два связанных списка вместо одного, в котором один содержит свободные фрагменты, а другой - выделенные. Когда должен быть выделен новый блок, я просто взял бы первый элемент в первом упомянутом связанном списке и переместил его в выделенный связанный список. Насколько я вижу, это исключило бы необходимость выполнения какого-либо поиска при выделении ресурсов и оставило бы только освобождение, требующее поиска для поиска правильного фрагмента.
Любые мысли приветствуются, так как я впервые работаю с памятью таким образом. Спасибо!
2 ответа
Вместо использования связанного списка, созданного вручную, вероятно, было бы более эффективно использовать std::list
(особенно если вы используете его с пользовательским распределителем). Меньше подвержен ошибкам и, вероятно, лучше оптимизирован.
Использование двух списков позволит многое упростить. Нет необходимости отслеживать в самом списке, свободен ли чанк или нет - так как это будет определено тем, в каком списке находится чанк (все, что нужно, это убедиться, что чанк каким-то образом не появляется в обоих списках).
Ваша текущая реализация означает, что вам приходится обходить связанный список, как при выделении, так и при освобождении.
Если чанки имеют фиксированный размер, то распределение будет просто реализовано путем перемещения первого доступного чанка из свободного в назначенный список - поиск не требуется. Чтобы освободить блок, вам все равно нужно найти его в выделенном списке, что означает, что вам необходимо отобразить T*
к записи в списке (например, выполнить поиск), но тогда акт освобождения будет просто перемещать запись из одного списка в другой.
Если чанки имеют переменный размер, вам нужно сделать немного больше работы. Распределение потребует нахождения фрагмента, который по крайней мере запрошенного размера при распределении. Перераспределение (выделение большего фрагмента, чем необходимо) сделало бы распределение и освобождение более эффективным с точки зрения производительности, но также означало бы, что меньшее количество фрагментов может быть выделено из пула. Или же разбейте большой кусок (из свободного списка) на две части и поместите одну запись в оба списка (представляющие выделенную часть и оставленную часть нераспределенной). Если вы сделаете это, при освобождении может оказаться желательным объединить смежные куски в памяти (эффективно реализовать дефрагментацию свободной памяти в пуле).
Вам нужно будет решить, можно ли использовать пул из нескольких потоков, и использовать соответствующую синхронизацию.
Используйте фиксированное количество ячеек размера и сделайте каждый бин связанным списком.
Например, скажем, ваши лотки - это просто целые числа, кратные размеру системной страницы (обычно 4 КБ), и вы используете куски 1 МБ; тогда у вас есть 1MiB/4KiB = 256 бинов. Если свободный делает n-страничный регион доступным в чанке, добавьте его в bin n. При выделении области из n страниц пройдитесь по лоткам от n до 256 и выберите первый доступный фрагмент.
Чтобы максимизировать производительность, свяжите бины с битовой картой, затем отсканируйте от бита n-1 до бита 255, чтобы найти первый установленный бит (считайте начальные или конечные нули, используя встроенные функции компилятора, такие как __builtin_clz и _BitScanForward). Это все еще не совсем O(1) из-за количества бинов, но это довольно близко.
Если вас беспокоит нехватка памяти, вы можете добавить каждый блок только один раз для каждого бина. То есть, даже если в чанке доступно 128 одностраничных областей (максимально фрагментированных), бен 1 все равно будет ссылаться на чанк только один раз и повторно использовать его 128 раз.
Чтобы сделать это, вам нужно связать эти области вместе в каждом чанке, что означает, что каждый чанк также должен будет хранить список блоков размера, но это может быть более эффективным с точки зрения памяти, поскольку в каждом чанке имеется не более 256 допустимых смещений. тогда как список должен хранить полные указатели.
Обратите внимание, что в любом случае, если вы не хотите, чтобы свободное место внутри каждого фрагмента фрагментировалось, вам понадобится быстрый способ удаления фрагментов из блоков в вашем списке - что означает использование двусвязных списков. Очевидно, что это добавляет дополнительные накладные расходы памяти, но все же может быть предпочтительнее периодической дефрагментации свободного пространства во всем списке.