Привет,
Меня зовут Александр Гранин, и я рад представить вам свою библиотеку для Software Transactional Memory.
Software Transactional Memory (STM, программная транзакционная память) - подход к программированию многопоточных приложений с конкурентно изменяемой моделью данных. STM значительно облегчает создание многопоточного кода, так как не нужно (почти) ломать голову над синхронизацией, data races и валидностью данных. Также STM снижает риск наступить на типичные проблемы параллельного программирования: блокировки, голодание, нетривиальные многопоточные баги. STM позволяет создать две модели: безопасную конкурентную модель данных и транзакционную модель изменения этих данных.
Для С++ существует несколько STM разной степени годности: Wyatt-STM (хорошая), пропозал TS 19841:2015 (плохой), и вот теперь я создал свою библиотеку, которая называется cpp_stm_free.
Библиотека построена на продвинутых идеях из мира ФП (Free-монады, алгебраические типы данных, и др.), и имеет монадический интерфейс. Иными словами, используя эту библиотеку, вы будете писать ФП-код. Библиотека повторяет интерфейс таковой STM в Haskell: транзакции - это монадические комбинаторы в монаде STML, работающие над транзакционными переменными (TVar).
Библиотека может быть полезна в разных сценариях.
- В серверных приложениях, обрабатывающих входящие и исходящие сообщения.
- В soft-realtime многопоточных играх.
- Для моделирования асинхронных вычислений.
Текущая версия библиотеки - v0.5.5. Требует GCC 7.2 и C++17 (и qmake; вскоре заменю на cmake или что-нибудь другое).
Буквально на днях я провел первый раунд оптимизаций и рефакторинга, увеличив производительность изначальной версии на 200% и добавив большое количество комбинаторов.
Для библиотеки имеется два движка, оба построены на Free монадах. Первый - Scott encoded Free monad (медленный), второй - Church encoded Free monad (быстрый). Для понимания: элементарные транзакции над простой моделью выполняются за <0.01 ms, сложные транзакции <0.1 ms, сложные транзакции в многопоточной среде <1 ms.
Более подробно с библиотекой можно ознакомиться в следующих материалах:
- Туториал
- Доклад на C++ Russia 2018 Функциональный подход к Software Transactional Memory
В качестве демонстрационного приложения я решил задачу «обедающих философов» (код здесь), и она работает хорошо. Пример транзакций для взятия ложек:
stm::STML<Unit> takeFork(const TFork& tFork) {
return stm::withTVar<Fork, stm::Unit>(tFork, [=](const Fork& fork) {
if (fork.state == ForkState::Free) {
return stm::modifyTVar<Fork>(tFork, setForkTaken);
}
else {
return stm::retry<stm::Unit>();
}
});
}
stm::STML<stm::Unit> takeForks(const TForkPair& forks) {
stm::STML<stm::Unit> lm = takeFork(forks.left);
stm::STML<stm::Unit> rm = takeFork(forks.right);
return stm::sequence(lm, rm);
}
Продолжаю развивать библиотеку, на очереди - еще один раунд оптимизаций и добавление новых фич.
Буду рад ответить на вопросы.
