原文地址：devblogs.microsoft.com/cppblog/usi…

原文作者：devblogs.microsoft.com/cppblog/aut…

发布时间：2018年9月11日

这篇文章是一个定期的系列文章的一部分，微软这里的C++产品团队和其他客人回答我们从客户那里收到的问题。这些问题可以是与C++有关的任何问题。MSVC工具集、标准语言和库、C++标准委员会、isocpp.org、CppCon，等等。今天的帖子是由Billy O’Neal写的。

C++17在标准库中增加了对并行算法的支持，以帮助程序利用并行执行的优势来提高性能。MSVC在15.5中首次为一些算法增加了实验性支持，在15.7中删除了实验性标签。

标准中描述的并行算法的接口并没有确切地说明一个给定的工作负载是如何被并行化的。特别是，该接口旨在以一种适用于异构机器的通用形式来表达并行，允许像SSE、AVX或NEON那样的SIMD并行，像GPU编程模型中的矢量 “通道 “那样的并行，以及传统的线程并行。

我们的并行算法实现目前完全依赖于库的支持，而不是编译器的特殊支持。这意味着我们的实现将与目前消费我们标准库的任何工具一起工作，而不仅仅是MSVC的编译器。特别是，我们测试了它与Clang/LLVM和支持Intellisense的EDG版本的工作关系。

如何。使用并行算法

要使用并行算法库，你可以按照以下步骤进行。

在你的程序中找到一个你希望用平行性来优化的算法调用。好的候选算法是做O(n)以上的工作，如排序，并且在分析你的应用程序时显示为花费合理的时间。
验证你提供给算法的代码是否可以安全地进行并行化。
选择一个并行的执行策略。执行策略将在下面描述）。
如果你还没有，#include <execution>以使并行执行策略可用。
将其中一个执行策略作为算法调用的第一个参数加入到并行化中。
对结果进行基准测试，以确保并行版本是一种改进。并行化并不总是更快，特别是对于非随机访问的迭代器，或者当输入规模较小时，或者当额外的并行性对外部资源（如磁盘）造成争夺时。

为了举例说明，这里有一个我们想使之更快的程序。它计算出对一百万个双数进行排序所需的时间。

// compile with:
//  debug: cl /EHsc /W4 /WX /std:c++latest /Fedebug /MDd .\program.cpp
//  release: cl /EHsc /W4 /WX /std:c++latest /Ferelease /MD /O2 .\program.cpp
#include <stddef.h>
#include <stdio.h>
#include <algorithm>
#include <chrono>
#include <random>
#include <ratio>
#include <vector>

using std::chrono::duration;
using std::chrono::duration_cast;
using std::chrono::high_resolution_clock;
using std::milli;
using std::random_device;
using std::sort;
using std::vector;

const size_t testSize = 1'000'000;
const int iterationCount = 5;

void print_results(const char *const tag, const vector<double>& sorted,
                   high_resolution_clock::time_point startTime,
                   high_resolution_clock::time_point endTime) {
  printf("%s: Lowest: %g Highest: %g Time: %fms\n", tag, sorted.front(),
         sorted.back(),
         duration_cast<duration<double, milli>>(endTime - startTime).count());
}

int main() {
  random_device rd;

  // generate some random doubles:
  printf("Testing with %zu doubles...\n", testSize);
  vector<double> doubles(testSize);
  for (auto& d : doubles) {
    d = static_cast<double>(rd());
  }

  // time how long it takes to sort them:
  for (int i = 0; i < iterationCount; ++i)
  {
    vector<double> sorted(doubles);
    const auto startTime = high_resolution_clock::now();
    sort(sorted.begin(), sorted.end());
    const auto endTime = high_resolution_clock::now();
    print_results("Serial", sorted, startTime, endTime);
  }
}
复制代码

并行算法取决于可用的硬件并行性，因此确保在你关心的硬件上进行测试。你不需要很多内核来显示胜利，而且许多并行算法是分而治之的问题，无论如何都不会随着线程数的增加而显示出完美的扩展性，但更多还是更好。为了这个例子的目的，我们在英特尔7980XE系统上进行了测试，该系统有18个内核和36个线程。在该测试中，该程序的调试和发布版本产生了以下输出。

.\debug.exe
Testing with 1000000 doubles…
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 310.176500ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 304.714800ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 310.345800ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 303.302200ms
Serial: Lowest: 1349 Highest: 4.29497e+09 Time: 290.694300ms

C:\Users\bion\Desktop> .\release.exe
Testing with 1000000 doubles…
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 74.590400ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 75.703500ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 87.839700ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 73.822300ms
Serial: Lowest: 2173 Highest: 4.29497e+09 Time: 73.757400ms
复制代码

