concurrency_and_parallelism.md

Concurrency and parallelism

Table of contents

• Introduction and overview
• SIMD
  • SIMD within a register (SWAR)
• Multithreading
  • Concurrency and the standard library
    • std::atomic
    • std::atomic_shared_ptr
    • std::condition_variable
    • std::mutex
    • std::promise / std::future
    • std::async
    • std::thread
    • std::lock_guard
  • Data races and race conditions
  • Lock-based
    • Mutex locks
    • Spin locks
  • Lock-free
    • Hazard pointers
    • Read-copy-update (RCU)
  • Memory model
  • POSIX threads
  • Coroutines
  • Executors
  • Concurrency patterns
• GPU computing

---

Introduction and overview

🔗

• B.Barney. Introduction to parallel computing – Lawrence Livermore National Laboratory

---

---

SIMD

🎥

• B.Steagall. Adventures in SIMD-thinking – CppNow (2021)
• B.Steagall. Adventures in SIMD-thinking Part I, Part II – CppCon (2020)

SIMD within a register (SWAR)

🔗

• SWAR – Wikipedia
• H.Dietz. Ch. 4: SIMD within a register (e.g., using MMX) – Linux parallel processing HOWTO
• SIMD and SWAR techniques – Chess Programming Wiki

❔

• Is reinterpret_casting between hardware SIMD vector pointer and the corresponding type an undefined behavior? – Stack Overflow
• Is casting to simd-type undefined behaviour in C++? – Stack Overflow

---

Multithreading

🔗

• E.Bendersky. C++11 threads, affinity and hyperthreading (2016)

🎥

• A.Williams. An introduction to multithreading in C++20 – CppCon (2022)
• F.Petriconi. An adventure in race conditions – ACCU (2019)
• A.Sermersheim. Multithreading is the answer. What is the question? Part I, Part II – CppCon (2017)
• R.Grimm. C++11 multithreading done right? – Meeting C++ (2014)
• A.Williams. The continuing future of C++ concurrency – CppCon (2016)

📖

• P.E.McKenney. Is parallel programming hard, and, if so, what can you do about it? (2018)
• A.Williams. C++ concurrency in action: Practical multithreading (2019)
• Ch. 9: Parallelism and concurrency – J.Galowicz. C++17 STL cookbook: Discover the latest enhancements to functional programming and lambda expressions (2017)
• Ch. 18: Concurrency – N.M.Josuttis. The C++ standard library: A tutorial and reference (2012)

📄

• P.E.McKenney. Memory barriers: A hardware view for software hackers (2010)

Concurrency and the standard library

🔗

• L.R.Teodorescu. A case against blind use of C++ parallel algorithms – Overload 161 (2021)
• A.Williams. Multi-threading in C++0x – Overload 93 (2009)
• C++11 standard library extensions: Concurrency – Standard C++ Foundation

🎥

• J.Machutová. Memory Model: Get your shared data under control – C++ Meeting (2023)
• A.Williams. An introduction to multithreading in C++20 – CppCon (2022)
• M.Shah. Back to basics: Concurrency – CppCon (2021)
• A.O’Dwyer. Back to basics: Concurrency – CppCon (2020)
• B.A.Lelbach. The C++17 parallel algorithms library and beyond – CppCon (2016)
• D.Kühl. C++17 parallel algorithms – CppCon (2017)

std::atomic

❔

• Does std::atomic::operator++ really return by value? – Stack Overflow

🎥

• H.-J.Boehm. Using weakly ordered C++ atomics correctly – CppCon (2016)

std::atomic_shared_ptr

🔗

• A.Williams. Why do we need atomic_shared_ptr? (2015)

❔

• What is the difference between std::shared_ptr and std::experimental::atomic_shared_ptr? – Stack Overflow

std::condition_variable

The std::condition_variable is a synchronization primitive that can be used to block a thread, or multiple threads at the same time, until another thread both modifies a shared variable (the condition), and notifies the std::condition_variable.

❔

• Shared atomic variable is not properly published if it is not modified under mutex – Stack Overflow

