Почему круглые связанные списки используются в распределителях памяти вместо дерева?

Question

Почему распределители памяти используют циклически связанный список для хранения распределенных / свободных адресов вместо сбалансированного дерева?Обход связанного списка потребует O (n) порядка сложности, в то время как сбалансированное дерево может быть пройдено за O (logn), верно?В чем преимущество / обоснование этого?

Answer 1

Предпосылка («распределители памяти используют циклически связанный список для хранения выделенных / свободных адресов») не всегда верны.Это может быть верно для некоторых распределителей, но это не так в целом.

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

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

Итак, у вас будет время доступа O (1) (потому что вы или компилятор знаете адрес памяти блока памяти).Слияние соседних свободных блоков также просто.Если необходимо запустить какой-либо алгоритм де-фрагментации или сжатия, это можно сделать с помощью структуры, похожей на связанный список.Найти свободный блок достаточного размера можно также с помощью структуры, похожей на связанный список (хотя иногда второй встроенный связанный список используется специально для свободных блоков, чтобы минимизировать накладные расходы на функции выделения).

OfКонечно, это только один из возможных подходов к проблеме.Но это говорит о том, что использование связанного списка не обязательно является худшим выбором, чем другая структура данных.

Answer 2

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

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

Тем не менее, если исходить из предположения, что ваш вопрос точен:

Сложность наихудшего случая наиболее актуальна для очень больших обходов. Большинство распределителей были бы спроектированы таким образом, чтобы необходимый объем обхода был, как правило, достаточно мал, настолько мал, что дополнительные накладные расходы, необходимые для поддержания сбалансированного дерева, замедляют обход в среднем случае. Кроме того, инженеры предпочитают самое простое решение, за исключением тех случаев, когда более сложные решения, очевидно, лучше: списки с круговой связью почти просты.

Answer 3

Обход связанного списка потребует O (n) порядка сложности

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

тогда как сбалансированное дерево может быть пройдено в O (logn), верно?

Мы могли бы найти определенный элемент в O (logn), но мы не можем "пройти" по дереву за это время, потому что по определению "обход" структуры данных означает посещение каждого узла, и есть O ( п) узлы. И мы можем «найти определенный элемент в O (logn) только в том случае, если у дерева есть соответствующее свойство дерева поиска. Какой узел нам снова нужен? Это позволит нам эффективно найти, например, наименьшее выделение, которое достаточно велико но в любом случае это не обязательно то, что мы хотим вернуть (поскольку эта политика приводит к созданию множества крошечных кусков, которые могут или не могут быть пригодны для любого будущего распределения и которые раздувают структуру). .