为什么是并行的.对于这个看似容易并行的操作来说，速度较慢

本文关键字：并行 操作 速度 易并行 于这个 为什么 | 更新日期: 2023-09-27 18:25:40

我和http://AdventOfCode.com（第4天挑战）

他们的一个问题涉及取每个数字1,2,3，将其视为字符串并计算该字符串的MD5散列。该问题需要第一个（最小）数字，其MD5哈希（十六进制）以6个零开头。

我用一个简单的for解决了这个问题，但它花了大约35秒（在2012 i5 Macbook上的Win10虚拟机中运行）。

看到CPU利用率相当低，我尝试了脑海中最简单的优化——TPL，更准确地说是Parallel.For。

令我惊讶的是，（第一个）结果在42秒后被检索到，比单线程更糟糕。正如预期的那样，CPU利用率大大提高。

这是我的C#代码。注释单线程与TPL的一行或另一行。

using System;
using System.Text;
using System.Threading;
using System.Security.Cryptography;
using System.Diagnostics;
using System.Threading.Tasks;
class Program
{
    static void Main(string[] args)
    {
        Day4.P2();
    }
}
class Day4
{
    //not thread-safe, make one instance per thread
    static ThreadLocal<MD5> md5Hash = new ThreadLocal<MD5>(MD5.Create);
    public static int P2()
    {
        string input = "yzbqklnj";
        var sw = Stopwatch.StartNew();
        Action<int> checkAction = i =>
        {
            var hashBytes = md5Hash.Value.ComputeHash(Encoding.UTF8.GetBytes(input + i));
            if ( hashBytes[0] == 0 && hashBytes[1] == 0 && (hashBytes[2]) == 0 )
            {
                Console.WriteLine(i + ": " + sw.Elapsed);
            }
        };
        //for (var i = 0;; i++) { checkAction(i); }
        Parallel.For(1, int.MaxValue, checkAction);
        return 0;
    }
}

我的问题是：为什么平行版本不是绝对优越的？

它是如何在线程之间划分数据的？

PS。当在实际的Windows机器上运行时，结果是相似的，但是（预计）第一个结果是，而不是最小的（即问题的正确结果）。

为什么是并行的.对于这个看似容易并行的操作来说，速度较慢

为什么平行版本不是绝对优越的？

因为没有理由。没有保证的处理顺序。这种情况可能是，您的线程都忙于处理没有前6个字符0的数字，而顺序版本的线程在获得第一个正确数字方面比所有线程都快。

它（即TPL）是如何在线程之间划分数据的？

MSDN上没有提到确切的方法，但关键原理是负载平衡。引用MSDN关于数据并行性（任务并行库）的页面：

在后台，任务调度器根据系统资源和工作负载。如果可能，调度程序如果工作量变得不平衡。

最后，正如预期的那样，并行版本的答案是错误的，然而，我得到的并行与顺序版本的数字与您所说的大不相同。我得到了：

  • 顺序-
    • 第一个号码：9962624；运行时间：20.51秒
  • 平行-
    • 第一个号码：1343955022；运行时间：10.06秒

此外，后来，平行版本分别给出了21.7秒（9962624）、22.06秒（541160794）和23.59秒（541640646）的下一个数字。

我在这里没有什么革命性的结论，只是重申

  1. 这取决于TPL在"后台"对数据进行分区的方式
  2. 分区是如何进行的还不清楚

当所有线程以某种方式划分范围1..int.MaxValue时，行为是可以预期的。这是一个巨大的范围，所以几乎所有线程都处理大得离谱的数字。一个线程可以做有用的工作并从头开始，但即使这样也不能保证，所以结果是不可预测的。我测量了你的程序的这个时间（纠正结果的时间）：

original serial: 00:00:28.27 
original parallel: 00:00:24.53

您可以手动对分块进行编码，但有一件事需要尝试，那就是将序列定义为有序的。

