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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Как узнать, указывает ли указатель на кучу или стек?
  • Динамический двумерный массив с указателем на указатель
  • Что каждый программист должен знать о памяти?
  • Как я могу получить размер массива из указателя в C?
  • Мусорный коллектор MATLAB?
  • Объясните эту реализацию malloc из книги K & R
  • Как инициализировать память новым оператором в C ++?
  • Предупреждения памяти iPhone OS. Что означают разные уровни?
  • Проверьте, указывает ли указатель на выделенную память в куче
  • Ядро обнуляет память?
  • std :: вектор и непрерывная память многомерных массивов
  • Interesting Posts

    Как увеличить высоту строки в Excel с помощью X. Т.е. Добавить вертикальное заполнение ячейки

    Как создать активность и службу Android, которые используют отдельные процессы

    Как проверить, указан ли аргумент метода директивы в AngularJS?

    Как определить, что вызывает повторный автозапуск установщика Windows?

    XSL-FO: принудительная обертка на табличных записях

    Выбор подмножества столбцов в таблице данных.

    Почему существуют орграфы в C и C ++?

    Обновления просмотра списка Android

    Очистка и настройка домашнего приложения по умолчанию

    Принудительное gnu make для восстановления объектов, затронутых определением компилятора

    Настроить программу Windows для автоматического возобновления, если она закрыта?

    Как я могу вернуть пользовательский код состояния HTTP из метода WCF REST?

    Как скрыть процесс в диспетчере задач на C #?

    Autoincrement VersionCode с дополнительными свойствами gradle

    Как вы можете оживить значение для панели прогресса jQuery UI?

    Давайте будем гением компьютера.