接下来，我们需要确保我们的排序调用是安全的，可以并行化。如果 “元素访问函数”–也就是迭代器操作、谓词以及你要求算法代表你做的其他任何事情都遵循正常的 “任意数量的读者或最多一个写者 “的数据竞赛规则，那么算法的并行化是安全的。此外，它们必须不抛出异常（或者抛出的异常很少，以至于在它们抛出时终止程序是可以的）。

接下来，选择一个执行策略。目前，该标准包括并行策略，由std::execution::par表示，以及并行无序列策略，由std::execution::par_unseq表示。除了并行策略所暴露的要求外，并行无序策略还要求你的元素访问函数能够容忍比并发的前向进度保证更弱的内容。这意味着它们不加锁或以其他方式执行需要线程并发执行以取得进展的操作。例如，如果一个并行算法在GPU上运行并试图取得一个自旋锁，在自旋锁上旋转的线程可能会阻止GPU上的其他线程执行，这意味着持有自旋锁的线程可能永远不会解锁，从而使程序陷入死锁。你可以在C++标准的[algorithms.parallel.defns]和[algorithms.parallel.exec]部分阅读更多关于具体的要求。如果有疑问，请使用并行策略。在这个例子中，我们使用的是不需要任何锁的内置双倍小于运算符，以及标准库提供的迭代器类型，所以我们可以使用并行的无序策略。

请注意，Visual C++的实现以同样的方式实现了并行和并行不排序策略，所以你不应该期望在我们的实现上使用par_unseq来获得更好的性能，但是有一天可能存在可以使用这种额外自由的实现。

在上面的双打排序例子中，我们现在可以添加

#include <execution>
复制代码

到我们程序的顶部。由于我们使用的是并行无序策略，所以我们将std::execution::par_unseq添加到算法调用位置。(如果我们使用的是并行策略，我们将使用std::execution::par来代替。) 有了这个改变，main中的for循环就变成了下面的样子。

for (int i = 0; i < iterationCount; ++i)
{
  vector<double> sorted(doubles);
  const auto startTime = high_resolution_clock::now();
  // same sort call as above, but with par_unseq:
  sort(std::execution::par_unseq, sorted.begin(), sorted.end());
  const auto endTime = high_resolution_clock::now();
  // in our output, note that these are the parallel results:
  print_results("Parallel", sorted, startTime, endTime);
}
复制代码

最后，我们进行基准测试。

.\debug.exe
Testing with 1000000 doubles…
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 54.815300ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.613700ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.504200ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.194200ms
Parallel: Lowest: 6642 Highest: 4.29496e+09 Time: 49.162200ms

.\release.exe
Testing with 1000000 doubles…
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 20.971100ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 17.510700ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 17.823800ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 20.230400ms
Parallel: Lowest: 18889 Highest: 4.29496e+09 Time: 19.461900ms
复制代码

结果是，对于这个输入，程序的速度更快。你如何对你的程序进行基准测试将取决于你自己的成功标准。并行化确实有一些开销，如果N足够小的话，会比串行版本慢，这取决于内存和缓存的影响，以及其他针对你特定工作负载的因素。在这个例子中，如果我把N设置为1000，并行和串行版本的运行速度大致相同，如果我把N改成100，串行版本的速度就会快10倍。并行化可以带来巨大的胜利，但选择在哪里应用它是很重要的。

并行算法的MSVC实现的当前局限性

我们建立了并行反向，在我们的测试硬件上它比串行版本慢了1.6倍，即使是大的N值。这并不意味着标准委员会在STL中加入这些算法是错误的；这只是意味着我们的实现所针对的硬件没有看到改进。因此，我们提供了签名，但实际上并没有对那些只是按顺序排列的元素进行交换、复制或移动的算法进行并行化。如果我们得到反馈，有一个并行化会更快的例子，我们将研究这些算法的并行化。受影响的算法是。

copy
copy_n
fill
fill_n
move
reverse
reverse_copy
rotate
rotate_copy
swap_ranges
复制代码

有些算法目前还没有实现，将在未来的版本中完成。我们在Visual Studio 2017 15.8中并行化的算法是。

adjacent_difference
adjacent_find
all_of
any_of
count
count_if
equal
exclusive_scan
find
find_end
find_first_of
find_if
for_each
for_each_n
inclusive_scan
mismatch
none_of
partition
reduce
remove
remove_if
search
search_n
sort
stable_sort
transform
transform_exclusive_scan
transform_inclusive_scan
transform_reduce
复制代码

MSVC的并行算法实现的设计目标

