One of the main challenges in multithreading applications is the access to shared memory. In case you have several software-components which want to read and write to shared memory you must synchronize these data access. The concept of Software Transactional Memory (STM) is based on the idea to use a concurrency control mechanism analogous to database transactions. A transaction in this context is a series of reads and writes to shared memory. These reads and writes are logically connected and should be executed in an atomic way, which means that intermediate states are not visible to other components. The transaction concept is an alternative to lock-based synchronization.

Let’s look at the following example to understand the concept: We have two list which store some data. Now we want to transfer one value from the first list to the second list. At the same time some other parallel processes may access the lists too. These other components may want to read or write some data. The transactional concept will guarantee a consistent state of the data objects. The task which wants to execute the movement of the value from one list into another list will implement execute the delete and insert operations as a transaction. In case another task reads the data at this moment it will only see the lists before the movement or after the movement. It will never see the intermediate state where the data value is deleted in one list but not yet inserted into the other list.

STM in C++

Unfortunately, STM is not yet part of standard C++ programming language. It is on the list of possible C++20 features but as there are some other features with higher priority it is not for sure that STM will be part of the standard soon. Nevertheless, the concept is well defined and there exist an experimental implementation of STM in GCC 6.1. Furthermore, there are a lot of third party libraries which will allows to use STM in C++ applications.

Within this article I want to introduce the concept in general and don’t want to show the implementation based on a specific one of these third-party libraries. Therefore, the source code of this article is based on the keyword introduced for the experimental implementation. You will find an introduction to these keywords within the cpp reference.

So please keep in mind that the shown example implementations cannot be compiled with a standard compiler. You can use a compiler which contains an experimental implementation of the STM or you may use a third-party library and adapt the example implementation accordingly.

Transactional Concept

A transaction is an action with the following characteristics: Atomicity, Consistency, Isolation and Durability (ACID). The STM in C++ will have these characteristics, except of durability. Based on the example above, I want to explain the remaining three concepts. We want to implement a transaction which contains two statements: delete a value from one list and insert the value into another list.

Atomicity

The two statements will be executed together ore none of them is executed. The transaction covers all the statements and therefore the transaction acts like a single statement.

Consistency:

The system is always in a valid state. Either all the statements within a transaction are executed or none of the statements is executed. The system will never be in a state where a part of the statements was executed only.

Isolation:

Each transaction is executed independently of other transactions.

Execution of a Transaction

As mentioned at the beginning of the article, the transaction concept is an alternative to lock-based synchronization. Therefore, transactions are implement in a way to ensure the characteristics shown above without the need of lock-mechanisms.

A transaction stores its starting state and executes all statements without lock-mechanisms. In case there is a conflict during transaction execution, it will be stopped and a rollback to the starting state is done. Afterwards the transaction will be executed again. If all statements are executed successful, the transaction will check whether the start conditions are still valid, e.g. no one has changed the data in the meantime. If the start conditions are still valid, the transaction will be published.

A transaction is a speculative action. In contrast to a lock-based mechanism, it follows an optimistic approach. The transaction will be executed without any synchronization but will be published only in case the start conditions are still valid. A lock-based mechanism instead follows a pessimistic approach. It ensures the exclusive access to the critical section and waits in case some other task currently holds the access rights to this critical section. The optimistic approach does not need this expensive lock-mechanism but of course, permanent rollbacks due to frequent data collisions may be expensive too. Therefore, it depends on the use case whether STM or lock-based synchronization is faster.

Performance

STM may increase the performance in many use cases. Unlike the lock-based techniques used in most modern multithreaded applications, STM follows an optimistic approach. A thread completes modifications to shared memory without regard for what other threads might be doing. It records every read and write within a log and stores the starting conditions to detect possible conflicts. Of course, this kind of data management isn’t for free but it creates less overhead than locking mechanisms. Additional, in case of data conflicts, a rollback is done and the transaction will be repeated. Therefore, the performance of STM is very much related to the likelihood of data conflicts.

The benefit of this optimistic approach is increased concurrency. No thread needs to wait for access to the shared memory. Different threads can safely and simultaneously modify parts of the shared memory which would otherwise be protected under the same lock in lock-based implementations.

Implementation

It is very easy to use STM in your implementations. No matter if you use a STM library or the upcoming standard language feature, normally you just must put the operations which belong together in a transaction, by enclose them with an according block (we will see examples later). But of course, you must respect the technical conditions of the STM concept. If you read and write data objects within transactions, you should not access these data objects outside of transactions too. Such data manipulations in not synchronized task can lead to data races. Furthermore, within your transactions, you are limited to transaction-safe functions. As we learned so far, the STM concept works with an optimistic approach and in case of conflicts a transaction rollback is done. Of course, this is possible only in case the functions called within the transaction can be rolled back. For example the std::cout function is not transaction-safe and cannot be used within transactions.

Example

