Concurrent Optimization Techniques in C++: SIMD, Out‑of‑Order Execution, and Lock‑Free/Wait‑Free Algorithms

This article systematically reviews the concurrency optimization work performed by Baidu C++ engineers. It begins with a background discussion on why modern software must improve parallelism, noting that algorithmic complexity, I/O overhead, and concurrency capability are the three main performance factors. CPU trends show stagnating clock frequencies and increasing core counts, making effective multi‑core utilization essential.

Why Concurrency? Large‑scale services and machine‑learning systems require massive parallelism. Even though single‑thread performance still improves slightly via fine‑grained parallelism, the dominant way to achieve higher throughput is to exploit multiple cores.

Single‑Thread Parallel Execution

1. SIMD (Single Instruction Multiple Data) enables a single instruction to operate on multiple data elements within a wide register. The article shows Intel SIMD diagrams and explains how SIMD can provide up to 8× speedup for vectorizable workloads such as memcpy, loop vectorization, and specialized libraries (e.g., Swiss Table, simdjson, base64).

2. Out‑of‑Order Execution (OoOE) allows the CPU to execute independent instructions ahead of stalled ones. The article includes pipeline diagrams and explains how modern CPUs combine OoOE with superscalar execution to keep execution units busy.

3. TMAM (Top‑down Microarchitecture Analysis Method) uses PMU counters to locate bottlenecks in the front‑end, backend, and mis‑prediction stages. Tools like pmu‑tools automate this analysis.

Critical‑Section Protection in Multithreaded Concurrency

The article classifies protection techniques:

Mutual Exclusion – traditional mutexes (pessimistic locking) that serialize access to shared data, potentially causing global stalls.

Lock‑Free – optimistic algorithms using atomic CAS or fetch‑add. They reduce contention but may incur wasted speculative work.

Wait‑Free – guarantees that every thread completes its operation in a bounded number of steps, eliminating global stalls. Examples include ticket‑based schemes and population‑oblivious algorithms.

Experimental code snippets illustrate three approaches for a multithreaded Fibonacci‑style accumulator:

// Mutual Exclusion
::std::lock_guard<::std::mutex> lock(mutex);
sum += calc(sequence, workload);

// Lock Free / Atomic CAS
auto current = atomic_sum.load(::std::memory_order_relaxed);
auto next = current;
do {
    next = current + calc(sequence, workload);
} while (!atomic_sum.compare_exchange_weak(current, next, ::std::memory_order_relaxed));

// Wait Free / Atomic Fetch‑Add
atomic_sum.fetch_add(calc(sequence, workload), ::std::memory_order_relaxed);

Results show that the Wait‑Free fetch‑add method consistently outperforms the other two, while lock‑free offers modest gains over mutexes.

Case Studies

1. Concurrent Counter Optimization – Baidu’s bvar::IntRecorder and babylon::IntRecorder replace per‑thread locks with 128‑bit atomic loads/stores on modern x86/ARM, dramatically reducing overhead.

2. Concurrent Queue Optimization – Traditional queue locking is replaced by head/tail separation, lock‑free Michael‑Scott queues, and sharded queues (e.g., tbb::concurrent_queue ). The article also introduces babylon::ConcurrentBoundedQueue , which assigns a unique sequence number to each enqueue/dequeue operation, allowing per‑slot synchronization and achieving Wait‑Free behavior for producers.

3. Execution Queue – A specialized Wait‑Free producer queue ( bthread::ExecutionQueue ) uses a two‑step atomic swap to enqueue nodes, providing high throughput for multi‑threaded fd‑write scenarios.

Overall, the article emphasizes that while lock‑based synchronization is simple, modern high‑performance services benefit from fine‑grained atomic operations, SIMD/vectorization, and Wait‑Free designs to fully exploit CPU micro‑architectural capabilities.