Редактирование: 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 ==
'''Ключевые слова:''' алгоритм, структура данных, кэш-линейка.

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

Следует отметить следующие особенности реализации:
* базовая структура данных — B+-дерево<ref name="bptree"/>;
* размер как внутренних, так и листовых узлов дерева — 256 байт; величина задаётся во время компиляции и в будущем может измениться;
* все узлы выровнены на размер кэш-линейки<ref name="hpc"/>; как правило, это 64 байта, но выравнивание может быть изменено при компиляции;
* количество заполненных ячеек в узле дерева хранится не в самом узле, а в младших битах указателя на узел — это позволяет избежать кэш-промахов и освободить место под полезные данные;
* флаг листового узла дерева также хранится в одном из младших битов указателя на узел по тем же причинам;
* структура внутреннего узла B+-дерева подобрана так, чтобы минимизировать padding как на 32-битных, так и на 64-битных системах; почти все 256 байт узла содержат полезную информацию — ключи, значения и указатели;
* API для множеств очень похож на API библиотеки Judy1<ref name="judy"/>, API для ассоциативных массивов — на JudyL<ref name="judy"/>;
* для пользователя ассоциативный массив и множество представлены указателем (пустой массив или множество — NULL), что позволяет создавать вложенные массивы и множества картежей;
* производительность libMarika в значительной степени определяется скоростью работы <math>aligned\_alloc(64,256)</math>; в GNU libc и Darwin libc эта функция работает заметно медленнее <math>malloc</math>, что может нивелировать преимущества библиотеки.

Рекомендуемые аллокаторы памяти для максимальной производительности:
* tcmalloc<ref name="tcmalloc"/>;
* jemalloc<ref name="jemalloc"/>;
* mimalloc<ref name="mimalloc"/>.

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


{{----}}
[[File:{{#setmainimage:libMarika — эффективная реализация множества и ассоциативного массива с целочисленным ключом и значением (Алексей Чеусов, OSSDEVCONF-2025)!.jpg}}|center|640px]]
{{LinksSection}}
<!-- <blockquote>[©]</blockquote> -->

<references>
<ref name="bptree">B+ tree. https://en.wikipedia.org/wiki/B+_tree</ref>
<ref name="hpc">Sergey Slotin. Algorithms for Modern Hardware. https://en.algorithmica.org/hpc/</ref>
<ref name="tcmalloc">tcmalloc — быстрый многопоточный malloc. https://github.com/google/tcmalloc</ref>
<ref name="jemalloc">jemalloc — аллокатор с упором на масштабируемость и фрагментацию. https://jemalloc.net/</ref>
<ref name="mimalloc">mimalloc — компактный высокопроизводительный аллокатор. https://github.com/microsoft/mimalloc</ref>
<ref name="judy">Doug Baskins. Judy — библиотека разреженных динамических массивов. https://judy.sourceforge.net/index.html</ref>
</references>
* libMarika — ассоциативные массивы с 4/8-байтными ключами и значениями и множества 4/8-байтных чисел https://github.com/cheusov/libMarika  

<references/>