Now we would look at an example which uses the experimental STM implementation of C++. Please keep in mind that the following source code will create compiler errors in standard compilers. You must use a compiler which has an implementation of this experimental feature or you may use on of the many third-party libraries for STM and adapt the example accordingly.

Within the example application we would look at typical use cases: change a value and execute some function based on the value. This sounds very easy but has the well-known pitfalls if we change to a multithreaded application. So, let’s say we have two variables. Within a function we want to change the variables values and afterwards we want to read the values and pass them to a function – in this case a standard cout function.

int x, y;

using namespace std::chrono_literals;

void Execute()
{
	x++;
	y--;

	std::cout << "(" << x << "," << y << ")";

	std::this_thread::sleep_for(100ns);
}

int main()
{
	x = 0;
	y = 100;

	std::vector threads(5);
	
	for (auto& thread : threads)
	{
		thread = std::thread([] { for (int i = 0; i < 20; ++i) Execute(); });
	}

	for (auto& thread : threads)
	{
		thread.join();
	}
	
	return 0;
}

If we execute this application we will see some strange issues. It looks like some of the variable increase and decrease steps get lost as the final values are not like expected and furthermore the output of cout may be muddled up.

These issues happen because there are data races between the different threads. A thread may execute the value increase or decrease at a moment where another thread already executed such a data change. So, the second thread works on partially changed data. The same concurrency issue occurs for the cout function. It may be partially executed by one thread and then interrupted by another thread.

The actual STM concept idea offers two concepts to solve these issues: Synchronized Blocks and Atomic Blocks. Following we will see and compare the two concepts and adapt the example application accordingly.

Synchronized Blocks

The STM implementation contains the concept of synchronized blocks. A synchronized block allows to combine different statements within this block. It is executed in a way that behaves like it is secured by one global lock-statement. Maybe it is implemented with a more performant mechanism but it must behave in the same way like a lock.

The example can be changed very easily. We just have to write the statements into a synchronized block. Now the application behaves like expected. The variables will be increased and decreased and the output looks fine.

int x, y;

using namespace std::chrono_literals;

void ExecuteSynchronized()
{
	synchronized{
		x++;
		y--;

		std::cout << "(" << x << "," << y << ")";

		std::this_thread::sleep_for(100ns);
	}
}

int main()
{
	x = 0;
	y = 100;

	std::vector threads(5);

	for (auto& thread : threads)
	{
		thread = std::thread([] { for (int i = 0; i < 20; ++i) ExecuteSynchronized(); });
	}

	for (auto& thread : threads)
	{
		thread.join();
	}

	return 0;
}

As synchronized blocks behave like as they are synchronized by a global lock, the different blocks will be executed successively. So we have the behavior of a lock-based mechanism and no real STM. STM is based on optimistic locking and transactions and allows a parallel execution of different threads. Synchronized blocks follow a pessimistic lock-based approach and will execute the blocks successively.

This sound like a disadvantage in the first moment but it will allow us to use transaction unsafe code within the synchronized blocks. For example, the “cout” function is transaction unsafe but we can still use it. In my opinion there are two big advantages of synchronized blocks. At first you can change any existing source code which is not thread safe into thread safe code just by enclosing the existing statement by a synchronized block. And second, if you use real STM, like we will see in the next example, you are able to change from real STM to the lock-based synchronization block just by change one statement. This will allow you to test both concept and use the better one according to your use case. Furthermore, you can change from real STM to synchronized blocks in case you want to use a transaction unsafe function.

Atomic Blocks

Using atomic blocks is nearly as simple as using synchronized blocks. We just have to add the according block which encloses the critical statements. But additional we must remove the “cout” function now as this function is not transaction safe. So, we have to change the output function and for example move it behind the thread execution or we can write into an buffer during thread execution and output this buffer within a parallel task.

int x, y;

using namespace std::chrono_literals;

void ExecuteAtomic()
{
	atomic_noexcept{
		x++;
		y--;

		std::this_thread::sleep_for(100ns);
	}
}

int main()
{
	x = 0;
	y = 100;

	std::vector threads(5);

	for (auto& thread : threads)
	{
		thread = std::thread([] { for (int i = 0; i < 20; ++i) ExecuteAtomic(); });
	}

	for (auto& thread : threads)
	{
		thread.join();
	}

	return 0;
}

Atomic blocks exist in three variations which differ in exception handling:

• atomic_noexcept: If an exception occurs, std::abort is called and the application will be aborted.
• atomic_cancel: If a transaction-safe exception occurs, the transaction will be canceled and rolled back and the exception is rethrown.
• atomic_commit: If a transaction-safe exception occurs, the transaction will be committed and the exception is rethrown.

Summary

The Software Transactional Memory is a performant and easy to use concept to solve data races in multithreading applications. In the (near) future STM will be integrated in the C++ standard. In the meantime, you can use existing third party libraries to add STM features.