C++17并行算法的惊人性能，这可能吗？

随着C++17中并行算法的加入，你现在可以轻松地更新你的“计算”代码以受益于并行执行。在本文中，我想探讨一个自然地揭示独立计算思想的STL算法。如果你的机器有10核CPU，你总是能期望获得10倍的加速吗？也许更多？也许更少？让我们来探讨一下这个话题。

并行算法简介

C++17为大多数算法提供了执行策略参数

• sequenced_policy - 是一种执行策略类型，用作唯一类型来消除并行算法重载的歧义，并要求并行算法的执行不得并行化。
  • 相应的全局对象是std::execution::seq
• parallel_policy - 是一种执行策略类型，用作唯一类型来消除并行算法重载的歧义，并指示并行算法的执行可以并行化。
  • 相应的全局对象是std::execution::par
• parallel_unsequenced_policy - 是一种执行策略类型，用作唯一类型来消除并行算法重载的歧义，并指示并行算法的执行可以并行化和向量化。
  • 相应的全局对象是std::execution::par_unseq

简而言之

• 使用std::execution::seq以串行方式执行你的算法
• 使用std::execution::par并行执行你的算法（通常使用一些线程池实现）
• 使用std::execution::par_unseq并行执行你的算法，同时还能使用向量指令（如SSE、AVX）

举个简单的例子，你可以并行调用std::sort

std::sort(std::execution::par, myVec.begin(), myVec.end());
       // ^^^^^^^^^^^^^^^^^^^
       // execution policy

请注意，只需为算法添加并行执行参数就这么简单！但你总能体验到巨大的性能提升吗？它总是更快吗？或者，在某些情况下，它可能会减慢速度？

并行std::transform

在这篇文章中，我想看看std::transform算法，它可能是其他并行技术（以及std::transform_reduce、for_each、scan、sort…）的构建块之一。

我们的测试代码将围绕以下模式展开

std::transform(execution_policy, // par, seq, par_unseq
               inVec.begin(), inVec.end(),
               outVec.begin(),
               ElementOperation);

假设ElementOperation函数不使用任何同步方法，那么代码可能具有很好的潜力进行并行执行甚至向量化。每个元素的计算都是独立的，顺序不重要，因此实现可能会生成多个线程（可能在线程池上）来独立处理元素。

我想测试以下情况

• 向量大小 - 大或小
• 主要花费在内存访问上的简单转换
• 更多的算术 (ALU) 操作
• 更实际场景中的ALU

如你所见，我不仅想测试适合使用并行算法的元素数量，还想测试保持CPU繁忙的ALU操作。

其他算法，如排序、累加（以std::reduce的形式），也提供并行执行，但它们需要更多工作（通常是合并步骤）来计算结果。所以它们可能是另一篇文章的候选者。

基准测试说明

我使用Visual Studio 2017，15.8进行测试——因为它是目前（2018年11月）流行的编译器/STL实现中唯一的实现（GCC正在开发中！）。此外，我只关注execution::par，因为MSVC中不提供execution::par_unseq（它与execution::par的工作方式相同）。

我有两台机器

• i7 8700 - PC，Windows 10，i7 8700 - 主频3.2 GHz，6核/12线程（超线程）
• i7 4720 - 笔记本，Windows 10，i7 4720，主频2.6GHz，4核/8线程（超线程）

代码在x64，Release模式下编译，默认启用自动向量化，并且我启用了增强指令集（SSE2）以及OpenMP（2.0）

代码位于我的github上

• github/fenbf/ParSTLTests/TransformTests/TransformTests.cpp

对于OpenMP（2.0），我只使用并行for循环

#pragma omp parallel for
for (int i = 0; ...)

我运行代码段5次，并查看最小值。

警告：结果仅用于呈现一些粗略的观察结果，在生产中使用之前请务必在您的系统/配置上运行。您的要求和环境可能与我的不同。

你可以在这篇文章中阅读更多关于MSVC实现的信息
使用C++17并行算法实现更好的性能 | Visual C++团队博客

这是Billy O’Neil在CppCon 2018上最近的演讲（Billy在MSVC中实现了并行STL）

• https://www.youtube.com/watch?v=nOpwhTbulmk

好的，让我们从一些基本示例开始！

简单转换

考虑一种情况，你对输入向量应用一个非常简单的操作。它可能是一个元素的复制或乘法。

