C语言归并排序4193790阈值及OpenMP并行性能骤降问题求解

问题1：4193790性能阈值的原因 #

1. merge函数实现存在严重的性能缺陷：你每次合并两个子数组时，都申请了整个原始数组大小的临时内存（参数size是数组总长度N），而非仅申请待合并的两个子数组总长度的内存。虽然你实际读写的只有子数组对应的区间，但每次都要申请、释放N大小的内存块，申请大内存块的开销本身也远高于申请小块内存，产生了大量不必要的性能消耗。
2. 4193790个double类型元素的总大小为 4193790 * 8 ≈ 32MB，刚好达到你CPU的三级缓存（L3 Cache）容量上限：
   • N小于阈值时，整个原始数组+临时申请的内存都能完全放在L3缓存中，内存存取延迟仅几纳秒，性能表现优异
   • N超过阈值后，数据无法全部放进缓存，所有读写操作都要访问主存，主存延迟是L3缓存的100倍以上，再叠加错误的merge实现带来的额外内存开销，耗时直接出现数量级上涨。

问题2：超过阈值后OpenMP版本性能下降的原因 #

当数组大小超过L3缓存容量后，程序的性能瓶颈已经从CPU计算转为内存带宽和访问延迟，此时并行化反而会引入额外的性能损耗，核心原因有三个：

1. 主存带宽是所有CPU核心共享的有限资源，4个线程同时读写主存会产生严重的带宽竞争，反而会降低整体内存访问效率
2. OpenMP的task调度本身存在固定开销，当内存成为瓶颈时，调度开销的占比会被大幅放大，进一步拉低性能
3. 多线程场景下频繁申请、释放大内存块，会触发内存分配器的全局锁竞争，新增大量不必要的等待开销。
   多个负面因素叠加后，就出现了并行版本比串行版本慢3倍的现象。

优化建议 #

• 优先修正merge函数实现：每次合并两个子数组时，仅申请两个子数组总长度的临时内存，或者提前在排序入口申请好一个全局临时数组复用，彻底避免频繁申请释放大内存的开销，让归并排序的时间复杂度回归正常的O(nlogn)水平。
• 调整OpenMP的任务切分阈值，把当前的10000适当调大，减少task生成数量，降低调度开销。
• 如果需要稳定处理超过L3缓存大小的数组，可以进一步优化内存访问模式，提升缓存命中率，降低主存访问压力。

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