Push_back比insert更快吗？

Question

Push_back比insert更快吗？

c++performancestl

7

我是一位有用的助手，可以为您翻译文本。

我正在使用 std::deque。我本以为用单个insert替换带有push_back循环会提高性能。比如这里建议这样做：here。

但现在我不太确定了。

我在测试代码上运行了一些基准测试。

Main.cpp：

#include"queueInsert.h"

#include<Windows.h>

std::deque<int> queue;

constexpr size_t len = 64;

int arr[len];

int main()
{
    DWORD startTime = GetTickCount();
    for (int i = 0; i < 100000; ++i)
    {
        insert(queue, arr, len);
    }
    DWORD endTime = GetTickCount();

    return endTime - startTime;
}

queueInsert.h:

#include<deque>

void insert(std::deque<int>&, int* arr, int n);

queueInsert.cpp - push版本

#include "queueInsert.h"

void insert(std::deque<int>& queue, int* arr, int n)
{
    for (int i = 0; i < n; ++i)
    {
        queue.push_back(arr[i]);
    }
}

queueInsert.cpp - 插入版本

#include "queueInsert.h"

void insert(std::deque<int>& queue, int* arr, int n)
{
    queue.insert(queue.end(), arr, arr + n);
}

使用push_back函数获得203毫秒，使用insert函数获得218毫秒。

将数组长度len更改为6，迭代次数增加到一百万次，结果保持不变：push函数需要219毫秒，insert函数需要266毫秒。

只有当len = 640时，push函数才稍微逊色，即使如此，差距也很小：使用push函数需要1531毫秒，使用insert函数需要1437毫秒。

我在Windows 10下使用VisualStudio 2015的Release模式编译。我确定编译器没有进行优化，例如内联常量迭代次数或者合并循环，因为每次更改实现后只重新编译queueInsert.cpp文件。

我做性能分析是否有误？或者如果要插入的元素数量不大，我应该继续使用push_back函数吗？

- Francesco Dondi

1

我确信编译器没有进行优化 -- 让我们看看汇编清单。 - PaulMcKenzie

1

我已经阅读了原始文章，没关系。 - Slava

我的意思是向量作为元素序列，而不是 std::vector。我已经进行了更正以使意思更清晰。 - Francesco Dondi

1

"如果要插入的元素数量不大，我是否应该保留 push_back 呢？" 考虑到在这种情况下性能差异微不足道，您可以按照自己的代码逻辑进行选择。 - Nicol Bolas

这篇文章是2011年的。 - knivil

1

你正在使用GetTickCount()来测量毫秒，它的精度为10-15毫秒。使用QueryPerformanceFrequency()/QueryPerformanceCounter()可以提供更高的分辨率。 - David Thomas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicol Bolas · Accepted Answer

deque::insert的操作方式可以分为三种：一般插入、在前面插入和在后面插入。因此，每次调用insert时，必须测试它需要插入的位置，即需要将传递的迭代器与前面和后面进行比较。

deque::push_back只有一种操作模式：在后面插入。

使用批量插入操作的优点在于，容器可以检测到需要分配多少内存来执行整个插入操作，因为它可以获取迭代器范围的长度。因此，批量插入越大，insert的性能就越好。

至少对于vector来说是这样的。

看看vector，如果您逐个插入30,000个元素，则可能会执行14-15次重新分配。这意味着分配新内存并将旧数据复制到该内存中。而如果您一次插入30,000个元素，则只需进行一次重新分配。

deque通常实现为固定大小块的数组。因此，如果您逐个插入30,000个元素，则将获得约3,000个分配（取决于块大小）。如果您一次插入30,000个元素，则将获得...约3,000个分配。因此，您并没有节省多少。

由于对于deque来说，批量插入与单个插入并没有太大区别，所以会出现微观优化问题的竞争。每个insert调用都必须进行迭代器比较，以确定如何执行该插入操作。因此，插入操作越小，insert的效率就越低。而push_back则没有这个开销，但它需要为每个元素调用一个函数，因此它有这个开销。

因此，在每次插入的元素数较多时，insert很可能会胜出。