coders corner

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.

Within multithreading applications even trivial functions like reading and writing values may create issues. The std::atomic template can be used in such situations. Within this article I want to give a short introduction into this topic.

Atomic operations

Let’s start with an easy example. Within a loop we will increase a value by using the “++” operator. The loop will be executed by several threads.

int value;

void increase()
{
	for (int i = 0; i < 100000; i++)
	{
		value++;
	}
}

int main()
{
	std::thread thread1(increase);
	std::thread thread2(increase);
	std::thread thread3(increase);
	std::thread thread4(increase);
	std::thread thread5(increase);

	thread1.join();
	thread2.join();
	thread3.join();
	thread4.join();
	thread5.join();

	std::cout << value << '\n';

  return 0;
}

We expect an output of “500000” but unfortunately the output is below this value and it will be different on each execution of the application.

That’s because the “++” operation is not atomic. To keep it simple we can say this operation consist of three steps: read value, increase value and write value. If these steps are executed in parallel, several threads may read the same value and increase it by one. Therefore, the result is much lower than expected.

The same issue may occur on simple read and write mechanisms too. For example, thread 1 sets a value and thread 2 reads a value. In case the value type does not fit into a processor word, even such trivial read and write operations are not atomics. Accessing a 64bit variable in a 32bit system may result in incomplete values.

In such cases we need a synchronization mechanism to prevent the parallel execution. Of course, we could use standard lock mechanism. Or we could use the std::atomic template. This template defines an atomic type and guarantees atomicity of the operations of this type. To adapt the previous example, we just have to change the data type.

std::atomic<int> value;

void increase()
{
	for (int i = 0; i < 100000; i++)
	{
		value++;
	}
}

int main()
{
	std::thread thread1(increase);
	std::thread thread2(increase);
	std::thread thread3(increase);
	std::thread thread4(increase);
	std::thread thread5(increase);

	thread1.join();
	thread2.join();
	thread3.join();
	thread4.join();
	thread5.join();

	std::cout << value << '\n';

	return 0;
}

Now the result is like expected. The output of the application is “500000”.

std::atomic

As mentioned before, the std::atomic template defines a atomic type. If one thread writes to an atomic object while another thread reads from it, the behavior is well-defined. The operation itself has a guaranteed atomicity. Furthermore, read and writes to several different objects can have a sequential consistency guarantee. This guarantee is based on the selected memory model. We will see according examples later.

Read and write values

A common scenario in multithreading applications is the parallel read and write of variables by different threads. Let’s create a simple example with two threads, one is writing variable values and the other one reads these values.

int x;
int y;

void write()
{
	x = 10;
	y = 20;
}

void read()
{
	std::cout << y << '\n';
	std::cout << x << '\n';
}

int main()
{
	std::thread thread1(write);
	std::thread thread2(read);

	thread1.join();
	thread2.join();

  return 0;
}

Within this kind of implementation, the behavior is undefined. Depending on the order of the threads the output may be “20/10”, “0/0”, “0/10” or “20/0”. But beside these expected results it may happen that a read is done during a write and a therefore an incomplete written value is used. Within the example this should not happen but ex described before depending on the used processor and value types it may happen. Therefore, we can say that the behavior of the application is undefined.

By using the std::atomic template we could change the undefined behavior to a defined on. We just have to define the variables as atomic and use the according read and write functions.

std::atomic<int> x;
std::atomic<int> y;

void write()
{
	x.store(10);
	y.store(20);
}

void read()
{
	std::cout << y.load() << '\n';
	std::cout << x.load() << '\n';
}

int main()
{
	std::thread thread1(write);
	std::thread thread2(read);

	thread1.join();
	thread2.join();

  return 0;
}

Now, the behavior of the application is well defined. Independent from the used processor and independent from the data type (we could change from “int” to any other type), we have a defined set of results. Depending on the order of the threads the output may be “20/10”, “0/0”, “0/10”. The output “20/0” is not possible because the default mode for atomic loads and stores enforces sequential consistency. That means, within this example, x will always be written before y is changed. Therefore, the output “0/10” is possible but not “20/0”. As the std::atomic template ensures an atomic execution of the read and write functions we don’t have to fear undefined behavior due to incomplete data updates. So, we have a defined behavior with three possible results.

Memory model

As mentioned before, the selected memory model will change the behavior of atomic read and write functions. By default, the memory model ensures a sequential consistence. This may be expensive because the compiler is likely to emit memory barriers between every access. If your application or algorithm does not need this sequential consistency you can set a more relaxed memory model.

For example, if it is fine to get “20/0” as result within our application, we can set the memory model to “memory_order_relaxed”. This removes the synchronization and ordering constraints, but operation’s atomicity is still guaranteed.

