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

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

{{VideoSection}}

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

{{----}}

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



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

* производительность 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-байтных чисел =

'''Чеусов Алексей'''  
Кутаиси  
независимый разработчик  

Проект: libMarika  
https://github.com/cheusov/libMarika  

<references/>

[[Категория:OSSDEVCONF-2025]]
[[Категория:Open-source projects]]
[[Категория:Draft]]