并行框架及避免虚假共享

Question

最近，我回答了一个关于优化一种可能可并行化的方法以生成任意基数数字的排列的问题。我发表了类似于并行化，低效实现代码块列表的答案，并有人几乎立即指出：

这几乎肯定会给你带来虚假共享，并且可能会慢很多倍。（归功于gjvdkamp）

他们说得对，它运行得非常慢。尽管如此，我研究了这个话题，并找到了一些有趣的材料和建议（仅存档的 MSDN 杂志，.NET Matters: False Sharing），可以用于解决这个问题。如果我理解正确，当线程访问连续内存时（比如，可能支持那个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;
}

为了进行自己的测试，我希望能够运行一个并行版本，并且确实更快，因此我基于原始代码创建了一个简单的示例。 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
    });

并行化的，糟糕的实现 平均运行时间：81秒729毫秒，~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
      });
  }); 

并行化，?? 实现 平均运行时间：5秒833毫秒，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并进行填充的优化，但它与并行化无关（还是有关系的？）
• 我知道使用Ripple-Carry加法器可以进行惰性求值，但与struct优化相同。

- jdphenix

---

你最好在程序员板块发布这个问题，或者更好的方式是将其作为高尔夫挑战。 - lloyd

@lloydm，把这个问题放在stackoverflow上有什么问题吗？这里至少有一些有趣、具有挑战性的问题，而不仅仅是一百万个错误消息或语法问题。 - Prokurors

@Prokurors 毫无疑问，这很有趣且具有挑战性。我学到了关于虚假共享的知识。再次阅读有效的问题后，我同意它符合一个有效问题的标准。 - lloyd

投票者，我该如何改进我的问题？ - jdphenix

你的实现对于List也不是最优的。你确切地知道列表中需要多少元素，因此你可以在构造函数中设置容量并防止不必要的分配。 - Mike Zboray

@mikez 这是一个很棒的优化，它将运行时间平均值缩短到了1秒689毫秒 - 这可能是最快的速度了。 - jdphenix

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 的求和，这只是为了让示例更加简短。

- jdphenix