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

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Просто проверить, насколько типичны распределители работу.

Буферных-The-указатель Распределитель работает в O (1), и это небольшое '' в этом.

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

Answer 5

Только два замечания:

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

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