例如

std::transform(std::execution::par,
               vec.begin(), vec.end(), out.begin(),
               [](double v) { return v * 2.0; }
);

我的机器有6或4个核心……我能期望获得串行执行的4…6倍性能吗？

以下是结果（时间单位为毫秒）

操作 (Operation)	向量大小	i7 4720 (4核)	i7 8700 (6核)
execution::seq	1万	0.002763	0.001924
execution::par	1万	0.009869	0.008983
openmp parallel for	1万	0.003158	0.002246
execution::seq	10万	0.051318	0.028872
execution::par	10万	0.043028	0.025664
openmp parallel for	10万	0.022501	0.009624
execution::seq	100万	1.69508	0.52419
execution::par	100万	1.65561	0.359619
openmp parallel for	100万	1.50678	0.344863

如你在更快的机器上所见，你需要大约100万个元素才能开始看到一些性能提升。另一方面，在我的笔记本上，所有并行实现都更慢。

总而言之，你可能会猜到，使用这样的转换，即使我们增加元素数量，也很难看到任何显著的加速。

为什么会这样？

由于操作是基本的，CPU核心几乎可以立即调用它，只使用几个周期。然而，CPU核心会花费更多时间等待主内存。因此，在这种情况下，它们大部分时间都在等待，而不是计算。

在内存中读写变量，如果已缓存，只需2-3个时钟周期；如果未缓存，则需数百个时钟周期。
https://www.agner.org/optimize/optimizing_cpp.pdf

我们可以粗略地观察到，如果你的算法受限于内存，那么你不能期望通过并行执行获得更好的性能。

更多计算

既然内存吞吐量至关重要并且可能会减慢速度……让我们增加影响每个元素的计算量。

我们的想法是，与其花费时间等待内存，不如更好地利用CPU周期。

首先，我将使用三角函数，例如sqrt(sin*cos)（这些是任意计算，不是最优形式，只是为了保持CPU忙碌）。

我们使用了sqrt、sin和cos，其中sqrt可能需要约20个周期，三角函数可能需要约100个周期。这种计算量可能足以弥补内存访问的延迟。

更多关于指令延迟的信息，请参阅Agner Fog的这份出色的性能指南。

这是基准测试代码

std::transform(std::execution::par, vec.begin(), vec.end(), out.begin(),
            [](double v) {
                return std::sqrt(std::sin(v)*std::cos(v));
            }
);

现在怎么样？我们能比之前的尝试获得更好的性能吗？

以下是结果（时间单位为毫秒）

操作 (Operation)	向量大小	i7 4720 (4核)	i7 8700 (6核)
execution::seq	1万	0.105005	0.070577
execution::par	1万	0.055661	0.03176
openmp parallel for	1万	0.096321	0.024702
execution::seq	10万	1.08755	0.707048
execution::par	10万	0.259354	0.17195
openmp parallel for	10万	0.898465	0.189915
execution::seq	100万	10.5159	7.16254
execution::par	100万	2.44472	1.10099
openmp parallel for	100万	4.78681	1.89017

现在，我们终于看到了一些不错的数字。:)

对于1000个元素（此处未显示），并行和串行的时间相似，因此超过1000个元素，我们可以看到并行版本的一些改进。

对于10万个元素，更快的机器比串行版本快近9倍（OpenMP版本也类似）。

对于最大的100万个元素集，它快了5倍或8倍。

对于这样的计算，我能实现与CPU核心数量“线性”的加速。这可能就是我们应该期望的。

菲涅尔与3D向量

在上面一节中，我使用了一些“虚拟”计算，但是一些实际代码呢？

让我们计算描述光在均匀平面界面处反射和折射的菲涅尔方程。这是一种在3D游戏中生成逼真照明的常用技术。

作为一个很好的参考，我找到了这个很棒的描述和实现
着色简介（反射、折射和菲涅尔） @scratchapixel.com

关于使用GLM库

我没有创建自己的实现，而是使用了glm库。我在我的OpenGL项目中大量使用了它。

该库可以通过Conan 包管理器轻松获取，所以我也将使用它

包的链接：https://bintray.com/bincrafters/public-conan/glm%3Ag-truc

Conan文件

[requires]
glm/0.9.9.1@g-truc/stable

[generators]
visual_studio

