LibMarika — эффективная реализация множества и ассоциативного массива с целочисленным ключом и значением (Алексей Чеусов, OSSDEVCONF-2025) — различия между версиями

;{{SpeakerInfo}}: {{Speaker|Алексей Чеусов}}
<blockquote>
Библиотека libMarika представляет собой набор C-функций, реализующих множества целых 4/8-байтных чисел и ассоциативные массивы с 4/8-байтными ключами и значениями. Элементы множества и ключи ассоциативных массивов доступны в упорядоченном виде. В этом смысле реализованная структура данных эквивалентна классическим бинарным деревьям поиска, таким как AVL-деревья или красно-чёрные деревья, однако производительность libMarika значительно выше (особенно при большом количестве элементов) за счёт более оптимального использования кэша первого уровня. В основу реализации положены B+-деревья в памяти.
</blockquote>

{{VideoSection}}

{{vimeoembed|1159717321|800|450}}
{{youtubelink|}}

{{SlidesSection}}
[[File:libMarika — эффективная реализация множества и ассоциативного массива с целочисленным ключом и значением (Алексей Чеусов, OSSDEVCONF-2025).pdf|left|page=-|300px]]

{{----}}

== Thesis ==

Версия 16:45, 29 января 2026

Докладчик

Алексей Чеусов

Библиотека libMarika представляет собой набор C-функций, реализующих множества целых 4/8-байтных чисел и ассоциативные массивы с 4/8-байтными ключами и значениями. Элементы множества и ключи ассоциативных массивов доступны в упорядоченном виде. В этом смысле реализованная структура данных эквивалентна классическим бинарным деревьям поиска, таким как AVL-деревья или красно-чёрные деревья, однако производительность libMarika значительно выше (особенно при большом количестве элементов) за счёт более оптимального использования кэша первого уровня. В основу реализации положены B+-деревья в памяти.

Видео

Презентация

Thesis

Ключевые слова: алгоритм, структура данных, кэш-линейка.

Библиотека libMarika представляет собой набор C-функций, реализующих множества целых 4/8-байтных чисел и ассоциативные массивы с 4/8-байтными ключами и значениями. Элементы множества и ключи ассоциативных массивов доступны в упорядоченном виде. В этом смысле реализованная структура данных эквивалентна классическим бинарным деревьям поиска, таким как AVL-деревья или красно-чёрные деревья, однако производительность libMarika значительно выше (особенно при большом количестве элементов) за счёт более оптимального использования кэша первого уровня. В основу реализации положены B+-деревья в памяти.

Следует отметить следующие особенности реализации:

• базовая структура данных — B+-дерево^[1];
• размер как внутренних, так и листовых узлов дерева — 256 байт; величина задаётся во время компиляции и в будущем может измениться;
• все узлы выровнены на размер кэш-линейки^[2]; как правило, это 64 байта, но выравнивание может быть изменено при компиляции;
• количество заполненных ячеек в узле дерева хранится не в самом узле, а в младших битах указателя на узел — это позволяет избежать кэш-промахов и освободить место под полезные данные;
• флаг листового узла дерева также хранится в одном из младших битов указателя на узел по тем же причинам;
• структура внутреннего узла B+-дерева подобрана так, чтобы минимизировать padding как на 32-битных, так и на 64-битных системах; почти все 256 байт узла содержат полезную информацию — ключи, значения и указатели;
• API для множеств очень похож на API библиотеки Judy1^[3], API для ассоциативных массивов — на JudyL^[3];
• для пользователя ассоциативный массив и множество представлены указателем (пустой массив или множество — NULL), что позволяет создавать вложенные массивы и множества картежей;
• производительность libMarika в значительной степени определяется скоростью работы ; в GNU libc и Darwin libc эта функция работает заметно медленнее , что может нивелировать преимущества библиотеки.

Рекомендуемые аллокаторы памяти для максимальной производительности:

• tcmalloc^[4];
• jemalloc^[5];
• mimalloc^[6].

Планы по развитию библиотеки и её приложений:

• переход на использование B*-дерева ввиду его большей эффективности;
• разработка обёрток для распространённых языков программирования: C++, Python, Lua, Ruby и др.

Примечания и ссылки

1. ↑ B+ tree. https://en.wikipedia.org/wiki/B+_tree
2. ↑ Sergey Slotin. Algorithms for Modern Hardware. https://en.algorithmica.org/hpc/
3. ↑ ^{3,0 3,1} Doug Baskins. Judy — библиотека разреженных динамических массивов. https://judy.sourceforge.net/index.html
4. ↑ tcmalloc — быстрый многопоточный malloc. https://github.com/google/tcmalloc
5. ↑ jemalloc — аллокатор с упором на масштабируемость и фрагментацию. https://jemalloc.net/
6. ↑ mimalloc — компактный высокопроизводительный аллокатор. https://github.com/microsoft/mimalloc

• libMarika — ассоциативные массивы с 4/8-байтными ключами и значениями и множества 4/8-байтных чисел https://github.com/cheusov/libMarika