Загрузка xenium - Загрузка исходного кода xenium

xenium

С/С++

v0.0.2: Merge pull request #19 from rbalint

Скачать

ксений

xenium — это библиотека только заголовков, которая предоставляет набор параллельных структур данных и алгоритмов освобождения памяти. Структуры данных параметризуются так, чтобы их можно было использовать с различными схемами восстановления (аналогично тому, как STL позволяет настраивать распределители).

только заголовок
настраиваемый
код инициализации не требуется
поддерживает динамическое количество потоков (без фиксированного времени компиляции)

В документации содержится более подробная информация.

Этот проект основан на моей предыдущей работе https://github.com/mpoeter/emr.

Пример использования

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

Структуры данных

На данный момент количество предоставленных структур данных довольно мало, поскольку до сих пор основное внимание уделялось схемам восстановления. Однако в ближайшем будущем планируется добавить еще несколько структур данных.

michael_scott_queue — неограниченная очередь с несколькими производителями и несколькими потребителями без блокировок, предложенная Майклом и Скоттом [MS96].
ramalhete_queue — быстрая неограниченная очередь без блокировок с несколькими производителями и несколькими потребителями, предложенная Ramalhete [Ram16].
vyukov_bounded_queue — ограниченная очередь FIFO с несколькими производителями и потребителями, основанная на версии, предложенной Вьюковым [Vyu10].
kirsch_kfifo_queue — неограниченная очередь k-FIFO с несколькими производителями и потребителями, предложенная Киршем и др. [КЛП13].
kirsch_bounded_kfifo_queue — ограниченная очередь k-FIFO с несколькими производителями и потребителями, предложенная Киршем и др. [КЛП13].
nikolaev_queue — неограниченная очередь с несколькими производителями и несколькими потребителями, предложенная Николаевым [Nik19].
nikolaev_bounded_queue — ограниченная очередь с несколькими производителями и несколькими потребителями, предложенная Николаевым [Nik19].
harris_michael_list_based_set — контейнер без блокировок, содержащий отсортированный набор уникальных объектов. Эта структура данных основана на решении, предложенном Майклом [Mic02], которое основывается на исходном предложении Харриса [Har01].
harris_michael_hash_map — хэш-карта без блокировок, основанная на решении, предложенном Майклом [Mic02], которое основывается на исходном предложении Харриса [Har01].
chase_work_stealing_deque — дек для кражи работы, основанный на предложении Чейза и Льва [CL05].
vyukov_hash_map — параллельная хэш-карта, которая использует мелкозернистую блокировку для операций обновления. Эта реализация во многом вдохновлена версией, предложенной Вьюковым [Vyu08].
left_right — общая реализация алгоритма LeftRight, предложенная Рамалхете и Коррейей [RC15].
seqlock — реализация последовательной блокировки (также часто называемой «последовательной блокировкой»).

Схемы рекультивации

Реализация схем рекультивации основана на адаптированной версии интерфейса, предложенной Робисоном [Rob13].

Реализуются следующие схемы рекультивации:

lock_free_ref_count [Val95, MS95]
hazard_pointer [Mic04]
hazard_eras [RC17]
quiescent_state_based
generic_epoch_based — это обобщенный восстановитель на основе эпох, который можно настроить несколькими способами. Для простоты для соответствующих конфигураций предопределены следующие псевдонимы.
- epoch_based [Fra04]
- new_epoch_based [HMBW07]
- debra [Bro15]
stamp_it [PT18a, PT18b]

Здание

xenium — это библиотека только заголовков, поэтому для ее использования достаточно включить папку xenium в список подключаемых каталогов. Никаких других сторонних библиотек не требуется. Однако реализация использует возможности C++17, поэтому требуется компилятор с достаточной поддержкой C++17. В сборках CI используются следующие компиляторы, поэтому известно, что они поддерживаются:

gcc9
лязг10
Визуальная Студия 2019

Для модульного теста требуется googletest , а для тестов — taocpp/json и taocpp/config . Эти зависимости включены в виде подмодулей, поэтому модульные тесты и/или тесты могут быть построены следующим образом:

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

Ссылки

