c++ - std::copy_n 中的执行策略的真正含义是什么？

Question

我刚刚发现 std::copy_n 为不同的执行策略提供了重载。但我发现cppreference这里很难理解，因为(我想)它非常笼统。所以我很难将实际发生的情况整合在一起。

1. 我不太明白第一个政策的解释:

The execution policy type used as a unique type to disambiguate parallel algorithm overloading and require that a parallel algorithm's execution may not be parallelized. The invocations of element access functions in parallel algorithms invoked with this policy (usually specified as std::execution::seq) are indeterminately sequenced in the calling thread.

据我了解，这意味着我们在这里不并行化(多线程)，并且每个元素访问都是顺序的，就像 strcpy 中一样。对我来说，这基本上意味着一个线程运行该函数，然后我就完成了。但接下来还有

invocations of element access functions in parallel algorithms.

现在怎么办？现在还有并行算法吗？怎么办？

第二个执行政策规定:

Any such invocations executing in the same thread are indeterminately sequenced with respect to each other.

我认为这意味着:每个线程从不同的位置开始，例如容器被分成多个段，每个线程复制其中一个段。库创建线程只是为了运行算法。我的假设正确吗？

来自第三项政策:

The invocations of element access functions in parallel algorithms invoked with this policy are permitted to execute in an unordered fashion in unspecified threads, and unsequenced with respect to one another within each thread.

这是否意味着上述容器“段”不需要逐个复制，而是可以随机复制？如果是这样，为什么这对于证明额外政策的合理性如此重要？当我有多个线程时，它们需要稍微混合以保持最小的同步？

这是我目前对政策的可能不正确的理解。请指正!

• sequenced_policy:1 个线程执行算法并复制 A - Z 中的所有内容。
• parallel_policy:Lib 创建专门用于复制的新线程，而每个线程的复制段必须跟随另一个线程(按顺序)？
• parallel_unsequenced_policy:尝试多线程和 SIMD。复制的段可以通过线程混合(无论从哪里开始)。
• unsequenced_policy:尝试使用 SIMD，但仅限单线程。

Answer 1

您对各项政策基本思想的总结基本上是正确的。

Does this mean the above mentioned container "segments" need not be copied one after another but can be copied in random fashion? If so, why is this so important to justify an extra policy?

unsequenced_policy 和 parallel_unsequenced_policy 的额外策略是必要的，因为它们对调用代码提出了额外要求¹:

The behavior of a program is undefined if it invokes a vectorization-unsafe standard library function from user code called from a execution::unsequenced_policy algorithm.

[以及 parallel_unsequenced_policy 的匹配限制。]

这四种执行策略通常用于算法。提及从执行算法调用的用户代码主要适用于诸如 std::for_each 或 std::generate 之类的情况，您可以在其中使用告诉算法调用函数。以下是该标准的示例之一:

int a[] = {0,1};
std::vector<int> v;
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int i) {
v.push_back(i*2+1); // incorrect: data race
});

这个特定示例显示了并行执行产生的问题 - 您可能有两个线程尝试同时调用 v 上的 push_back，从而产生数据争用。

如果您将 for_each 与其中一个未排序的策略一起使用，则会进一步限制您的代码可以执行的操作。

当我们专门查看 std::copy_n 时，通常这可能不是什么问题，因为我们没有向它传递一些要调用的代码。好吧，无论如何，我们不会直接这样做。但实际上，我们可能是间接这样做的。 std::copy_n 对要复制的项使用赋值运算符。因此，例如，考虑这样的事情:

class foo {
    static int copy_count;
    int data;
public:
    foo &operator=(foo const &other) {
        data = other.data;
        ++copy_count;
    }
};

foo::int copy_count;

std::vector<foo> a;
std::vector<foo> b;

// code to fill a with data goes here

std::copy_n(std::execution::par, a.begin(), a.end(), std::back_inserter(b));

我们的复制分配运算符无需同步即可访问 copy_count。如果我们指定顺序执行，那没问题，但如果我们指定并行执行，我们现在(可能)在两个或更多线程上同时调用它，因此我们会出现数据竞争。

我可能需要更加努力地为赋值运算符做一些向量化不安全的事情提供一个有点连贯的理由，但这并不意味着它不存在。

摘要

我们有四个单独的执行策略，因为每个策略都对您可以在代码中执行的操作施加独特的限制。在 std::copy 或 std::copy_n 的特定情况下，这些约束主要适用于正在复制的集合中的项目的赋值运算符。

---

1. N4835，[algorithms.parallel.exec] 部分