多线程Threaded radixsort运行速度不及单线程的原因咨询

核心问题根因 #

如果运行环境的可用物理CPU核心数为1，所有线程都会在同一个核心上分时调度，完全无法实现并行计算，反而会新增线程创建、上下文切换的额外开销，性能自然低于无额外开销的单线程版本。调整虚拟机CPU核心配置后拿到预期加速效果，也刚好验证了这一点。

同场景下其他常见性能问题排查点 #

• 线程创建开销过高：递归过程中动态创建线程的成本很高，若子任务拆分粒度过小、创建的线程数远大于物理核心数，调度开销会完全抵消并行收益。建议改用线程池复用线程，同时设置并行拆分阈值：当子任务处理的数据量小于阈值时直接走单线程排序，不再拆分新的并行任务。
• 缓存伪共享：如果多个线程处理的内存区域相邻，频繁写入会导致CPU缓存行反复失效，大幅增加内存访问开销。可以对每个线程的局部统计变量、输出缓冲区做缓存行对齐，避免跨线程的缓存干扰。
• 串行瓶颈未优化：MSB基数排序的按位统计桶大小、桶空间分配步骤如果是串行实现，会成为并行阶段的性能瓶颈，这部分可以拆分为各线程统计各自负责区间的桶大小，再合并统计结果完成分配，尽可能消除串行逻辑。
• 并行深度设置不合理：你当前设置的递归深度为log2(n)，这里的n建议匹配物理CPU核心数而非数据量，避免创建过多无用线程增加调度负担。

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