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

Question

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

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

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 (двухуровневое разделение по размерам), который имеет стоимость выделения O (1): http://www.gii.upv.es/tlsf/

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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