LibMarika — эффективная реализация множества и ассоциативного массива с целочисленным ключом и значением (Алексей Чеусов, OSSDEVCONF-2025)
Материал из 0x1.tv
- Докладчик
- Алексей Чеусов
Библиотека 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 эта функция работает заметно медленнее , что может нивелировать преимущества библиотеки.
Рекомендуемые аллокаторы памяти для максимальной производительности:
Планы по развитию библиотеки и её приложений:
- переход на использование B*-дерева ввиду его большей эффективности;
- разработка обёрток для распространённых языков программирования: C++, Python, Lua, Ruby и др.
!.jpg)
Примечания и ссылки[править вики-текст]
- ↑ B+ tree. https://en.wikipedia.org/wiki/B+_tree
- ↑ Sergey Slotin. Algorithms for Modern Hardware. https://en.algorithmica.org/hpc/
- ↑ 3,0 3,1 Doug Baskins. Judy — библиотека разреженных динамических массивов. https://judy.sourceforge.net/index.html
- ↑ tcmalloc — быстрый многопоточный malloc. https://github.com/google/tcmalloc
- ↑ jemalloc — аллокатор с упором на масштабируемость и фрагментацию. https://jemalloc.net/
- ↑ mimalloc — компактный высокопроизводительный аллокатор. https://github.com/microsoft/mimalloc
- libMarika — ассоциативные массивы с 4/8-байтными ключами и значениями и множества 4/8-байтных чисел https://github.com/cheusov/libMarika