Awesome
C++ Software Transactional Memory library
Working library for Software Transactional Memory that is built using several FP techniques and modern C++17.
- STM is monadic and combinatorial.
- It is very robust due to purely functional design.
- It is built on top of the custom Free monad.
- It operates by custom ADTs.
- It is usable despite it's experimental.
Additional materials
- Tutorial: Software Transactional Memory in C++
- Dining Philosophers Problem solved (variant 1)
- Dining Philosophers Problem solved (variant 2)
- More samples
- stm-free | Implementation in Haskell
- cpp_parsec_free | Implementation of Haskell's Parsec in C++ using the same Free Monad approach
- Functional Approach To Software Transactional Memory in C++ (Talk, Rus) | Slides (Eng) | My talk about this approach at C++ Russia 2018, Saint-Petersburg
- Functional Programming in C++ and Concurrent Calculations (Talk, Rus) | Slides (Eng) | My talk about this approach at LambdaNsk meetup, Novosibirsk, 2019
Requirements
- GCC 7.2
Troubleshooting
- Pass tvars to closures by copy.
- Make
retry
satisfiable.
Examples
The simplest possible usage is int counter increment from different threads.
Transaction:
stm::STML<int> incrementCounter(const stm::TVar<int>& tCounter) {
stm::STML<stm::Unit> modified =
stm::modifyTVar<int>(tCounter, [](int i) { return i + 1; });
return stm::bind<stm::Unit, int>(modified,
[&](const stm::Unit&){ return stm::readTVar<int>(tCounter); });
}
Evaluation:
Context ctx;
stm::TVar<int> tCounter = stm::newTVarIO(ctx, 0);
int counter = stm::atomically(ctx, incrementCounter(tCounter));
std::cout << "Counter: " << counter << std::endl;
The Dining Philosopher Problem
can be solved with STM elegantly. Here are the transactions for taking of forks:
stm::STML<stm::Unit> takeFork(const TFork& tFork) {
return stm::withTVar<Fork, stm::Unit>(tFork, [=](const Fork& fork) {
if (fork.state == ForkState::Free) {
return stm::writeTVar<Fork>(tFork, Fork { fork.name, ForkState::Taken });
}
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);
}
Notice the retry
combinator that marks some state illegal and makes the transaction to restart on case if fork was already taken.
To get more information, read the tutorial.