void write()
{
	x.store(10, std::memory_order_relaxed);
	y.store(20, std::memory_order_relaxed);
}

void read()
{
	std::cout << y.load(std::memory_order_relaxed) << '\n';
	std::cout << x.load(std::memory_order_relaxed) << '\n';
}

Another interesting memory model is the Release-Acquire ordering. You can set the store functions within the first thread to “memory_order_release” and the load functions in the second thread to “memory_order_acquire”. In this case all memory writes (non-atomic and relaxed atomic) that happened before the atomic store in thread 1 are executed before load in thread 2 is executed. This takes us back to the ordered loads and stores, so “20/0” is no longer a possible output. But it does so with minimal overhead and an increased execution performance. Within this trivial example, the result is the same as with the full-blown sequential consistency. In a more complex example with several threads reading and writing all or some of the variables, the result may be different from the default sequential consistency.

void write()
{
	x.store(10, std::memory_order_release);
	y.store(20, std::memory_order_release);
}

void read()
{
	std::cout << y.load(std::memory_order_acquire) << '\n';
	std::cout << x.load(std::memory_order_acquire) << '\n';
}

As mentioned before, the Release-Acquire ordering ensures that all memory writes before the atomic store are executed, even non-atomic ones. So we could change the application and use a non-atomic type for x. The atomic store of y still ensures the correct write order.

int x;
std::atomic<int> y;

void write()
{
	x = 10;
	y.store(20, std::memory_order_release);
}

void read()
{
	std::cout << y.load(std::memory_order_acquire) << '\n';
	std::cout << x << '\n';
}

int main()
{
	std::thread thread1(write);
	std::thread thread2(read);

	thread1.join();
	thread2.join();

	return 0;
}

But again, in a more complex scenario with several threads and maybe a read of x only, it could be necessary to define the x as atomic.

Synchronization of threads

A common implementation technique for thread synchronization are locks. By using the atomic template, you can create such thread synchronizations without locks. Depending on the selected memory model this may increase the performance of your application.

The following application shows an example how to use the atomic template to synchronize the execution of two threads. Thread 2 will wait until thread 1 finished execution. This is done by using a variable which contains the execution state. Furthermore thread 1 commits its results within a data variable. The used Release-Acquire ordering mechanism of the atomic template ensures that the data is written before the synchronization flag is set.

int data;
std::atomic<bool> ready;

void write()
{
	data = 10;
	ready.store(true, std::memory_order_release);
}

void read()
{
	if(ready.load(std::memory_order_acquire))
	{ 	
		std::cout << data << '\n';
	}
}

int main()
{
	std::thread thread1(write);
	std::thread thread2(read);

	thread1.join();
	thread2.join();

	return 0;
}

Summary

This article gave a short introduction into the std::atomic template based on some common use cases. The examples name some major issues regarding data access in multithreading applications and introduce according implementations based on the atomic template. Of course this article is an introduction only. The atomic template offers some more features, for example there exist more memory model configurations beside the three shown within this article.

This article is one part of a series about the Visitor pattern. Please read the previous articles to get an overview about the pattern and to get the needed basics to understand this article.

As this article is the last one of the series I want to give a short retrospective and summarize the advantages and disadvantages of the Visitor pattern.

Retrospective

The article series started with a short introduction of the Visitor pattern, shows its strength but also explained the reasons for existing confusions and misunderstandings regarding this pattern. To remove these misunderstandings, we started with an investigation regarding the technical needs for this pattern and explored the difference of single dispatch and double dispatch.

Based on the technical needs we could derive the aims of the pattern. So, the article series continued with explanations and examples for the two main needs: enumeration and dispatching. A further article combined these two aspects to create a wholesome Visitor pattern example.

Based on this Visitor pattern example we investigated some additional questions often seen in practical application of the pattern. We created an extended enumerator Visitor with access to container elements which are not part of the visible objects and we analyzed the pros and cons of a monolithic single Visitor versus small specialized Visitors.

At next there followed articles about topics regarding the code quality. We learned how to create reusable enumerator and query visitors following the separation of concerns rule. And we have seen some examples which can lead to over engineering if we use the Visitor pattern.
 

Based on these articles I want to summarize the advantages and disadvantages of the pattern. Additional, as the pattern is a good candidate for over engineering, I want to name some use cases for alternative patterns.

Within the articles of this series we have seen some different implementations of the pattern. They all following the same main principles but have some differences in implementation according the practical needs of the respective use cases. Therefore, I don’t want to finish the article with a default implementation of the pattern as there is no singe default implementation. Instead I want to summarize the implementation aspect by list the involved components, the concepts to connect these components and I want to give some recommendations according the naming of the Visitor interfaces and methods.

Advantages

