Временная сложность выделения памяти

Question

Какова временная сложность динамического выделения памяти с использованием new, malloc и т.д.?Я очень мало знаю о том, как реализованы распределители памяти, но я предполагаю, что ответ заключается в том, что это зависит от реализации.Поэтому, пожалуйста, ответьте на некоторые из наиболее распространенных случаев / реализаций.

Редактировать:Я смутно припоминаю, что слышал, что распределение кучи в худшем случае неограниченно, но меня действительно интересует средний / типичный случай.

Answer 1

Одна из вещей, которую вы должны понимать, имея дело с O нотацией, заключается в том, что часто очень важно понимать, что n есть.Если в n связано ли что-то с чем-то, что вы можете контролировать (например:количество элементов в списке, которые вы хотите отсортировать), то имеет смысл внимательно присмотреться к нему.

В большинстве реализаций кучи ваш n это количество непрерывных блоков памяти, обрабатываемых менеджером.Это решительно не что-то, как правило, находящееся под контролем клиента.Единственный n клиент действительно имеет контроль над размером нужного ему фрагмента памяти.Часто это не имеет никакого отношения к количеству времени, затрачиваемому распределителем.Большой n может быть так же быстро выделен, как небольшой n, или это может занять гораздо больше времени, или это может даже оказаться неработоспособным.Все это могло бы измениться к тому же самому n в зависимости от того, как поступали предыдущие распределения и освобождения от других клиентов.Так что на самом деле, если вы не реализуете кучу, то правильный ответ заключается в том, что он недетерминирован.

Вот почему программисты в реальном времени стараются избегать динамического распределения (после запуска).

Answer 2

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

В настольных системах распределитель кучи, вероятно, использует смесь различных стратегий, включая кэширование недавних выделений, поисковые списки общих размеров выделений, ячейки блоков памяти с определенными характеристиками размера и т.д.попытаться сократить время выделения, но при этом сохранить управляемость фрагментацией.Смотрите Примечания к реализации malloc Дуга Ли, чтобы получить обзор различных используемых методов: http://g.oswego.edu/dl/html/malloc.html

Для более простых систем может быть использована стратегия первого соответствия или наилучшего соответствия, когда свободные блоки хранятся в связанном списке (что даст время O (N), где N - количество свободных блоков).Но более сложная система хранения, такая как дерево AVL, может быть использована для поиска свободных блоков за O (log N) времени (http://www.oocities.org/wkaras/heapmm/heapmm.html).

Система реального времени может использовать распределитель кучи, такой как TLSF (Two-Level Segregate Fit), стоимость выделения которого составляет O (1): http://www.gii.upv.es/tlsf/

Answer 3

Я бы подумал, что обычно это будет O (n), где n - количество доступных блоков памяти (поскольку вам нужно просканировать доступные блоки памяти, чтобы найти подходящий).

Сказав это, я видел оптимизации, которые могут ускорить процесс, в частности, поддерживая несколько списков доступных блоков в зависимости от их диапазонов размеров (таким образом, блоки размером менее 1 кб находятся в одном списке, блоки размером от 1 до 10 кб - в другом списке и так далее).

Однако это все еще O (n), только с меньшим n.

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

Answer 4

Просто посмотрите, как работают типичные распределители.

Распределитель bump-the-pointer работает в O(1), и это небольшой '1" на это.

Для распределителя с разделенным хранилищем выделение k байтов означает "вернуть первый блок из списка (n)" где Список(n) - это список блоков из n байт , где n >= k.IT мог бы найдите этот Список(n) пусто, так что блок из следующего списка (List(2n)) пришлось бы разделить с обоими результирующими блоками n байты, помещаемые в список(n), и этот эффект мог бы пульсируют во всех доступных размерах, что усложняет O(ns) где ns - количество доступных различных размеров, и ns = логарифм (N) где N это размер самого большого доступного размера блока, так что даже он был бы небольшим.В большинстве случаев, особенно после выделения и освобождения нескольких блоков, сложность O(1).

Answer 5

Всего два замечания:

• TLSF является O(1) в том смысле, что не имеет ни одного цикла;и управляет объемом до 2 Гб.Хотя в это действительно трудно поверить, просто проверьте код.

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