c++ - 为什么我的并行 foreach 循环实现比单线程慢？

Question

我正在尝试为 std::vector 实现并行 foreach 循环它以最佳线程数(主线程的内核数减去 1)运行计算，但是，我的实现似乎不够快——它实际上比单线程慢 6 倍!

线程实例化经常被指责为瓶颈，所以我尝试了一个更大的 vector ，但是，这似乎没有帮助。

我目前在一个单独的线程中观看并行算法在 13000-20000 微秒内执行，而单线程算法在主线程中在 120-200 微秒内执行，无法弄清楚我做错了什么。在那些 13-20 毫秒的并行算法中运行 8 或 9 次通常用于创建线程，但是，我仍然看不出 std::for_each 的原因在一个单独的线程中运行 1/3 的 vector ，运行时间比另一个线程长几倍 std::for_each需要遍历整个 vector 。

#include <iostream>
#include <vector>
#include <thread>
#include <algorithm>
#include <chrono>

const unsigned int numCores = std::thread::hardware_concurrency();

const size_t numUse = numCores - 1;

struct foreach
{
    inline static void go(std::function<void(uint32_t&)>&& func, std::vector<uint32_t>& cont)
    {
        std::vector<std::thread> vec;
        vec.reserve(numUse);
        std::vector<std::vector<uint32_t>::iterator> arr(numUse + 1);
        size_t distance = cont.size() / numUse;
        for (size_t i = 0; i < numUse; i++)
            arr[i] = cont.begin() + i * distance;
        arr[numUse] = cont.end();
        for (size_t i = 0; i < numUse - 1; i++)
        {
            vec.emplace_back([&] { std::for_each(cont.begin() + i * distance, cont.begin() + (i + 1) * distance, func); });
        }
        vec.emplace_back([&] { std::for_each(cont.begin() + (numUse - 1) * distance, cont.end(), func); });
        for (auto &d : vec)
        {
            d.join();
        }
    }
};


int main()
{
    std::chrono::steady_clock clock;
    std::vector<uint32_t> numbers;
    for (size_t i = 0; i < 50000000; i++)
        numbers.push_back(i);
    std::chrono::steady_clock::time_point t0m = clock.now();
    std::for_each(numbers.begin(), numbers.end(), [](uint32_t& value) { ++value; });

    std::chrono::steady_clock::time_point t1m = clock.now();
    std::cout << "Single-threaded run executes in " << std::chrono::duration_cast<std::chrono::microseconds>(t1m - t0m).count() << "mcs\n";
    std::chrono::steady_clock::time_point t0s = clock.now();
    foreach::go([](uint32_t& i) { ++i; }, numbers);

    std::chrono::steady_clock::time_point t1s = clock.now();
    std::cout << "Multi-threaded run executes in " << std::chrono::duration_cast<std::chrono::microseconds>(t1s - t0s).count() << "mcs\n";
    getchar();
}

有没有办法可以优化它并提高性能？

我使用的编译器是 Visual Studio 2017 的编译器。配置是版本 x86。我还被建议使用探查器，目前正在研究如何使用探查器。

实际上，我设法让并行代码比常规代码运行得更快，但是，这需要由 5 个元素组成的数十万个 vector 组成的 vector 。如果有人对如何提高性能或我在哪里可以找到更好的实现来检查其结构有任何建议，那将不胜感激。

Answer 1

感谢您提供一些示例代码。

获得好的指标(尤其是并行代码)可能非常棘手。您的指标受到污染。

使用high_resolution_clock而不是 steady_clock用于分析。

不要在计时测量中包含线程启动时间。线程启动/加入比您在这里的实际工作长几个数量级。您应该创建一次线程并使用条件变量使它们休眠，直到您发出信号让它们工作。这不是微不足道的，但重要的是不要测量线程启动时间。

Visual Studio 有一个分析器。您需要使用发布优化编译代码，但还需要包含调试符号(默认发布配置中不包括这些符号)。我没有研究如何手动设置它，因为我通常使用 CMake，它会自动设置 RelWithDebInfo 配置。

另一个与拥有良好指标相关的问题是您的“工作”只是增加一个整数。这真的代表了您的程序将要进行的工作吗？增量真的很快。如果您查看由您的顺序版本生成的程序集，所有内容都会内联到一个非常短的循环中。

Lambda 很有可能被内联。但是在您的 go函数，您将 lambda 转换为 std::function . std::function被内联的机会非常小。
所以如果你想保持内联 lambda 的机会，你必须做一些模板技巧:

template <typename FUNC>
inline static void go(FUNC&& func, std::vector<uint32_t>& cont)

通过手动内联您的代码(我将 go 函数的内容移动到 main )并执行上面的步骤 2，我能够获得并行版本(超线程双核上的 4 个线程)以大约 75 ％ 的时间。这不是特别好的缩放，但考虑到原版已经相当快，这还不错。为了进一步优化，我将使用 SIMD 又名“vector ”(不同于 std::vector，除了它们都与数组有关)操作，它将在一次迭代中将增量应用于多个数组元素。

您在这里有一个竞争条件:

for (size_t i = 0; i < numUse - 1; i++)
{
    vec.emplace_back([&] { std::for_each(cont.begin() + i * distance, cont.begin() + (i + 1) * distance, func); });
}

因为您将默认 lambda 捕获设置为按引用捕获，i变量是一个引用，这可能会导致某些线程检查错误的范围或范围太长。你可以这样做:[&, i] ，但为什么要冒险再次开枪打自己的脚呢？ Scott Meyers 建议不要使用默认捕获模式。就做[&cont, &distance, &func, i]
更新:

我认为移动您的foreach 是个好主意到自己的空间。我认为您应该做的是将线程创建与任务分派(dispatch)分开。这意味着您需要某种信号系统(通常是条件变量)。您可以查看线程池。

添加线程池的一种简单方法是使用 OpenMP，Visual Studio 2017 支持 (OpenMP 2.0)。需要注意的是，不能保证在并行部分的进入/退出期间不会创建/销毁线程(它取决于实现)。因此，它权衡了性能和易用性。

如果可以使用 C++17，它有一个标准的并行 for_each (ExecutionPolicy 过载)。大多数算法标准函数都可以。 https://en.cppreference.com/w/cpp/algorithm/for_each

至于使用std::function您可以使用它，只是不希望您的基本操作(将被调用 50,000,000 次)成为 std::function .

坏的:

void go(std::function<...>& func)
{
    std::thread t(std::for_each(v.begin(), v.end(), func));
    ...
}

...
go([](int& i) { ++i; });

好的:

void go(std::function<...>& func)
{
    std::thread t(func);
    ...
}

...
go([&v](){ std::for_each(v.begin(), v.end(), [](int& i) { ++i; })});

在好的版本中，短的内部 lambda(即++i)在对 for_each 的调用中被内联。这很重要，因为它被调用了 5000 万次。对更大 lambda 的调用不是内联的(因为它已转换为 std::function )，但这没关系，因为每个线程只调用一次。