并行框架并避免错误共享

Question

最近,我回答了一个关于优化可能的可并行化方法来生成任意基数的每个排列的问题.我发布了类似于Parallelized,糟糕的实现代码块列表的答案,有人几乎立即指出了这一点:

这几乎可以保证为您提供错误的共享,并且可能会慢很多倍.(信用gjvdkamp)

他们是对的,死亡很慢.也就是说,我研究了这个主题,并找到了一些有趣的材料和建议(仅存档的MSDN杂志,.NET Matters:False Sharing)来对抗它.如果我理解正确,当线程访问连续的内存(例如,可能支持该数组的数组ConcurrentStack)时,可能会发生错误共享.

---

对于横向规则下面的代码,a Bytes是:

struct Bytes {
  public byte A; public byte B; public byte C; public byte D;
  public byte E; public byte F; public byte G; public byte H;
}

对于我自己的测试,我想获得这个运行的并行版本并且真正更快,所以我创建了一个基于原始代码的简单示例.6因为limits[0]是我的一个懒惰的选择-我的电脑有6个核心.

单线程块 平均运行时间:10s0059ms

  var data = new List<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  for (byte a = 0; a < limits[0]; a++)
  for (byte b = 0; b < limits[1]; b++)
  for (byte c = 0; c < limits[2]; c++)
  for (byte d = 0; d < limits[3]; d++)
  for (byte e = 0; e < limits[4]; e++)
  for (byte f = 0; f < limits[5]; f++)
  for (byte g = 0; g < limits[6]; g++)
  for (byte h = 0; h < limits[7]; h++)
    data.Add(new Bytes {
      A = a, B = b, C = c, D = d, 
      E = e, F = f, G = g, H = h
    });

并行化,执行不佳 运行时间平均值:81s729ms,~8700个争用

  var data = new ConcurrentStack<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For(0, limits[0], (a) => {
    for (byte b = 0; b < limits[1]; b++)
    for (byte c = 0; c < limits[2]; c++)
    for (byte d = 0; d < limits[3]; d++)
    for (byte e = 0; e < limits[4]; e++)
    for (byte f = 0; f < limits[5]; f++)
    for (byte g = 0; g < limits[6]; g++)
    for (byte h = 0; h < limits[7]; h++)
      data.Push(new Bytes {
        A = (byte)a,B = b,C = c,D = d,
        E = e,F = f,G = g,H = h
      });
  }); 

并行化,?? 实现 运行时平均值:5s833ms,92个争用

  var data = new ConcurrentStack<List<Bytes>>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For (0, limits[0], () => new List<Bytes>(), 
    (a, loop, localList) => { 
      for (byte b = 0; b < limits[1]; b++)
      for (byte c = 0; c < limits[2]; c++)
      for (byte d = 0; d < limits[3]; d++)
      for (byte e = 0; e < limits[4]; e++)
      for (byte f = 0; f < limits[5]; f++)
      for (byte g = 0; g < limits[6]; g++)
      for (byte h = 0; h < limits[7]; h++)
        localList.Add(new Bytes {
          A = (byte)a, B = b, C = c, D = d,
          E = e, F = f, G = g, H = h
        });
      return localList;
  }, x => {
    data.Push(x);
  });

我很高兴我有一个比单线程版本更快的实现.我预计结果接近10s/6左右,或大约1.6秒,但这可能是一个天真的期望.

我的问题是并行实现实际上比单线程版本更快,是否有进一步的优化可以应用于操作？我想知道与并行化相关的优化,而不是用于计算值的算法的改进.特别:

• 我知道存储和填充的优化struct代替byte[],但它与并行化无关(或者是它？)
• 我知道使用纹波进位加法器可以延迟评估所需的值,但与struct优化相同.

Answer 1

首先，我最初的假设Parallel.For()是Parallel.ForEach()错误的。

糟糕的并行实现很可能有 6 个线程都试图同时写入一个线程CouncurrentStack()。使用线程局部变量（下面将详细解释）的良好实现每个任务仅访问共享变量一次，几乎消除了任何争用。

使用Parallel.For()and时Parallel.ForEach()，不能简单地用它们内联替换foror循环。foreach这并不是说它不能是盲目的改进，但如果不检查问题并对其进行检测，使用它们就会在问题上投入多线程，因为它可能会使问题变得更快。

**Parallel.For()并Parallel.ForEach()具有重载，允许您为它们最终创建的本地状态创建一个本地状态Task，并在每次迭代执行之前和之后运行一个表达式。

如果您有一个与Parallel.For()or并行的操作Parallel.ForEach()，那么使用此重载可能是个好主意：

public static ParallelLoopResult For<TLocal>(
    int fromInclusive,
    int toExclusive,
    Func<TLocal> localInit,
    Func<int, ParallelLoopState, TLocal, TLocal> body,
    Action<TLocal> localFinally
)

例如，调用For()对从 1 到 100 的所有整数求和，

var total = 0;

Parallel.For(0, 101, () => 0,  // <-- localInit
(i, state, localTotal) => { // <-- body
  localTotal += i;
  return localTotal;
}, localTotal => { <-- localFinally
  Interlocked.Add(ref total, localTotal);
});

Console.WriteLine(total);

localInit应该是一个初始化本地状态类型的 lambda，该类型被传递给body和localFinallylambda。请注意，我不建议使用并行化来实现 1 到 100 的求和，而只是举一个简单的示例来简化示例。