[Бро15]	Тревор Александр Браун. Освобождение памяти для структур данных без блокировок: должен быть лучший способ. В материалах симпозиума ACM по принципам распределенных вычислений (PODC) 2015 г. , страницы 261–270. АКМ, 2015.
[CL05]	Дэвид Чейз и Йосси Лев. Динамический циклический дек с кражей работы. В материалах 17-го ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA) , страницы 21–28. АКМ, 2005.
[Fra04]	Кейр Фрейзер. Практическая свобода блокировки . Докторская диссертация, Компьютерная лаборатория Кембриджского университета, 2004 г.
[Har01]	Тимоти Л. Харрис. Прагматичная реализация неблокирующих связанных списков. В материалах 15-й Международной конференции по распределенным вычислениям (DISC) , страницы 300–314. Спрингер-Верлаг, 2001.
[HMBW07]	Томас Э. Харт, Пол Э. Маккенни, Анджела Демке Браун и Джонатан Уолпол. Выполнение восстановления памяти для блокировки без блокировки. Журнал параллельных и распределенных вычислений, 67 (12): 1270–1285, 2007.
[КЛП13]	Кристоф Кирш, Михаэль Липауц и Ханнес Пайер. Быстрые и масштабируемые очереди k-FIFO без блокировки. В материалах Международной конференции по параллельным вычислительным технологиям (PaCT) , страницы 208–223, Springer-Verlag, 2013.
[Mic02]	Магед М. Майкл. Высокопроизводительные динамические хеш-таблицы без блокировок и наборы на основе списков. В материалах 14-го ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам (SPAA) , страницы 73–82. АКМ, 2002.
[Mic04]	Магед М. Майкл. Указатели на опасность: безопасное восстановление памяти для объектов без блокировки. Транзакции IEEE в параллельных и распределенных системах, 15(6):491–504, 2004.
[MS95]	Магед М. Майкл и Майкл Л. Скотт. Исправление метода управления памятью для lock-free структур данных. Технический отчет, Рочестерский университет, 1995 г.
[MS96]	Магед М. Майкл и Майкл Л. Скотт. Простые, быстрые и практичные неблокирующие и блокирующие алгоритмы параллельных очередей. В материалах 15-го ежегодного симпозиума ACM по принципам распределенных вычислений (PODC) , страницы 267–275. АКМ, 1996.
[Ник19]	Руслан Николаев Масштабируемая, портативная и эффективно использующая память очередь fifo без блокировок. В материалах 33-го Международного симпозиума по распределенным вычислениям (DISC) , 2019.
[PT18a]	Мануэль Пётер и Йеспер Ларссон Трефф. Краткое объявление: Stamp-it, более потокоэффективная схема параллельного освобождения памяти в модели памяти C++. В материалах 30-го ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA) , страницы 355–358. АКМ, 2018.
[PT18b]	Мануэль Пётер и Йеспер Ларссон Трефф. Stamp-it — более потокоэффективная схема параллельного освобождения памяти в модели памяти C++. Технический отчет, 2018.
[Рам16]	Педро Рамалете. FAAArrayQueue — незаблокированная очередь MPMC (часть 4 из 4). Блог, ноябрь 2016 г.
[RC15]	Педро Рамалете и Андреа Коррейя. Слева-справа — метод управления параллелизмом с забывчивым чтением без ожидания. Октябрь 2015 г.
[RC17]	Педро Рамалете и Андреа Коррейя. Краткое объявление: Hazard Eras - неблокируемое освобождение памяти. В материалах 29-го ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA) , страницы 367–369. АКМ, 2017.
[Роб13]	Арч Д. Робисон. Основанный на политиках дизайн для безопасного уничтожения в одновременных контейнерах. Документ комитета по стандартам C++, 2013 г.
[Вал95]	Джон Д. Валуа. Структуры данных без блокировки . Кандидатская диссертация, Политехнический институт Ренсселера, 1995 г.
[Вью08]	Дмитрий Вьюков. Масштабируемая хэш-карта. Публикация в группах Google, 2008 г.
[Вью10]	Дмитрий Вьюков. Простая и эффективная ограниченная очередь MPMC. Публикация в группах Google, 2010 г.