Lock-Free Parallel Algorithm Patterns

Advanced Pattern Mindset (Theory)

At the advanced level, concurrency bugs become:

• timing-dependent (rare races)
• ordering-dependent (memory model issues)
• performance-dependent (contention changes behavior)

Lock-free designs aim to:

• eliminate blocking
• minimize contention hotspots
• use atomic operations correctly

Code Example 1 — Lock-Free-ish Counter with C++ atomics

Atomics provide safe single-variable updates without locks.

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>

int main() {
  const int N = 1'000'00;
  const int T = 8;

  std::vector<int> a(N, 1);
  std::atomic<long long> sum{0};

  auto worker = [&](int tid) {
    int start = tid * (N / T);
    int end   = (tid + 1) * (N / T);

    long long local = 0;
    for (int i = start; i < end; i++) local += a[i];

    // Single shared update using atomic add (contention depends on T)
    sum.fetch_add(local, std::memory_order_relaxed);
  };

  std::vector<std::thread> threads;
  for (int tid = 0; tid < T; tid++) threads.emplace_back(worker, tid);
  for (auto& th : threads) th.join();

  std::cout << "sum=" << sum.load() << "\n";
}

When this helps

• You reduce work locally, then do one atomic update per thread
• That minimizes contention compared to atomics per element

Code Example 2 — Parallel Reduction Tree Skeleton

A reduction tree combines partial sums in stages. Even when implemented with locks/atomics, the tree structure reduces contention by aggregating locally first.

#include <vector>
#include <thread>
#include <iostream>

long long parallel_sum_tree(const std::vector<int>& a, int threads) {
  int N = (int)a.size();
  std::vector<long long> partial(threads, 0);

  auto worker = [&](int tid) {
    int start = tid * (N / threads);
    int end   = (tid + 1) * (N / threads);

    long long local = 0;
    for (int i = start; i < end; i++) local += a[i];
    partial[tid] = local;
  };

  std::vector<std::thread> ts;
  for (int t = 0; t < threads; t++) ts.emplace_back(worker, t);
  for (auto& th : ts) th.join();

  // Reduction tree over partial results (serial here for illustration)
  while ((int)partial.size() > 1) {
    int half = (int)partial.size() / 2;
    for (int i = 0; i < half; i++) partial[i] += partial[partial.size() - 1 - i];
    partial.resize(half + (partial.size() % 2));
  }
  return partial[0];
}

int main() {
  std::vector<int> a(1'000'000, 1);
  std::cout << "sum=" << parallel_sum_tree(a, 8) << "\n";
}

Why the tree matters

• Instead of “many threads hammering one variable,” you aggregate in levels
• In real systems, each level can be parallelized (e.g., with tasks)

Common Gotchas (Advanced)

• Wrong memory ordering: using atomics incorrectly can produce subtle bugs.
• Contention hotspots move: removing a lock can create a new hotspot at an atomic variable.
• Non-associative floating point: results may differ slightly across scheduling/order.
• ABA problem (advanced): lock-free pointer algorithms can be vulnerable without additional tagging/hazard pointers.

Quick Checklist

• Reduce locally; update shared state infrequently
• Prefer reduction trees over a single accumulator
• Use atomics for single-variable correctness, not for complex state
• Benchmark under realistic contention patterns