无等待 SPSC 队列
Wait Free Spsc Queue
题目详情
在高频交易系统中，行情线程与策略线程之间的通信必须以极低延迟进行。传统锁或阻塞队列会引入不可预测的延迟和上下文切换，这是不可接受的。严格的 wait-free 单生产者单消费者（SPSC）队列确保生产者和消费者都能在有限步骤内完成操作，不受其他线程行为影响。
任务：实现 wait-free SPSC 队列，使用原子索引和预分配环形缓冲区。push() 和 pop() 操作均为 O(1) wait-free，使用 relaxed/acquire/release 内存序保证正确性。
英文原题
In high-frequency trading systems, communication between the market data thread and the trading strategy thread must occur with minimal latency. Traditional locks or blocking queues introduce unpredictable delays and context switches, which are unacceptable. A strictly wait-free Single-Producer Single-Consumer (SPSC) queue ensures that both the producer and consumer can complete their operations in a bounded number of steps, completely avoiding locks or blocking.
Task
Implement a bounded, stric
解析
问题分析
无等待 SPSC 队列保证每个操作在有限步数内完成（比无锁更强）。通过为生产者和消费者分配独立槽位避免 CAS 重试。适合单线程向单线程传递订单/成交数据的场景。
实现
template<typename T, size_t N>
class WaitFreeSPSC {
static_assert((N & (N-1)) == 0, "N must be power of 2");
std::array<std::atomic<T*>, N> buf_{};
std::atomic<size_t> w_{0}, r_{0};
public:
bool push(T* v) {
size_t w = w_.load(std::memory_order_relaxed);
if (w - r_.load(std::memory_order_acquire) >= N) return false;
buf_[w & (N-1)].store(v, std::memory_order_release);
w_.store(w + 1, std::memory_order_release);
return true;
}
T* pop() {
size_t r = r_.load(std::memory_order_relaxed);
if (r >= w_.load(std::memory_order_acquire)) return nullptr;
T* v = buf_[r & (N-1)].load(std::memory_order_acquire);
r_.store(r + 1, std::memory_order_release);
return v;
}
};复杂度与边界
- 时间复杂度：push/pop O(1)，无 CAS 重试循环
- 空间复杂度：O(N * sizeof(T*))
- 边界条件：(1) 仅单生产者单消费者 (2) N 必须为 2 的幂 (3) 空/满通过位置差判断
英文解析
Analysis
A wait-free SPSC queue guarantees each operation completes in a bounded number of steps (stronger than lock-free). By assigning independent slots to the producer and consumer, CAS retries are avoided. This suits single-thread-to-single-thread order/trade data transfer scenarios.
Solution
template<typename T, size_t N>
class WaitFreeSPSC {
static_assert((N & (N-1)) == 0, "N must be power of 2");
std::array<std::atomic<T*>, N> buf_{};
std::atomic<size_t> w_{0}, r_{0};
public:
bool push(T* v) {
size_t w = w_.load(std::memory_order_relaxed);
if (w - r_.load(std::memory_order_acquire) >= N) return false;
buf_[w & (N-1)].store(v, std::memory_order_release);
w_.store(w + 1, std::memory_order_release);
return true;
}
T* pop() {
size_t r = r_.load(std::memory_order_relaxed);
if (r >= w_.load(std::memory_order_acquire)) return nullptr;
T* v = buf_[r & (N-1)].load(std::memory_order_acquire);
r_.store(r + 1, std::memory_order_release);
return v;
}
};Complexity & Edge Cases
- Time complexity: push/pop O(1), no CAS retry loops
- Space complexity: O(N x sizeof(T*))
- Edge cases: (1) Only single-producer single-consumer (2) N must be a power of 2 (3) Empty/full detected via position difference
Verification
Single producer pushes N items, single consumer pops N items. Verify no item loss, no double-pop, and correct empty/full behavior at boundaries.
Key Considerations
Wait-free progress guarantee is stronger than lock-free - no thread can ever block another. In kernel-bypass trading pipelines where a feed handler thread produces market events and a strategy thread consumes them, wait-free SPSC ensures deterministic latency with no CAS retry jitter.