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

Question

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

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

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

Answer 1

В средах программирования

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

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

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

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