Concurrency with Modern C++: What every professional C++ programmer should know about concurrency

Reader Testimonials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Fonts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Special Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
Run the Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
How should you read the book? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Personal Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
About Me . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
A Quick Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1. Concurrency with Modern C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1 C++11 and C++14: The Foundation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 C++17: Parallel Algorithms of the Standard Template Library . . . . . . . . . . . . . 8
1.2.1 Execution Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2 New Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Calculating the Sum of a Vector . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 The Dining Philosophers Problem by Andre Adrian . . . . . . . . . . . . . . 10
1.4.3 Thread-Safe Initialization of a Singleton . . . . . . . . . . . . . . . . . . . . 10
1.4.4 Ongoing Optimization with CppMem . . . . . . . . . . . . . . . . . . . . . 10
1.4.5 Fast Synchronization of Threads . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Variations of Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Modification and Generalization of a Generator . . . . . . . . . . . . . . . . . . . . . 11
1.7 Various Job Workflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 The Future of C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8.1 Executors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8.2 Extended futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8.3 Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8.4 Task Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8.5 Data-Parallel Vector Library . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9 Patterns and Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9.1 Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9.2 Concurrent Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9.3 Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.10 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.11 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.12 Time Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.13 CppMem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.14 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
The Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2. Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Basics of the Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 What is a memory location? . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.2 What happens if two threads access the same memory location? . . . . . . . 19
2.2 The Contract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 The Foundation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2 The Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Atomics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.1 Strong versus Weak Memory Model . . . . . . . . . . . . . . . . . . . . . . 23
2.3.2 The Atomic Flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.3 std::atomic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.4 All Atomic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.3.5 Free Atomic Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.6 std::atomic_ref (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.4 The Synchronization and Ordering Constraints . . . . . . . . . . . . . . . . . . . . . 67
2.4.1 The Six Variants of Memory Orderings in C++ . . . . . . . . . . . . . . . . 67
2.4.2 Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.4.3 Acquire-Release Semantic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.4.4 std::memory_order_consume . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
2.4.5 Relaxed Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5 Fences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.5.1 std::atomic_thread_fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.5.2 std::atomic_signal_fence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3. Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.1 The Basic Thread std::thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.1.1 Thread Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.1.2 Thread Lifetime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.1.3 Thread Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.1.4 Member Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.2 The Improved Thread std::jthread (C++20) . . . . . . . . . . . . . . . . . . . . . . . 116
3.2.1 Automatically Joining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.2.2 Cooperative Interruption of a std::jthread . . . . . . . . . . . . . . . . . . 119
3.3 Shared Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.3.1 Mutexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.3.2 Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
3.3.3 std::lock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.3.4 Thread-safe Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
3.4 Thread-Local Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
3.5 Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
3.5.1 The Predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
3.5.2 Lost Wakeup and Spurious Wakeup . . . . . . . . . . . . . . . . . . . . . . . 157
3.5.3 The Wait Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
3.6 Cooperative Interruption (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
3.6.1 std::stop_source . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
3.6.2 std::stop_token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
3.6.3 std::stop_callback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
3.6.4 A General Mechanism to Send Signals . . . . . . . . . . . . . . . . . . . . . 165
3.6.5 Additional Functionality of std::jthread . . . . . . . . . . . . . . . . . . . 168
3.6.6 New wait Overloads for the condition_variable_any . . . . . . . . . . . . . 169
3.7 Semaphores (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
3.8 Latches and Barriers (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3.8.1 std::latch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
3.8.2 std::barrier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
3.9 Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
3.9.1 Tasks versus Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
3.9.2 std::async . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
3.9.3 std::packaged_task . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
3.9.4 std::promise and std::future . . . . . . . . . . . . . . . . . . . . . . . . . 199
3.9.5 std::shared_future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
3.9.6 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
3.9.7 Notifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
3.10 Synchronized Outputstreams (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . 215
4. Parallel Algorithms of the Standard Template Library . . . . . . . . . . . . . . . . . . . 225
4.1 Execution Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
4.1.1 Parallel and Vectorized Execution . . . . . . . . . . . . . . . . . . . . . . . . 228
4.1.2 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
4.1.3 Hazards of Data Races and Deadlocks . . . . . . . . . . . . . . . . . . . . . 231
4.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
4.3 The New Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
4.3.1 More overloads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.3.2 The functional Heritage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
4.4 Compiler Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
4.4.1 Microsoft Visual Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
4.4.2 GCC Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
4.4.3 Further Implementations of the Parallel STL . . . . . . . . . . . . . . . . . . 242
4.5 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
4.5.1 Microsoft Visual Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
4.5.2 GCC Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
5. Coroutines (C++20) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
5.1 A Generator Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.2 Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
5.2.1 Typical Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
5.2.2 Underlying Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
5.2.3 Design Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
5.2.4 Becoming a Coroutine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
5.3 The Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
5.3.1 Promise Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
5.3.2 Coroutine Handle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
5.3.3 Coroutine Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
5.4 Awaitables and Awaiters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
5.4.1 Awaitables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
5.4.2 The Concept Awaiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
5.4.3 std::suspend_always and std::suspend_never . . . . . . . . . . . . . . . . . 257
5.4.4 initial_suspend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
5.4.5 final_suspend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
5.4.6 Awaiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
5.5 The Workflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
5.5.1 The Promise Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
5.5.2 The Awaiter Workflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
5.6 co_return . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.6.1 A Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.7 co_yield . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
5.7.1 An Infinite Data Stream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
5.8 co_await . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
5.8.1 Starting a Job on Request . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
5.8.2 Thread Synchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
5.9 std::generator (C++23) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
6. Case Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
6.1 Calculating the Sum of a Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
6.1.1 Single-Threaded addition of a Vector . . . . . . . . . . . . . . . . . . . . . . 280
6.1.2 Multi-threaded Summation with a Shared Variable . . . . . . . . . . . . . . 286
6.1.3 Thread-Local Summation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
6.1.4 Summation of a Vector: The Conclusion . . . . . . . . . . . . . . . . . . . . 303
6.2 The Dining Philosophers Problem by Andre Adrian . . . . . . . . . . . . . . . . . . . 305
6.2.1 Multiple Resource Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
6.2.2 Multiple Resource Use with Logging . . . . . . . . . . . . . . . . . . . . . . 308
6.2.3 Erroneous Busy Waiting without Resource Hierarchy . . . . . . . . . . . . . 309
6.2.4 Erroneous Busy Waiting with Resource Hierarchy . . . . . . . . . . . . . . . 310
6.2.5 Still Erroneous Busy Waiting with Resource Hierarchy . . . . . . . . . . . . 313
6.2.6 Correct Busy Waiting with Resource Hierarchy . . . . . . . . . . . . . . . . 315
6.2.7 Good low CPU load Busy Waiting with Resource Hierarchy . . . . . . . . . 317
6.2.8 std::mutex with Resource Hierarchy . . . . . . . . . . . . . . . . . . . . . . 318
6.2.9 std::lock_guard with Resource Hierarchy . . . . . . . . . . . . . . . . . . . 319
6.2.10 std::lock_guard and Synchronized Output with Resource Hierarchy . . . . 320
6.2.11 std::lock_guard and Synchronized Output with Resource Hierarchy and acount . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
6.2.12 A std::unique_lock using deferred locking . . . . . . . . . . . . . . . . . . 323
6.2.13 A std::scoped_lock with Resource Hierarchy . . . . . . . . . . . . . . . . . 325
6.2.14 The Original Dining Philosophers Problem using Semaphores . . . . . . . . 326
6.2.15 A C++20 Compatible Semaphore . . . . . . . . . . . . . . . . . . . . . . . . 328
6.3 Thread-Safe Initialization of a Singleton . . . . . . . . . . . . . . . . . . . . . . . . . 330
6.3.1 Double-Checked Locking Pattern . . . . . . . . . . . . . . . . . . . . . . . . 330
6.3.2 Performance Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
6.3.3 Thread-Safe Meyers Singleton . . . . . . . . . . . . . . . . . . . . . . . . . 334
6.3.4 std::lock_guard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
6.3.5 std::call_once with std::once_flag . . . . . . . . . . . . . . . . . . . . . . 338
6.3.6 Atomics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
6.3.7 Performance Numbers of the various Thread-Safe Singleton Implementations 343
6.4 Ongoing Optimization with CppMem . . . . . . . . . . . . . . . . . . . . . . . . . . 345
6.4.1 CppMem: Non-Atomic Variables . . . . . . . . . . . . . . . . . . . . . . . . 347
6.4.2 CppMem: Locks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
6.4.3 CppMem: Atomics with Sequential Consistency . . . . . . . . . . . . . . . . 353
6.4.4 CppMem: Atomics with Acquire-Release Semantics . . . . . . . . . . . . . . 360
6.4.5 CppMem: Atomics with Non-atomics . . . . . . . . . . . . . . . . . . . . . 364
6.4.6 CppMem: Atomics with Relaxed Semantic . . . . . . . . . . . . . . . . . . . 366
6.4.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
6.5 Fast Synchronization of Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
6.5.1 Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
6.5.2 std::atomic_flag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
6.5.3 std::atomic<bool> . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
6.5.4 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
6.5.5 All Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
6.6 Variations of Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
6.6.1 A Lazy Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
6.6.2 Execution on Another Thread . . . . . . . . . . . . . . . . . . . . . . . . . . 387
6.7 Modification and Generalization of a Generator . . . . . . . . . . . . . . . . . . . . . 391
6.7.1 Modifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
6.7.2 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
6.8 Various Job Workflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
6.8.1 The Transparent Awaiter Workflow . . . . . . . . . . . . . . . . . . . . . . 401
6.8.2 Automatically Resuming the Awaiter . . . . . . . . . . . . . . . . . . . . . . 403
6.8.3 Automatically Resuming the Awaiter on a Separate Thread . . . . . . . . . . 407
6.9 Thread-Safe Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
7. The Future of C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
7.1 Executors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
7.1.1 A long Way . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
7.1.2 What is an Executor? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
7.1.3 First Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
7.1.4 Goals of an Executor Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 427
7.1.5 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
7.1.6 Execution Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
7.1.7 A Prototype Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 430
7.2 Extended Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
7.2.1 Concurrency TS v1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
7.2.2 Unified Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
7.3 Transactional Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
7.3.1 ACI(D) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
7.3.2 Synchronized and Atomic Blocks . . . . . . . . . . . . . . . . . . . . . . . . 444
7.3.3 transaction_safe versus transaction_unsafe Code . . . . . . . . . . . . . . 448
7.4 Task Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
7.4.1 Fork and Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
7.4.2 define_task_block versus define_task_block_restore_thread . . . . . . . . 450
7.4.3 The Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
7.4.4 The Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
7.5 Data-Parallel Vector Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
7.5.1 Data-Parallel Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
7.5.2 The Interface of the Data-Parallel Vectors . . . . . . . . . . . . . . . . . . . 454
Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
8. Patterns and Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
8.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
8.2 Invaluable Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
8.3 Pattern versus Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
8.4 Anti-Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
9. Synchronization Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
9.1 Dealing with Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
9.1.1 Copied Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465
9.1.2 Thread-Specific Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
9.1.3 Future . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
9.2 Dealing with Mutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
9.2.1 Scoped Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
9.2.2 Strategized Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
9.2.3 Thread-Safe Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
9.2.4 Guarded Suspension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
10. Concurrent Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
10.1 Active Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
10.1.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
10.1.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
10.1.3 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
10.1.4 Dynamic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
10.1.5 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . 506
10.1.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
10.2 Monitor Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
10.2.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
10.2.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
10.2.3 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
10.2.4 Dynamic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
10.2.5 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . 514
10.2.6 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
10.3 Half-Sync/Half-Async . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
10.3.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
10.3.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
10.3.3 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
10.3.4 Dynamic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
10.3.5 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . 521
10.3.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
10.4 Reactor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
10.4.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
10.4.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
10.4.3 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
10.4.4 Dynamic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
10.4.5 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . 525
10.4.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
10.5 Proactor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
10.5.1 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
10.5.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
10.5.3 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
10.5.4 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . . . . . 533
10.5.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
10.6 Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
11. Best Practices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
11.1 General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
11.1.1 Code Reviews . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
11.1.2 Minimize Sharing of Mutable Data . . . . . . . . . . . . . . . . . . . . . . . 541
11.1.3 Minimize Waiting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
11.1.4 Prefer Immutable Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
11.1.5 Use pure functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
11.1.6 Look for the Right Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . 548
11.1.7 Use Static Code Analysis Tools . . . . . . . . . . . . . . . . . . . . . . . . . 549
11.1.8 Use Dynamic Enforcement Tools . . . . . . . . . . . . . . . . . . . . . . . . 549
11.2 Multithreading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
11.2.1 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
11.2.2 Data Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
11.2.3 Condition Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
11.2.4 Promises and Futures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
11.3 Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
11.3.1 Don’t use volatile for synchronization . . . . . . . . . . . . . . . . . . . . . 567
11.3.2 Don’t program Lock Free . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
11.3.3 If you program Lock-Free, use well-established patterns . . . . . . . . . . . 567
11.3.4 Don’t build your abstraction, use guarantees of the language . . . . . . . . . 568
11.3.5 Don’t reinvent the wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
12. General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
12.1 Concurrent Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
12.2 Locking Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
12.3 Granularity of the Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574
12.4 Typical Usage Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
12.4.1 Linux (GCC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
12.4.2 Windows (cl.exe) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
12.5 Avoidance of Loopholes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
12.6 Contention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
12.6.1 Single-Threaded Summation without Synchronization . . . . . . . . . . . . 586
12.6.2 Single-Threaded Summation with Synchronization (lock) . . . . . . . . . . . 588
12.6.3 Single-Threaded Summation with Synchronization (atomic) . . . . . . . . . 589
12.6.4 The Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
12.7 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
12.8 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
12.9 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
13. Lock-Based Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
13.1 Concurrent Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
13.1.1 A Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
13.2 Concurrent Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
13.2.1 A Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
13.2.2 Coarse-Grained Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
13.2.3 Fine-Grained Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
14. Lock-Free Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
14.1 General Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620
14.1.1 The Next Evolutionary Step . . . . . . . . . . . . . . . . . . . . . . . . . . . 620
14.1.2 Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620
14.2 Concurrent Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
14.2.1 A Simplified Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 622
14.2.2 A Complete Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 624
14.3 Concurrent Queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
Further Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
15. Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
15.1 ABA Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
15.2 Blocking Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
15.3 Breaking of Program Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654
15.4 Data Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
15.5 Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
15.6 False Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
15.7 Lifetime Issues of Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
15.8 Moving Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
15.9 Race Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
16. The Time Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
16.1 The Interplay of Time Point, Time Duration, and Clock . . . . . . . . . . . . . . . . . 669
16.2 Time Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
16.2.1 From Time Point to Calendar Time . . . . . . . . . . . . . . . . . . . . . . . 670
16.2.2 Cross the valid Time Range . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
16.3 Time Duration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
16.3.1 Calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676
16.4 Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
16.4.1 Accuracy and Steadiness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
16.4.2 Epoch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
16.5 Sleep and Wait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
17. CppMem - An Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
17.1 The simplified Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
17.1.1 1. Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692
17.1.2 2. Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 692
17.1.3 3. Display Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
17.1.4 4. Display Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
17.1.5 5. Model Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
17.1.6 The Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
18. Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
18.1 adress_free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
18.2 ACID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
18.3 CAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
18.4 Callable Unit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
18.5 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
18.6 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
18.7 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
18.8 Critical Section . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 699
18.9 Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
18.10 Eager Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
18.11 Executor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
18.12 Function Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
18.13 Lambda Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
18.14 Lazy evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
18.15 Lock-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
18.16 Lock-based . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
18.17 Lost Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
18.18 Math Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
18.19 Memory Location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
18.20 Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
18.21 Modification Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
18.22 Monad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
18.23 Non-blocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
18.24 obstruction-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
18.25 Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
18.26 Predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
18.27 Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
18.28 RAII . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
18.29 Release Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
18.30 Sequential Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
18.31 Sequence Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
18.32 Spurious Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
18.33 Thread . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
18.34 Total order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
18.35 TriviallyCopyable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
18.36 Undefined Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
18.37 volatile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
18.38 wait-free . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 709

C++11 is the first C++ standard that deals with concurrency. The story goes on with C++17, C++20, and will continue with C++23. I'll give you a detailed insight into the current and the upcoming concurrency in C++. This insight includes the theory and a lot of practice.

• C++11 and C++14 have the basic building blocks for creating concurrent or parallel programs.

• With C++17, we got the parallel algorithms of the Standard Template Library (STL). That means most of the algorithms of the STL can be executed sequentially, in parallel, or vectorized.

• The concurrency story in C++ goes on. With C++20, we got coroutines, atomic smart pointers, semaphores, latches, and barriers.

• C++23 supports the first concrete coroutine: std::generator.

• With future C++ standards, we can hope for executors, extended futures, transactional memory, and more.