⚓

• std::condition_variable – C++ reference

std::mutex

The std::mutex class is a synchronization primitive that can be used to protect shared data from being simultaneously accessed by multiple threads.

❔

• Move constructor for std::mutex – Stack Overflow
• Why is std::mutex::unlock() not noexcept – Stack Overflow

⚓

• std::mutex – C++ reference

std::promise / std::future

The std::promise provides a facility to store a value or an exception that is later acquired asynchronously via a std::future object created by the std::promise object.

❔

• What is std::promise? – Stack Overflow
• Futures vs. promises – Stack Overflow
• Why we need both std::promise and std::future? – Stack Overflow

⚓

• std::promise – C++ reference

std::async

🔗

• E.Bendersky. *The promises and challenges of std::async task-based parallelism in C++11 * (2016)
• M.Nelson. C++11’s async template – Dr.Dobb’s Journal (2012)

❔

• std::async won’t spawn a new thread when return value is not stored – Stack Overflow

⚓

• N.Josuttis. Why deprecating async() is the worst of all options – WG21/N3780
• H.-J.Boehm. async() future destructors must wait – WG21/N3679
• H.Sutter. async and ~future – WG21/N3451

std::thread

⚓

• H.-J.Boehm. A plea to reconsider detach-on-destruction for thread objects – WG21/N2802

std::lock_guard

❔

• Why is std::lock_guard not movable? – Stack Overflow

⚓

• std::lock_guard – C++ reference

Data races and race conditions

❔

• Are “data races” and “race condition” actually the same thing in context of concurrent programming – Stack Overflow

Lock-based

Mutex locks

🔗

• S.Ignatchenko. 5 big fat reasons why mutexes suck big time – Overload 149 (2019)
• M.Spertus. Thread-safe copy and move constructors (2011)

Spin locks

🔗

• When should one use a spinlock instead of mutex? – Stack Overflow
• Spinlock versus semaphore – Stack Overflow

Lock-free

Lock-free programming is a set of techniques for writing concurrent programs without using explicit locks.

🎥

• F.Pikus. C++ atomics, from basic to advanced: What do they really do? – CppCon (2017)
• F.Pikus. Live lock-free or deadlock (practical lock-free programming). Part I, Part II – CppCon (2015)
• H.Sutter. atomic<> weapons: Part I, Part II – C++ and Beyond (2012)

Hazard pointers

🔗

• Hazard pointer – Wikipedia
• A.Alexandrescu, M.Michael. Lock-free data structures with hazard pointers – Dr.Dobb’s Journal (2004)

Read-copy-update (RCU)

🔗

• Read-copy-update – Wikipedia
• P.E.McKenney. Introduction to RCU

🎥

• F.Pikus. Read, copy, update, then what? RCU for non-kernel programmers – CppCon (2017)
• P.E.McKenney. A lock-free concurrency toolkit for deferred reclamation and optimistic speculation – CppCon (2016)

⚓

• P.E.McKenney et al. Proposed RCU C++ API – WG21/P0461
• P.E.McKenney. Read-copy update (RCU) for C++ – WG21/P0279

Memory model

🔗

• C++11 introduced a standardized memory model. What does it mean? And how is it going to affect C++ programming? – Stack Overflow

⚓

• Memory model – C++ reference

POSIX threads

🔗

• B.Barney. POSIX threads programming

❔

• When to use pthread_exit() and when to use pthread_join() in Linux? – Stack Overflow

Coroutines

🎥

• R.Barkan. Coroutine intuition in C++ – C++ on Sea (2023)
• J.McNellis. Introduction to C++ coroutines – CppCon (2016)

Executors

🎥

• E.Niebler. Working with asynchrony generically: A tour of C++ executors. Part I, Part II – CppCon (2021)
• D.Vollmann. Executors for C++ – A Long story ... – CppCon (2015)

Concurrency patterns

See Concurrency patterns – Patterns, idioms, and design principles.

---

GPU computing

🎥

• P.Steinbach. C++ on GPUs done right? – Meeting C++ (2015)