多线程图采样算法性能排查：无锁哈希集为何慢于单线程？

问题背景 #

我正在开发一款基于多CPU核心的图采样算法，核心设计包括：

• 采用参考Preshing实现的无锁哈希集，保证跨线程样本唯一性
• 搭配带锁任务队列，线程从队列取任务并可能新增任务，直至所有任务完成

但在16核、24核机器上，单线程版本始终比多线程版本快一个数量级。已做排查：

• 用perf分析缓存，多线程的缓存引用与缺失比例和单线程相近
• 替换为无锁任务队列后性能无明显变化
• 同功能Python库速度与我的多线程版本处于同一数量级

可能的原因与排查方向 #

• 无锁哈希集的CAS冲突与伪共享
  Preshing的无锁哈希集依赖CAS操作，高并发下会出现大量CAS重试——看似无锁，实则是自旋等待消耗CPU。可以用perf stat -e cycles,instructions,cas-misses统计CAS失败次数，或者观察top的CPU使用率（如果CPU跑满但进度慢，大概率是自旋冲突）。另外，哈希桶如果没做缓存行对齐，多个线程操作相邻桶会触发缓存行失效，导致频繁同步，可给哈希桶结构体加__attribute__((aligned(64)))对齐后再测试。

• 任务粒度太小，同步开销盖过计算收益
  如果每个任务只处理极少量采样（比如1-2个节点），线程切换、队列操作的开销会远大于任务本身的计算量。单线程没有这些额外开销，自然更快。试试把任务粒度放大，比如一次处理一批采样请求，再对比性能。

• 全局哈希集的总线风暴
  即使是无锁哈希集，若每个任务都频繁访问这个全局状态，多线程会争抢内存总线带宽，导致总线风暴，反而比单线程串行访问更慢。可以统计每个线程对哈希集的操作频率，或者按节点ID分片哈希集，让每个线程负责一个分片的唯一性检查，减少跨线程竞争。

• 任务队列的调度问题
  不管带锁还是无锁队列，高并发下可能出现线程频繁唤醒却取不到任务，或者少数线程垄断队列的情况。可以给队列的取/放操作加计数日志，看每个线程处理的任务量是否均匀，或者用perf trace跟踪线程调度，观察是否有大量park/unpark操作。

• 编译器优化差异
  单线程代码更容易被编译器做激进优化（循环展开、常量传播等），而多线程代码因为内存可见性限制，编译器无法做同样优化。对比单线程和多线程版本的汇编代码，检查关键循环的优化程度，确保两者用相同的编译优化级别（比如-O3）。

内容的提问来源于stack exchange，提问作者Manatee Pink