int result = Enumerable.Range(1, int.MaxValue)
    //.AsParallel()
    //.AsOrdered()
    .Where(i =>
    {
        var hashBytes = md5Hash.Value.ComputeHash(Encoding.UTF8.GetBytes(input + i));
        return (hashBytes[0] == 0 && hashBytes[1] == 0 && hashBytes[2] == 0);
    }).First();
Console.WriteLine(result + ": " + sw.Elapsed);

我首先拿出了两行，使之成为连载。

enumerable serial: 00:00:26.68
ordered parallel: 00:01:53.41

这真是一个惊喜。虽然第一个数字实际上很快就找到了（在Where条件下，可以在大约9.2秒内打印到控制台），但事实证明，引擎不会合并结果，直到每个线程都返回至少一个值（或者可能是按顺序运行）。所以大多数时候我们都在等待最慢的线程找到它的值。但是将Console.WriteLine返回到Where条件将返回订单问题。虽然结果是有保证的，但处理顺序却不是。

最后，分块并不是那么难的

const int chunkSize = 100000;
int result = int.MaxValue;
object foundLock = new object();
for (int chunk = 1; chunk < int.MaxValue; chunk += chunkSize)
{
    Parallel.For(chunk, chunk + chunkSize, (i) =>
      {
          var hashBytes = md5Hash.Value.ComputeHash(Encoding.UTF8.GetBytes(input + i));
          if (hashBytes[0] == 0 && hashBytes[1] == 0 && hashBytes[2] == 0)
          {
              lock (foundLock)
              {
                  result = Math.Min(result, i);
              }
          }
      });
    if (result < int.MaxValue)
    {
        Console.WriteLine(result + ": " + sw.Elapsed);
        break;
    }
}

结果时间

chunked parallel: 00:00:08.85

它是如何在线程之间划分数据的？

这是关键问题。未指定此项。它很可能会巧合地首先检查坏数字。也许，你也得到了一个错误的答案，因为你可能不一定得到尽可能小的i，只是任何一个。

我会这样做：处理大块的数字，比如说，每个大约10000个。一旦发现匹配，就中止对比具有匹配的块大的所有块的处理。你可能会找到更多的小火柴，必须选择最小的一个。

我不太确定如何用TPL最好地实现这一点。Parallel.ForEach循环可以中止，但我不知道它们是否可以可靠地排序。可能

尝试在每次迭代中调用Console.WriteLine(...)。你可能会看到一些至少和我在机器上看到的一样有趣的东西。。。

2: 00:00:00.0030730
1: 00:00:00.0031281
1073741824: 00:00:00.0033078
1073741825: 00:00:00.0080216
1073741826: 00:00:00.0080340
1073741827: 00:00:00.0080457
...
1073745189: 00:00:00.0663925
1073745190: 00:00:00.0664038
1073745191: 00:00:00.0664155
85: 00:00:00.0489811
86: 00:00:00.0666171
87: 00:00:00.0666364
...
40451: 00:00:01.1846214
1073753653: 00:00:01.1846293
40452: 00:00:01.1846365
1073753654: 00:00:01.1846440
40453: 00:00:01.1846527
1073753655: 00:00:01.1846633
40454: 00:00:01.1846750
... etc.

循环计数器可以快速增加，但由于更多的计算无法跟上，您可能会看到以看似任意的顺序测试的各种值。

按照usr的建议，分块测试（块不需要大于系统上的内核数量）是利用多线程处理的一个想法，但请记住，这样做会破坏算法的逻辑正确性。按指定顺序运行测试不是多线程解决方案可以保证的。

随着操作的增长，并行化是有意义的，如果每个操作要做的工作真的很小，那么在并行化时可能会变得更慢，因为拥有更多线程和在它们之间切换所增加的成本可能高于使用多个CPU所节省的成本。

为了测试这一点，如果您执行以下操作，是否会得到类似的结果：将int.MaxValue更改为int.MaxValue/1000，并用a包装lambda的INSIDE（如果j=1到1000），以确保一个单位的工作量是1000倍，从而减少了调度更少任务的时间，并增加了每个任务的"投入"时间。

根据你得到的结果，我们将能够得出一些结论。

相关文章：