以及安装库的命令行（它将生成一个props文件，我可以在我的Visual Studio项目中使用）。

conan install . -s build_type=Release -if build_release_x64 -s arch=x86_64

该库是仅头文件库，因此如果你愿意，也可以轻松手动下载。

实际代码和基准测试

我已根据scratchapixel.com的代码调整了glm

// implementation adapted from https://www.scratchapixel.com
float fresnel(const glm::vec4 &I, const glm::vec4 &N, const float ior)
{
    float cosi = std::clamp(glm::dot(I, N), -1.0f, 1.0f);
    float etai = 1, etat = ior;
    if (cosi > 0) { std::swap(etai, etat); }

    // Compute sini using Snell's law
    float sint = etai / etat * sqrtf(std::max(0.f, 1 - cosi * cosi));
    // Total internal reflection
    if (sint >= 1)
        return 1.0f;

    float cost = sqrtf(std::max(0.f, 1 - sint * sint));
    cosi = fabsf(cosi);
    float Rs = ((etat * cosi) - (etai * cost)) /
               ((etat * cosi) + (etai * cost));
    float Rp = ((etai * cosi) - (etat * cost)) /
               ((etai * cosi) + (etat * cost));
    return (Rs * Rs + Rp * Rp) / 2.0f;
}

代码使用了一些数学指令，点积、乘法、除法，这也能让CPU保持忙碌。我们还使用了4元素向量而不是double向量，所以内存使用量也增加了。

基准测试

std::transform(std::execution::par,
               vec.begin(), vec.end(), vecNormals.begin(),  // input vectors
               vecFresnelTerms.begin(),                     // output term
               [](const glm::vec4& v, const glm::vec4& n) {
                   return fresnel(v, n, 1.0f);
               }
 );

以下是结果（时间单位为毫秒）

操作 (Operation)	向量大小	i7 4720 (4核)	i7 8700 (6核)
execution::seq	1k	0.032764	0.016361
execution::par	1k	0.031186	0.028551
openmp parallel for	1k	0.005526	0.007699
execution::seq	1万	0.246722	0.169383
execution::par	1万	0.090794	0.067048
openmp parallel for	1万	0.049739	0.029835
execution::seq	10万	2.49722	1.69768
execution::par	10万	0.530157	0.283268
openmp parallel for	10万	0.495024	0.291609
execution::seq	100万	25.0828	16.9457
execution::par	100万	5.15235	2.33768
openmp parallel for	100万	5.11801	2.95908

通过“真实”计算，我们可以看到并行算法提供了良好的性能。在我的两台Windows机器上，对于此类操作，我可以获得几乎与核心数量呈线性关系的加速。

对于所有测试，我也向你展示了OpenMP的结果，两种实现：MSVC和OpenMP的性能似乎相似。

摘要

在文章中，我展示了三种可以开始使用并行执行和并行算法的情况。虽然用std::execution::par版本替换所有标准算法可能很诱人，但这并不总是一个好方法！你在算法内部使用的每个操作可能会有不同的性能表现，并且可能更受CPU或内存限制，这就是为什么你必须单独考虑每个更改。

要记住的事情是

• 并行执行通常会比串行版本做更多的工作，这是因为库必须准备并行执行。
• 重要的不仅是元素的数量，还有使CPU保持忙碌的指令数量。
• 最好有不相互依赖也不依赖其他共享资源的任务。
• 并行算法提供了一种将工作分派到独立线程的直接方法。
• 如果你的操作受内存限制，那么你不能期望太多的性能提升，在某些情况下，算法可能会更慢。
• 为了获得可观的性能提升，请务必测量每个问题的时间，因为在某些情况下，结果可能完全不同。

特别感谢JFT对本文的帮助！

如需更多参考，你还可以查看我关于并行算法的其他资源

• 我的《C++17详解》书中关于并行算法的新章节
• 并行STL和文件系统：文件词数统计示例
• C++17并行算法示例

请参阅另一篇与并行算法相关的文章：如何使用Intel并行STL和C++17并行算法提升性能。

轮到你了

标题中我的问题的答案是什么？我们能从并行算法中获得惊人的性能吗？

你玩过并行执行吗？它带来了预期的加速吗？

在本文中，我只触及了“简单”的并行算法——std::transform。当我们讨论std::reduce时，事情会变得更加复杂。