(C) какие политики кучи чаще всего используются?

Question

Я слышал, что "лучше подходит" довольно часто используется, но я, кажется, не много читал об этом в Интернете. Что наиболее часто используется / считается наиболее эффективной политикой, используемой распределителями кучи.

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

Редактировать: Меня также особенно интересует сравнение политик кучи "лучшей подгонки" и стратегии Дуга Леа ( http://gee.cs.oswego.edu/dl/html/malloc.html). Дуг использует тип наилучшего соответствия, но его подход использует индексные корзины, тогда как лучший подход использует декартово дерево.

Answer 1

Среды программирования C используют реализацию malloc, предоставляемую стандартной библиотекой C, которая поставляется вместе с операционной системой. Концепции в распределителе памяти Дуга Ли (называемом dlmalloc) наиболее широко используются в большинстве распределителей памяти в той или иной форме в системах UNIX. В dlmalloc для размещения объектов используются ячейки разных размеров - для размещения объекта используется ячейка, ближайшая к размеру объекта.

FreeBSD использует новый многопоточный распределитель памяти, называемый jemalloc, предназначенный для одновременной и поточно- ориентированной защиты, который обеспечивает хорошие характеристики производительности при использовании в современных многоядерных системах. Сравнение старого malloc и нового многопоточного можно найти здесь. Несмотря на то, что он многопоточный, он по-прежнему использует концепции блоков разных размеров для размещения объектов в соответствии с их размером (блоки (ы), наиболее близкие к размеру объекта, используются для выделения объекта).

Внутри ядер UNIX наиболее популярным распределителем памяти является распределитель slab, который был представлен Sun Microsystems. Распределитель slab использует большие куски памяти, называемые slabs. Эти плиты делятся между тайниками объектов (или пулов) разных размеров. Каждый объект выделяется из кэша, который содержит объекты, наиболее близкие к его размеру.

Как вы могли заметить, вышеприведенные кэши bin / chunks / slab - это просто формы алгоритма наилучшего соответствия. Таким образом, вы можете легко предположить, что алгоритм "наилучшего соответствия" является одним из наиболее широко используемых алгоритмов malloc (хотя распределители памяти отличаются другими важными способами).