What is a thread-safe data structure?

Before we begin learning about thread-safe data structures, we have to know what they are. If this seems like a simple question – data structures that can be used by multiple threads at once – you have not given the question enough thought. I cannot overstate how important it is to ask this question every time you start designing a new data structure or an algorithm to be used in a concurrent program. If this sentence puts you on guard and gives you pause, there is a good reason for it: I have just implied that the thread-safe data structure has no single definition that suits every need and every application. This is indeed the case, and is a very important point to understand.

The best kind of thread safety

Let's start with something that should be obvious but is often forgotten in practice: a very general principle of designing for high performance is that doing zero work is always faster than doing some work. For the...