Push_back比插入更快？

Question

我正在使用std::deque.我确信替代与循环push_back有一个insert会产生性能的提高.例如,这里也建议使用它.

但现在我不再那么肯定了.

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

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 -insert版本

#include "queueInsert.h"

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

我得到203毫秒push_back,但218有insert.

更改len到6,并增加迭代到一百万,保持了相同的结果:219钢厂push和266进行insert.

只有len = 640不push吃亏,甚至然后很少:1531对于push反对1437的insert.

我正在Windows 10下的VisualStudio 2015中发布.

我确信编译器没有进行优化,因为内联迭代的常数或融合循环,因为每次更改实现时queueInsert.cpp都会重新编译.

我在做剖析错了吗？或者,push_back如果要插入的元素数量不大,我应该保留吗？

Answer 1

deque::insert有效地有3种可能的操作方式:一般插入,前插入,后插入.因此,每次调用时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当每个插入物添加的元素数量很高时,可能会获胜.