Parallel.For实现的函数比顺序循环慢，求原因及优化建议

我用Parallel.For实现了两个函数，但运行速度均慢于普通顺序循环版本：

• 第一个函数仅略慢于顺序版本
• 第二个函数速度直接慢了一倍

第一个函数：筛法对数累加 #

代码实现 #

static int[] sieveWithLogs(long n, long start, int intervalSize, List<int> factorBase, List<int> factorBaseLogs)
{
    int[] result = new int[intervalSize];
    Parallel.For(0, factorBase.Count, i => 
    {
        int p = factorBase[i];
        var roots = Tools.ShanksTonelliLONG(n, p);
        long r1 = roots.Item2;
        long r2 = roots.Item3;
        long root1 = r1 + p * ((start - r1) / p + 1);
        long root2 = r2 + p * ((start - r2) / p + 1);
        long index1 = root1 - start;
        long index2 = root2 - start;
        while (index1 < intervalSize)
        {
            result[index1] += factorBaseLogs[i];
            index1 += p;
        }
        while (index1 < intervalSize)
        {
            result[index2] += factorBaseLogs[i];
            index2 += p;
        }
    });
    return result;
}

功能说明 #

factorBase由若干质数组成，函数创建指定大小的int数组，将对应质数的对数添加到数组中所有符合r + p*k形式的元素上。

第二个函数：矩阵列异或加法 #

代码实现 #

static void AddColumn(int i, int j, List<bool[]> matrix)
{
    Parallel.For(0, matrix.Count, k =>
    {
        matrix[k][j] = matrix[k][j] ^ matrix[k][i];
    });
}

问题原因分析 #

1. 第一个函数：并行开销与缓存竞争 #

• 并行调度开销：Parallel.For的线程调度、上下文切换存在固定开销，如果factorBase.Count的规模不大，这些开销会抵消并行带来的收益。
• 伪共享问题：多个线程同时修改result数组的不同位置，而数组是连续内存块，当操作的位置处于同一缓存行时，会引发频繁的缓存失效，拖慢性能。
• 任务粒度不足：每个循环迭代的计算量偏小，并行额外开销占比过高，导致仅略慢于顺序版本。

2. 第二个函数：极端细粒度与严重伪共享 #

• 任务粒度极小：每个迭代仅执行一次异或操作，计算量微乎其微，线程调度、同步的开销远远超过计算本身，这是速度慢一倍的核心原因。
• 伪共享加剧：bool[]是连续内存结构，多个线程修改不同行的第j列元素时，这些元素大概率处于同一缓存行（一个64字节缓存行可容纳64个bool），导致大量缓存行失效，线程频繁等待缓存同步，性能暴跌。

结论与优化建议 #

这类操作并非完全无法高效并行，但需要针对性调整策略：

• 第一个函数优化方向：
  • 增大任务粒度：将factorBase划分为若干批次，每个线程处理一个批次，减少线程调度次数。
  • 缓解伪共享：给result数组添加缓存行对齐的填充（比如使用System.Runtime.CompilerServices.CacheLineSize控制对齐），避免不同线程操作的元素处于同一缓存行。
• 第二个函数优化方向：
  • 放弃细粒度并行：单个异或操作的计算量远低于并行开销，建议直接改用顺序循环。如果矩阵规模极大，可考虑按行块并行，每个线程处理连续的多行，既增大任务粒度，也减少缓存竞争。

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