并行框架和避免错误共享

最近，我回答了一个关于优化可能的并行方法来生成任意基数的每个排列的问题。我发布了类似的答案并行化，实施不佳代码块列表，有人几乎立即指出了这一点：

这几乎肯定会给你带来错误的共享，并且可能会慢很多倍。 （归功于gjvdkamp https://stackoverflow.com/users/65747/gjvdkamp)

他们是对的，那就是death慢的。也就是说，我研究了这个话题，发现了一些有趣的材料和建议 http://download.microsoft.com/download/3/a/7/3a7fa450-1f33-41f7-9e6d-3aa95b5a6aea/MSDNMagazine2008_10en-us.chm（仅存档 MSDN 杂志，.NET 问题：错误共享）来对抗它。如果我理解正确的话，当线程访问连续内存时（也就是说，可能支持该内存的数组）ConcurrentStack），可能会出现虚假共享。

对于水平线下方的代码，aBytes is:

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 as 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优化。

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

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

使用时Parallel.For() and Parallel.ForEach(), you cannot只需在线替换for or foreach和他们一起循环。这并不是说它不能是盲目的改进，但如果不检查问题并对其进行检测，使用它们就会在问题上投入多线程，因为它可能会使问题变得更快。

**Parallel.For() and 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 and localFinally拉姆达。请注意，我不建议使用并行化来实现 1 到 100 的求和，而只是举一个简单的示例来简化示例。