虽然标准规定了并行算法库的接口，但它根本没有说算法应该如何并行化，甚至没有说算法应该在什么硬件上并行化。一些C++的实现可以通过使用GPU或其他异构计算硬件来实现并行化，如果目标上有的话。对于我们的实现来说，复制并行化是没有意义的，但对于以GPU或类似加速器为目标的实现来说，这确实是有意义的。在我们的实现中，我们重视以下几个方面。

与平台锁的组合

微软之前推出了一个并行化框架ConcRT，它为标准库的部分内容提供了支持。ConcRT允许不同的工作负载透明地使用可用的硬件，并让线程完成彼此的工作，这可以提高整体吞吐量。基本上，每当一个线程在运行ConcRT工作负载时通常会进入睡眠状态，它就会暂停当前正在执行的工作，而运行其他准备运行的工作。这种非阻塞行为减少了上下文切换，可以产生比我们的并行算法实现所使用的Windows线程池更高的整体吞吐量。然而，这也意味着ConcRT工作负载不能与操作系统同步原语，如SRWLOCK、NT事件、semaphores、COM单线程公寓、窗口程序等组成。我们认为，对于标准库中的 “默认 “实现来说，这是一个不可接受的折衷。

标准的并行无序策略允许用户声明他们支持像ConcRT这样的轻量级用户模式调度框架的各种限制，所以我们可能会在未来考虑提供类似ConcRT的行为。然而目前，我们只有利用并行策略的计划。如果你能满足要求，你应该使用并行的非排序策略，因为这可能导致在其他实现上或未来的性能提高。

调试构建中的可用性能

我们关心的是调试性能。那些需要打开优化器才能实用的解决方案并不适合在标准库中使用。如果我在前面的例子程序中添加一个Concurrency::parallel_sort的调用，ConcRT的并行排序在发布时要快一点，但在调试时几乎慢了100倍。

for (int i = 0; i < iterationCount; ++i)
{
  vector<double> sorted(doubles);
  const auto startTime = high_resolution_clock::now();
  Concurrency::parallel_sort(sorted.begin(), sorted.end());
  const auto endTime = high_resolution_clock::now();
  print_results("ConcRT", sorted, startTime, endTime);
}
复制代码

C:\Users\bion\Desktop> .\debug.exe
Testing with 1000000 doubles…
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 23910.081300ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24096.297700ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 23868.098500ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24159.756200ms
ConcRT: Lowest: 5564 Highest: 4.29497e+09 Time: 24950.541500ms

C:\Users\bion\Desktop> .\release.exe
Testing with 1000000 doubles…
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 19.019000ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 16.348000ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.699400ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.907100ms
ConcRT: Lowest: 1394 Highest: 4.29496e+09 Time: 15.859500ms
复制代码

与系统中的其他程序和并行性框架的组合

我们的实现中的调度是由Windows系统的线程池处理的。线程池利用了标准库所不具备的信息，比如系统中的其他线程在做什么，线程在等待什么内核资源，等等。它选择何时创建更多的线程，以及何时终止它们。它也与其他系统组件共享，包括那些不使用C++的组件。

关于线程池代表你（和我们）所做的各种优化的更多信息，请查看Pedro Teixeira关于线程池的演讲，以及CreateThreadpoolWork、SubmitThreadpoolWork、WaitForThreadpoolWorkCallbacks和CloseThreadpoolWork函数的官方文档。

最重要的是，并行化是一种优化

如果我们不能想出一个实用的基准，让并行算法在合理的N值下获胜，那么它将不会被并行化。我们认为在N=1’000’000’000时速度是两倍，而在N=100时速度慢3个数量级是不可接受的折衷。如果你想要 “不计成本的并行化”，有很多其他的实现可以和MSVC一起使用，包括HPX和线程构件。

同样地，C++标准允许并行算法分配内存，并在无法获得内存时抛出std::bad_alloc。在我们的实现中，如果不能获得额外的资源，我们会退回到算法的串行版本。

为并行算法做基准测试并加速你自己的应用

需要超过O(n)时间的算法（如排序）和被调用的N大于2,000的算法是考虑应用并行的好地方。我们想确保这个功能的表现与你所期望的一样；请试一试。如果你对我们有任何反馈或建议，请告诉我们。你可以通过下面的评论、电子邮件（visualcpp@microsoft.com）联系我们，你也可以通过产品中的帮助>报告问题，或通过开发者社区提供反馈。你也可以在Twitter（@VisualC）和Facebook（msftvisualcpp）上找到我们。

本文于2018-10-31更新，以表明分区在15.8中被并行化。

通过www.DeepL.com/Translator（免费版）翻译

文章版权归作者所有，未经允许请勿转载。

THE END

代码人生