六核机器上Haskell并行数独求解性能提升甚微的原因排查

核心可能原因及排查方向 #

1. ST monad的单线程绑定限制

ST monad的状态是线程局部的，runST强制绑定到单个执行线程。如果你的并行任务是在ST上下文内部启动，或者多个求解任务共享同一个ST状态，GHC会自动将这些任务串行化到同一个线程执行——这直接导致多核完全无法发挥作用。

• 检查代码：若数独求解逻辑嵌套在ST中，且并行化操作（如par/策略）是在ST内部调用，必须重构为每个并行求解任务独立调用runST，再对这些独立的runST结果做并行评估。

2. 任务粒度与负载不均衡

回溯法的任务拆分如果过细，线程调度开销会抵消并行收益；若初始分支的计算量差异极大（比如部分分支很快剪枝，部分分支需深度回溯），会导致多数核心长期空闲。

• 调整拆分策略：不要硬拆6个任务，而是基于初始数独的前几个空单元格的所有候选值组合，生成粗粒度任务（比如10-20个），确保每个任务的计算时间远大于调度开销；同时监控各任务的执行时间，避免负载倾斜。

3. 并行策略与编译运行参数错误

• 确认编译参数是否包含-threaded -rtsopts，运行时是否指定+RTS -N6——缺少这些参数，GHC默认以单线程模式运行。
• 检查并行策略的应用：若使用Control.Parallel.Strategies，需确保策略作用在实际需要计算的结果上，且正确触发WHNF评估。例如，使用using parList rseq而非仅标注策略却不强制评估；若用par，需配合pseq确保主线程等待结果时，子线程已完成计算。

4. 内存竞争与GC开销

若多个线程频繁访问共享内存结构（如全局候选值表），会引发缓存一致性开销；若每个求解任务生成大量临时数据，多核下GC的同步开销会被放大，导致性能下降。

• 查看Threadscope图：若存在大量Blocked on MVar/Blocked on blackhole状态，说明任务存在不必要的依赖；若GC时间占比过高，需优化数据结构，减少临时内存分配。

快速验证步骤 #

1. 把单个求解任务的runST调用独立出来，用par并行评估多个独立的runST结果，验证是否能触发多线程执行。
2. 用+RTS -s运行程序，查看Parallel GC work balance和Total time指标，确认多核是否实际参与计算。
3. 在Threadscope中检查是否有多个线程处于RUNNING状态，若只有一个线程在执行计算，说明并行未正确触发。

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