Tools, Algorithms & Patterns
1. Correctness Tools
- Always-on compiler flags can detect common mistakes (e.g.
-Wall -Werror). - Check for memory correctness with a dynamic program instrumentation tool like Valgrind, or ASan (
-fsanitize=address). - Check for deadlocks, livelocks and dataraces with a dynamic program instrumentation tool like TSan (
-fsanitize=thread), or helgrind.
2. Performance Tools
- Linux
perf: a profiler to analyze CPU performance, memory usage, etc on user applications & kernel code. coz: a causal profiler to give optimization hints in parallel programs.- Multithreading Memory Allocators: Default memory allocators do not scale with threads (they use global structures to track alloc/free). Better solutions are heirarchical and batched (e.g.
tcmalloc,jemalloc, etc).
3. Algorithms
- Blocking algorithms use locks to protect shared data structures. They are simple to implement but can lead to contention and deadlocks.
- Non-blocking algorithms: suspention of any thread cannot cause suspension of other threads. We will use CAS but no locks. Lock free means one thread is guaranteed to progress, wait free means all threads are guaranteed to progress.
3.1 The ABA Problem
CAS can fail to detect changes if the value changes from A to B and back to A (the "ABA problem"). Solutions include:
- Using intermediate nodes (e.g.
shared_ptr, expensive). - Using tagged pointers (e.g. 128-bit CAS with a version number). This suffers from the "wraparound problem" where the version number can overflow and repeat, but this is less likely than the ABA problem.
- Defer reclamation using
read-copy-update (RCU)or hazard pointers. This allows threads to safely access shared data without locks, but is very complex.
4. Patterns
RAII (Resource Acquisition Is Initialization): A programming idiom where resource management is tied to object lifetime. Resources are acquired in constructors and released in destructors, ensuring that resources are always properly released even if an exception is thrown. We can use consistent semantics when passing arguments:
- By Value: local copy, used arbitrarily.
- By Reference: never freed before function returns,
- Unique Pointer: moved across functions or freed by end of scope.
- Shared Pointer: not freed until all references are gone.
RAII is also commonly used in locks ensuring they are always properly released.