Skip to main content

Loading the code workspace…

LC

Implement a Wait-Free Counter

hard8/8

Implement Epoch-Based Memory Reclamation for Lock-Free Data StructuresNext

Language

Compiler

2.0s Limit 256MB

Submit and pass all tests to enable saving to GitHub.

Implementation

Implement a wait-free counter and compare it to lock-free and mutex-based approaches.

Requirements:

Implement wait-free counter using atomic fetch_add
Implement lock-free counter using CAS retry loop
Implement mutex-based counter for comparison
Run all three with multiple threads and measure latency
Show that wait-free has bounded latency per operation
Calculate percentiles (p50, p99, p999) for each approach
Print results comparing throughput and tail latency
Explain why fetch_add is wait-free on x86

Test:

Show wait-free counter increments
Show lock-free counter increments
Show comparison results
Show latency percentiles

Why This Matters

x86's LOCK XADD makes fetch_add wait-free in hardware, which is exactly why atomic reference counts in shared_ptr and Rust's Arc rely on it instead of a CAS retry loop for their hot path. Wait-freedom matters most for tail latency in real-time and low-latency trading systems, where Maurice Herlihy's original wait-free universal construction work showed that bounding worst-case latency, not just average throughput, is what separates a system that meets a hard deadline from one that occasionally doesn't.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0

← Implement Epoch-Based Memory Reclamation for Lock-Free Data Structures