std::deque不适合工作窃取队列，因其内存不连续、节点跳转开销大且无真正无锁支持；高性能实现需用2的幂环形缓冲区+分离原子索引（top_/bottom_），避免false sharing并确保本地操作完全无锁。
为什么 std::deque 不适合做工作窃取队列
因为 std::deque 的两端操作虽为均摊 O(1)，但底层内存不连续、节点跳转开销大，且缺乏无锁（lock-free）支持；工作窃取要求「本地线程高频 push/pop 本端」+「其他线程低频 steal 从对端」，std::deque 的互斥锁或内部同步机制会成为瓶颈。真实高性能实现必须自己管理环形缓冲区 + 原子索引，且分离「本地访问路径」和「跨线程 steal 路径」。
常见错误是直接包装 std::deque 加一把 std::mutex —— 这本质是串行化，并发度归零；更隐蔽的坑是用 std::atomic 操作 deque 的 size 或指针，但没处理 ABA 问题或边界竞争，导致 pop 返回空任务却实际未空。
- 本地 push/pop 必须完全无锁，仅靠两个原子整数（
top_和bottom_）驱动 - steal 操作需先读
bottom_再读top_，且用 compare_exchange_weak 防止被 push 干扰 - 缓冲区大小必须是 2 的幂，才能用位运算替代取模，避免分支和除法
如何用数组 + 原子索引实现 lock-free 双端队列
核心是维护一个固定大小的 std::array<task n></task>（N 为 2 的幂），配合两个 std::atomic<size_t></size_t>：一个 bottom_（本地线程写入位置，可递增），一个 top_（steal 线程读取起始位置，只由 steal 线程 CAS 更新）。
本地 push 使用 bottom_.fetch_add(1) 获取 slot，再写入；本地 pop 先读 bottom_ 得到当前尾，再检查是否 > top_，若成立则原子减 bottom_ 并取值——注意此处要二次校验 top_ ，防止竞态下 top 已推进但 bottom 尚未回退。
立即学习“C++免费学习笔记（深入）”；
steal 操作最易出错：必须先读 bottom_（宽松加载），再读 top_（获取加载），然后尝试用 CAS 把 top_ 从 old_top 推进到 old_top + 1，仅当成功才取 array[old_top & (N-1)]。失败说明本地线程刚 pop 了它，或另一 steal 线程抢先拿走。
// 简化 steal 片段
size_t b = bottom_.load(std::memory_order_acquire);
size_t t = top_.load(std::memory_order_acquire);
if (t >= b) return nullptr;
Task* task = array_[t & (N-1)];
if (top_.compare_exchange_strong(t, t + 1)) {
return task;
}
return nullptr;
为什么 steal 失败后不能立即重试，而要让出 CPU
steal 是低频操作，但若在空队列上自旋重试（比如 while(!steal()) {}），会浪费大量 cycles，抬高延迟，还可能饿死其他线程。Linux 下典型表现是 sched_yield() 调用缺失，导致 steal 线程持续占用核心，本地线程反而得不到调度机会。
更严重的是，某些场景（如所有 worker 都在 steal）会形成“假死”：每个线程都在等别人 push，但没人真在 work。此时必须打破循环依赖。
- steal 失败后应调用
sched_yield()（Linux）或SwitchToThread()（Windows） - 也可加指数退避（如第一次 yield，第二次 sleep(0)，第三次 sleep(1)μs），但 yield 通常已足够
- 绝对不要用
std::this_thread::sleep_for(1ns)—— 实际精度远低于 1ns，且开销比 yield 大数倍
多线程下 false sharing 怎么破
top_ 和 bottom_ 若落在同一 cache line（通常 64 字节），即使一个线程只改 bottom_、另一个只读 top_，也会因 cache coherency 协议（MESI）频繁失效彼此的 line，造成性能雪崩。实测在 32 核机器上，false sharing 可使吞吐下降 40% 以上。
解决方法不是「加 padding」那么简单——padding 位置不对仍无效。必须确保 top_、bottom_、以及它们各自最常被同线程访问的邻近字段（如本地任务计数器）分属不同 cache line。
- 用
alignas(64)对齐整个结构体，再手动插入char pad[64]隔开top_和bottom_ - 不要把
top_和bottom_放在同一个 struct 里却不 padding；也不要依赖编译器自动填充 - 用
perf stat -e cache-misses验证：高 cache-miss rate + 低 IPC 是 false sharing 的强信号
真正难调的点不在算法，而在内存布局与缓存行为的耦合——哪怕逻辑全对，一行 padding 错位，性能就掉一半。
