迭代器范围的向量构建和向量删除哪个更快？

Question

考虑这两个不同的函数实现，它们都是用来从前面删除 x 个元素的：

template <typename T>
std::vector<T> drop(int size, const std::vector<T>& coll){
    if (size<0) return std::vector<T>();
    auto sized = size > coll.size() ? coll.size() : size;
    typename std::vector<T>::const_iterator first = coll.begin()+sized;
    typename std::vector<T>::const_iterator last = coll.end();
    return std::vector<T>(first,last);
}

template <typename T>
std::vector<T> drop2(int size, std::vector<T> coll){
    if (size<0) return std::vector<T>();
    auto sized = size > coll.size() ? coll.size() : size;
    coll.erase(coll.begin(),coll.begin()+sized);
    return coll;
}

在这两个版本中，都会分配一个新的std::vector（在第二个版本中，它被作为参数复制，而不是引用）。其中一个通过erase()创建结果，而另一个则使用原始向量的迭代器创建结果。

有没有理由认为这两者在性能上有实质性的区别？

此外，在这两个版本中，RVO是否有保障？

编辑：

我做了一个测试，结果表明第一个版本比第二个版本慢很多。

template<typename F>
void dropExample(F f){
    std::cout<<"drop example"<<std::endl;
    auto t1 = Clock::now();
    for (auto x: range(100000)){
        f(2, range(100));
    }
    auto t2 = Clock::now();

    std::cout << "Delta t2-t1: "
    << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
    << " ms" << std::endl;
}

输出：

dropExample(drop<int>);
dropExample(drop2<int>);

drop example 
Delta t2-t1: 625 ms
drop example 
Delta t2-t1: 346 ms

无论我在for循环中添加多少次迭代，即使是进行十秒钟的操作，数字也大致如此。

编辑2：

我已经按照评论建议增加了lvalue测试：

template<typename F, typename T>
void dropExample2(F f, T vec){
    std::cout<<"drop example 2"<<std::endl;
    auto t1 = Clock::now();
    for (auto x: range(1000)){
        f(2, vec);
    }
    auto t2 = Clock::now();

    std::cout << "Delta t2-t1: "
    << std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count()
    << " ms" << std::endl;
}

然后在主函数中：

int main(int argc, const char * argv[]) {

    auto testrange=range(100000);

    dropExample(drop<int>);
    dropExample(drop2<int>);

    dropExample2(drop<int>,testrange);
    dropExample2(drop2<int>,testrange);

     return 0;
}

输出结果仍然表明第二个更快:

drop example 
Delta t2-t1: 564 ms
drop example 
Delta t2-t1: 375 ms
drop example 2 
Delta t2-t1: 2318 ms
drop example 2 
Delta t2-t1: 698 ms

以下是示例中使用的辅助函数：

```

std::vector<int> range(int start, int end, int step);

std::vector<int> range(int start, int end){
    if (end<start){
        return range(start,end,-1);
    }else if (start == end){
        return std::vector<int> {start};
    }else{
        std::vector<int> nums(end-start);
        std::iota(nums.begin(),nums.end(),start);
        return nums;}
}

std::vector<int> range(int end){
    return range(0,end);
}

std::vector<int> range(int start, int end, int step){
    std::vector<int> nums{start};
    auto next=start+step;
    while ((next<end&&start<=end&&step>0)||
           (next>end&&start>end&&step<0))
    {
        nums.push_back(next);
        next+=step;
    }
    return nums;
}

- johnbakers

---

有趣的猜测...使用std::chrono在执行数百万次操作时计时，第一次总是需要至少多50%的时间，通常近乎两倍长。 - johnbakers

在测试示例中，提供的向量是临时的，并且函数直接在提供的向量上调用erase。由于erase可能是一堆移动操作和可能是复制操作，所以它会更快。尝试提供一个左值。由于你正在处理int，所以只需要进行复制操作。但是第二个测试不需要分配内存。 - jaggedSpire

什么是 range 和 logit？我们需要一个可编译的示例。 - NathanOliver

@johnbakers 你用来编译的标志是什么？ - NathanOliver

@T.C. 无论我如何修改向量中的元素数量，数字都会被删除（我尝试了成百上千个删除参数），似乎没有任何改变可以让第一个更快。很奇怪。 - johnbakers

Answer 1

第一种方法几乎肯定更快，除非您正在向drop输入一个右值，在这种情况下，您需要进行度量。

假设你有N个元素要开始，并且要删除M个元素：

• 第一种方法复制N-M个元素；第二种方法复制N个元素。
• 第一种方法不执行任何分配；第二种方法执行N-M次移动分配，可能会退化为拷贝分配。
• 第一种方法可以实现返回值优化（RVO）;第二种方法需要进行不能省略的移动操作。但是，移动向量足够便宜，额外的成本很可能是最小的。

- T.C.

---

我已经更新了测试结果，表明第二个实际上要快得多。 - johnbakers

在我的测试示例中尝试了很多测试设置后，我终于能够创建一些场景，在这些场景下第一个执行速度更快，但前提是操作的向量大小在1000万个元素以上。但是，只有当向量是左值时，第一个才会更快。不论大小如何，在所有其他测试中，第二个都是最快的。 - johnbakers

Answer 2

您的第二个示例会创建许多对象（复制输入参数），然后再将它们全部删除（在调用erase时）。这将根据T的值而产生不同的性能差异，但我怀疑第一个示例可能永远不会比第二个示例慢。
此外，第二个版本使用的内存量将更大，因为erase不会重新分配内存。

编辑：
您当前的测试存在缺陷，因为您将要对其进行子集化的向量传递为临时变量，允许编译器在drop2中移动构造输入参数，从而完全省略复制。只需更改：

   for (auto x: range(100000))
       f(200, range(10000));

为了

   auto v = range(10000);
   for (auto x: range(100000))
       f(200, v);

这显著改变了结果。不过，在向量变得更大之前，第二种方法对我仍然更快。值得注意的是，因为你使用了int，所以不同的方法可以被最优地优化为memcpy和一些指针操作。

drop可以简单地成为一个(coll.size() - size) * sizeof(int)字节的memcpy，而drop2可以成为coll.size() * sizeof(int)字节的memcpy。这是因为int的析构函数是一个空操作，所以对erase的调用可以简化为从向量的__last指针中减去size。

如果你只关心像这样的原始类型，那么这没问题，但如果你还想为std::string等类型实现最优实现，则其析构函数和复制构造函数就成为非常重要的因素。我尝试过将std::vector<int>作为向量内部的类型，虽然总体上较慢，但对于较小的大小，似乎drop2仍然更快。然而，drop在更低的阈值下变得更有效率。我非常怀疑这就是我们在这里看到的，因此我们最终运行的代码处于某种介于纯粹的memcpy和我们原样编写的代码之间的状态。

我想最终我们正在测试编译器优化不同函数的能力（例如std::uninitialized_copy、基于迭代器的std::move、在平凡和非平凡类型上循环调用get_allocator().destroy(p)等）。我现在只能说的是，即使是代码中似乎很小的变化，结果也可能相差很大。

然而，我仍然感到惊讶的是，即使只针对一定范围内的元素，drop2运行得比drop还要快。

- SirGuy

Answer 3

实际上，答案在于对这两个版本进行广泛的基准测试。

然而，经过评估，我倾向于认为第一个版本会更快，因为在一般情况下，你需要从初始向量复制较少的元素到输出向量中，而在第二种情况中，你需要复制所有元素。

- 101010