Лучше ли использовать порядок LIFO или порядок FIFO при хранении списка освобожденных блоков в динамическом распределителе памяти?

Question

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

Answer 1

Без запуска эталона наиболее вероятным выбором для достижения максимальной производительности является FIFO, то есть помещать освобожденные блоки в начало списка свободных.

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

Answer 2

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

Составьте хотя бы упорядоченный список по размерам.

Посмотрите на некоторые другие методы, если вы действительно хотите что-то быстрое, например, внедрите систему друзей .