并行框架和避免虚假共享

Question

最近，我回答了一个关于优化用于生成任意基数的每个排列的可能并行化方法的问题。我发布了一个类似于 Parallelized, poor implementation code block list 的答案，几乎立即有人指出了这一点：

This is pretty much guaranteed to give you false sharing and will probably be many times slower. (credit to gjvdkamp)

他们是对的，死亡慢。也就是说，我研究了这个主题，并找到了一些 interesting material and suggestions（仅存档 MSDN 杂志，.NET 问题：虚假共享）来打击它。如果我理解正确，当线程访问连续内存时（也就是说，可能支持 ConcurrentStack 的数组），可能会发生错误共享。

对于水平线以下的代码，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;
}

对于我自己的测试，我想得到这个运行ning 的并行版本并且真正更快，所以我创建了一个基于原始代码的简单示例。 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);
  });

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

我的问题是对于实际上比单线程版本更快的并行化实现，是否有进一步的优化可以应用于操作？我想知道关于与并行化相关的优化，而不是改进用于计算值的算法。具体来说：

我知道存储和填充为 struct 而不是 byte[] 的优化，但它与并行化无关（或者是吗？）
我知道可以使用纹波进位加法器延迟计算所需值，但与 struct 优化相同。

Answer 1

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

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

当使用 Parallel.For() 和 Parallel.ForEach() 时，您不能简单地将 for 或 foreach 循环替换为他们。这并不是说它不能盲目改进，但如果不检查问题并对其进行检测，使用它们就是将多线程扔到一个问题上，因为它可能会使它更快。

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

如果您有与 Parallel.For() 或 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 和 localFinally lambda。请注意，我不建议使用并行化实现 1 到 100 的求和，而只是提供一个简单的示例来简化示例。

并行框架和避免虚假共享

Parallel Framework and avoiding false sharing

c#

parallel-processing

performance

false-sharing