buddy allocator workshop
1.0.0
Этот репозиторий содержит несколько небольших примеров реализаций распределителей приятелей. Они предназначены для распределения физической памяти, хотя их можно использовать для других типов распределения, таких как куча. В конце концов, лучший показатель будет объединен в цветок.
Во -первых, клонировать репо. Затем, cd в него и сделайте cargo +nightly run , чтобы запустить всех демонстрационных распределителей. По умолчанию размер блока составляет 4 киб, а количество блоков составляет 100 000, так что это может занять некоторое время для примера связанных списков. Не волнуйтесь, на самом деле это ничего не выделяет - только фиктивные блоки памяти. Пропустите -h или --help , чтобы получить помощь и просмотреть использование. Вы можете отредактировать исходный код для изменения размеров Min/Max Block и т. Д. Чтобы запустить модульные тесты, запустить cargo test . К сожалению, пока нет грузовых тестов, но я довольно не особо подтверждал их на моем машине Windows.
Я протестировал алгоритмы, используя различные реализации, используя встроенную отчетность, распределяя гибибит в блоках 4KIB (с печати) на моей машине Windows. Если у вас есть другие тесты, которые нужно добавить, см. Вклад.
(MSI CX61-2QF)
| Выполнение | Время | Пропускная способность |
|---|---|---|
| Списки - векторы | 2 мин | ~ 8.33e-3 Gib/s |
| Списки - вдвойне связанные списки | 25 минут | ~ 6.66e-4 Gib/s |
| РБ деревья - векторы | ~ 0,3 с | ~ 3,33 Гиб/с |
| РБ Деревья - Одиночные связанные списки | ~ 0,5 с | ~ 2 gib/s |
| Растровое дерево | ~ 0,07 с | ~ 14.28 Gib/s |
Примечание. Пропускная способность экстраполируется с того времени, когда потребовалось для выделения 1 GIB в блоках 4KIB. Для реализаций, которые имеют сложность> o (log n) (например, реализация на основе наивных списков), это не будет точной - пропускная способность замедляется по мере распределения большего количества блоков. Это должно быть точным для тех, которые имеют сложность O (log n) или меньше.
Эта реализация содержит список на заказ блока. Это общее из -за используемых списков типов. Я решил использовать два вида списков: векторы ( Vec от std ) и вдвойне связанные списки ( LinkedList , также от std ). Связанные списки часто ценится за их предсказуемое время толкания (без перераспределения, необходимого для нажимания), в то время как векторы имеют лучшую локальность кэша, поскольку элементы выделяются в смежном блоке памяти. Я использовал дважды связанные списки, потому что они быстрее для индексации, чем однозначные списки, так как они могут итерации сзади или спереди в зависимости от того, ближе ли индекс ближе к началу или конец списка. Я решил проверить оба, чтобы увидеть, что будет работать лучше в целом.
Реализация рекурсивна. Чтобы выделить бесплатный блок заказа k , он сначала ищет любые бесплатные блоки в списке блоков заказа k . Это не хранит бесплатный список. Если никто не найден, он повторяется, пытаясь выделить блок порядка k + 1. Наконец, если ни в каком точке не было никаких свободных блоков, он сдается и паникует. Как только один из них разбивает его пополам, удалив исходный блок из списка заказов и немедленно подтолкнув половинки в список заказов. Затем он возвращает заказ и индекс первого блока в своем списке заказа. Вы можете найти этот алгоритм в find_or_split .
Быстрый, не научный эталон на моей машине Windows говорит, что потребовалось около двух минут, чтобы выделить полный гибибит (1024^3 байта). Я время от времени заметил, что Spell Second Pause's Thery, когда ему приходилось перераспределить весь вектор, чтобы выдвинуть элемент.
stdПодобный эталон говорит, что потребовалось двадцать пять минут, чтобы выделить полный гибибит. Это более двенадцать раз медленнее, чем та же реализация с векторами. Тем не менее, эта реализация не была оптимизирована для связанных списков, поэтому она немного несправедливо. В отличие от реализации с векторами, я не заметил никаких паузов, но распределение постепенно становилось медленнее и медленнее.
Мы можем сделать вывод, что, хотя вдвойне связанные списки в теории быстрее в движении, чем векторы, они все еще были в 12 раз медленнее, чем векторы. Это может быть связано с тем, что реализация была немного в пользу векторов (много индексации), или потому, что у векторов был более высокий кэш-местность и, следовательно, испытывал меньше промахов в кешах, в то время как связанные списки испытывают высокие промахи кэша, поскольку они имеют индивидуальные элементы, связанные с кучей.
Эта реализация хранит одно красное черное дерево (от intrusive_collections ) для всех блоков и бесплатный список для каждого порядка. Бесплатные списки были реализованы для STD Vec и SinglyLinkedList от intrusive_collections . Я выбрал однозначный список, так как не было бы реальной выгоды для двойного связывания - единственный метод, который выиграл бы (незначительно), - это FreeList::remove , но это всегда называется максимум во втором элементе в этом свободном списке, поэтому нет реальной точки зрения в оптимизации этого. Красное черное дерево индивидуально выделяет каждый узел, что ухудшает эффективность кэша, но в отличие от BTreeSet / BTreeMap std , его поиск- O(log n) , в то время как std использует линейный поиск, который не является O(log n) (вы можете прочитать об этом здесь). Тем не менее, деревья std не имеют индивидуального распределения узлов, поэтому локальность кеша лучше. Я решил, что, хотя это было правдой, поскольку распределитель приятелей должен иметь дело с невероятно большим количеством блоков, было более важно иметь более эффективный алгоритм поиска.
Реализация рекурсивна. Чтобы выделить бесплатный блок заказа k , он сначала ищет любые бесплатные блоки в списке бесплатных списков блоков заказа k . Если никто не найден, он повторяется, пытаясь выделить блок порядка k + 1. Наконец, если ни в каком точке не было никаких свободных блоков, он сдается и паникует. Как только он разбивает его пополам, удаляя исходный блок от дерева и вставляя половинки, подтолкнув их адреса в соответствующий свободный список. Затем он возвращает курсор, указывающий на первый блок. Вы можете найти этот алгоритм в find_or_split . На самом внешнем слое рекурсии (функция, которая фактически вызывает рекурсивную функцию find_or_split ), возвращаемый блок помечается как используется и удаляется из свободного списка.
Использование векторов в качестве свободных списков потребовалось ~ 0,3 с, чтобы выделить полный GIB. Это ~ 0,2 с быстрее, чем связанные списки в качестве версии бесплатных списков. Вероятно, это связано с векторами, имеющими лучшую местность кэша.
Использование связанных списков в качестве бесплатных списков потребовалось ~ 0,5 с для распределения полного GIB. См. Векторы как раздел бесплатные списки выше.
Эта реализация была в 400 раз быстрее, чем реализация на основе наивных списков (в лучшем случае, используя векторы в качестве бесплатных списков). Вероятно, это связано с тем, что красно-черные деревья, имеющие операции O(log n) по всем направлениям, быстрее, чем поиски, вставки и удаления векторов или связанных списков.
Эта реализация не является строго растровой картой, но является модификацией системы растрового изображения. По сути, каждый блок в дереве хранит самый большой порядок (полностью объединенный) где -то под ним. Например, дерево, которое бесплатно, с 4 заказами выглядит так:
3
2 2
1 1 1 1
0 0 0 0 0 0 0 0
Если мы распределим один блок Order 0, он выглядит так (t is t aken):
2
1 2
0 1 1 1
T 0 0 0 0 0 0 0
Он реализован как сплющенный массив, где для дерева, как
1
2 3
представление составляет 1; 2; 3 Это имеет хорошее свойство, которое мы используем индексы, начинающиеся с 1 (т.е. индексы, а не сметают), то индекс левого ребенка любого данного индекса составляет 2 * index , а правый ребенок - просто 2 * index + 1 . Родитель - floor(index / 2) . Поскольку все эти операции работают с 2S, мы можем использовать эффективное битовое смещение для их выполнения ( index << 1 , (index << 1) | 1 и index >> 1 ).
Мы можем выполнить бинарный поиск, чтобы найти блок, который свободен от желаемого порядка. Во -первых, мы проверяем, есть ли какие -либо блоки желаемого заказа бесплатно, проверяя корневой блок. Если есть, мы проверяем, достаточно ли левого ребенка бесплатно. Если это так, то мы снова проверяем, что он остался ребенок и т. Д. Если у левого ребенка блока не хватает достаточно блоков, мы просто используем его правого ребенка. Мы знаем, что у правильного ребенка должно быть достаточно свободного, или корневой блок недействителен.
Эта реализация была очень быстрой. На моем компьютере потребовалось всего ~ 0,07, чтобы выделить 1GIB. Я видел, как он работает до 0,04 с моего компьютера, хотя производительность немного колеблется. Я предполагаю, что это связано с нагрузкой процессора.
Эта реализация не имеет очень хорошей местности кэша, поскольку уровни хранятся далеко друг от друга, поэтому родительский блок может быть очень далеко от его ребенка. Тем не менее, все остальное все еще очень быстро, так что это компенсируется. Это также O (log n), но практически это настолько быстро, что это не имеет значения. Для справки: выделение 8GIB потребовалось для меня 0,6 с, но я видел, что он работает намного лучше на уровне> 150 мс на ноутбуке @gegy1000.
Если у вас есть что -нибудь, чтобы добавить (например, редактирование в ReadMe или другую реализацию или эталон), не стесняйтесь отправить запрос на привлечение! Вы также можете создать проблему. Если вы просто хотите поболтать, не стесняйтесь пинговать меня на Rust Discord (Restioson#8323).
