Лучшая эвристика для malloc

Question

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

Какая эвристика лучше всего (что приводит к наименьшей потере кучи) для выбора местоположения среди следующих?

1. Выберите наименьшее местоположение, которое больше x байтов.
2. Выберите самое большое местоположение, которое больше чем x байтов.

Моя интуиция - это самое маленькое место, которое больше чем x байтов.Я не уверен, что является лучшим на практике.

Нет, это не какой-либо заданный вопрос.Я читал это Как работают malloc () и free ()? , и это похоже на хороший вопрос для продолжения.

Answer 1

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

Однако существуют и другие способы реализации кучи, которые могут сделать этот вопрос менее актуальным (например, популярный dlmalloc от Doug Lea - где он объединяет блоки одинакового размера для повышения скорости и уменьшения общей фрагментации). .

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

Answer 2

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

Answer 3

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