In object-oriented implementations, data classes often inherit from base classes or interfaces. Data containers which hold collections of these data classes often store pointers to the base classes. This object-oriented concept works fine as long as no type specific methods are needed. In case the client wants to call type specific methods he must cast the base class pointer to the specific type. This may result in code which is hard to understand, hard to maintain and has a good chance for errors.

The Visitor pattern resolves this issue. It allows a type safe access to the origin data type without the need of casting. Furthermore, the Visitor pattern offers traversing mechanism. As result, the pattern allows an easy access of data elements independent whether they are stored in a simple list or a complex container and independent whether they are stored in origin type or as pointers to any base type.

Disadvantages

It isn’t easy to find the right balance between many small specialized Visitor interfaces and a few or a single monolithic wide Visitor interface. And both approaches came with drawbacks. Many small interfaces increasing the complexity of the system and few wide interfaces lead to implementations containing empty method implementations.

The Visitor pattern traverse elements of a data container. This traversing is done via double dispatch. As a result of this dispatching, the traversing is some kind of hidden feature. A client implements the dispatching callbacks but he may easily overlock that the callback is one step of a traversing over a data container. On one hand that’s fine because the client should not have to think about the data structures, but on the other hand this may cause issues. Like in any other traversing mechanism, the client should not change the data container during traversing. So, the dispatching callback methods of the client should not change the data container itself. Furthermore, a traversing step should normally not execute long running complex functionalities. In summary, the traversing is some kind of hidden feature for a client developer, but it is an important software design fact which has to be respected by the client developer. This contradiction may result in bad software designs, especially if the developer isn’t that familiar with the Visitor pattern.

Alternatives

The Visitor pattern is a powerful but complex pattern. It unites two functionalities: type conversation by dispatching and traversing of complex data structures. But if only one of these functionalities is needed, you will find more specialized patterns which are less complex. If you want to traverse over a data structure only, you should implement an Iterator pattern. And if you want to do the dispatching only, you may use Callback mechanisms.

Components and Dependencies

The Visitor pattern contains the following components.

• Data Elements
• Data Container
• Enumerator
• Algorithm

The Data elements are the Visitable components and the Enumerator and Algorithm together are the Visitor component which execute some functionality based on the data elements. As explained and shown within the article series, I prefer a clear separation of concerns. Therefore, I recommend implementing the Algorithm aspect and the Enumeration aspect in different and independent components. Different Algorithms and different Enumeration can be loosely coupled by composition according the use case specific needs. A strong coupling by using inheritance should only be used in case there is no need for a reuse of any of the components.

Naming

At the very beginning of the article series I mentioned that, in my opinion, the Visitor pattern is one of the most misused and misunderstand patterns and the main source of this issue is the misleading naming of the pattern interfaces and methods.

Names of methods, interfaces and components should reflect their purpose. Therefore, I recommend avoiding the naming which is used within the origin Visitor pattern as this naming is meaningless. Following I would give you some naming I like to use. But of course, feel free to find your own naming.

As the name Visitor is well known and most software developers know the pattern, you should use this name anyway, even if it is universal and therefore some kind of meaningless. You should use the name but extend it with a more describing naming. As mentioned before, we have a separation of concerns and we may create specialized visitors. Therefore, we may create visitors for following purposes: enumeration, queries, data updates and so on. So, you should not implement a “IVisitor” interface or a “Visitor” component, but specialized ones like a “CustomerEnumerationVisitor” or a “OrderQueryVisitor”. Some may argue that implementation details should not part of naming. That’s totally fine, but as the Visitor contains the hidden enumeration feature it may be very useful for a client developer to know that he uses a component which is implemented as Visitor. Therefore, in this case it is fine to add the “Visitor” prefix to the component name.

The data elements will be passed to the Visitors. Therefore, I would call them “Visitable”. This results in according interface names like “IVisitableCustomer” or “IVisitableOrder”.

But what’s with the method names? The origin method names are “accept” and “visit”. To be honest, I think these names are terrible. They don’t say anything about their purpose. So, let’s think about the purpose of the methods and find some better names. The Visitor pattern is implemented by double dispatch. For this purpose, the data elements offer a method to get the instance of the data element. This getter method will pass the element instance to an instance receiver method which is provided by the Visitor. The method names should reflect this dispatching process. So, let’s call the method to get the element instance “GetInstance” and call the method which receives these instance “InstanceReceiver”.

By using such a clear naming, you could avoid some of the misunderstanding and errors which are a result of the complexity of the Visitor pattern.

Conclusion

The Visitor pattern is one of the base implementation patterns in software development. So, it should be part of the tool kit of a good software engineer. But unfortunately, the Visitor Pattern comes with a big disadvantage: it is one of the most misunderstood and misused patterns I know. This article series provided an extensive overview about the Visitor pattern and give you the needed knowledge to use the Visitor pattern within your applications.