c++ - 并行 std::copy 复杂度

Question

这是 cppreference.com 对 std::copy( https://en.cppreference.com/w/cpp/algorithm/copy ) 的引用。

Complexity
1-2) Exactly (last - first) assignments
3-4) Exactly (last - first) applications of the predicate, between ​0​ and (last - first) assignments (assignment for every element for which predicate is equal to true, dependent on predicate and input data)
For the overloads with an ExecutionPolicy, there may be a performance cost if ForwardIt1's value type is not MoveConstructible.

很明显，std::copy 的并行版本应该做额外的工作来组织并行性，并且其复杂性可能会增加。我想了解它可能会高出多少以及何时会发生。

如果值类型不是MoveConstructible，也意味着它不是CopyConstuctible，对吧？那么我们如何复制那种对象呢？有人可以提供一个我们因此而受到性能损失的例子。

Answer 1

If value type is not MoveConstructible it also means that it is not CopyConstuctible, right?

不，这是一个反例，如果复制代价高昂，可能会由于无法移动而导致一些性能损失:

struct S
{
    S();
    S(const S&);
    S& operator=(const S&);
    S(S&&) = delete;
    S& operator=(S&&) = delete;
};

请注意，OutputIt 是一个单向迭代器，而不是随机访问。对于并行复制以实现性能优势，复制必须以非顺序方式进行，但结果必须顺序存储到 OutputIt 中。这就是为什么对象应该是可移动的，以便在多个线程创建它们时将它们取出并按顺序将它们写入 OutputIt，而不管分配的顺序如何。

事实上，对象可移动是不够的，它们必须廉价可移动以避免额外的运行时成本。