c++ 向量reserve + emplace_back比普通数组慢

zu0ti5jz  于 2022-12-15  发布在  其他
关注(0)|答案(1)|浏览(95)

我知道带resize或/和push_back的向量比普通数组慢,因为需要额外创建/复制对象。Most之前关于向量慢的问题是关于resize/push_back慢的。通常的建议是使用reserve+emplace_back,因为它们比push_back快。
我做了一些测试,根据测试结果reserve+emplace_back比普通数组慢很多。为什么?我遗漏了什么东西,使比较不公平吗?
代码:

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <vector>
#include <chrono>
#include <string>
#include <algorithm>
#include <climits>
using tp = std::chrono::steady_clock::time_point;
class Time {
public:
    static void show(tp t1, tp t2) { //time passed since t1
        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count() << '\t';
        printf("nanoseconds \n");
    }
    tp add() {
        tp p = std::chrono::steady_clock::now();
        return p;
    }
};

int main()
{
    Time time;
    const int VSIZE = 1000000;
    auto t1 = time.add();
    double vsizearr[VSIZE];
    for (auto i = 0; i < VSIZE; i++) {
        vsizearr[i]=i;
        asm volatile("" : : : "memory"); //doesn't allow compiler to erase the loop
    }
    auto t2 = time.add();
    std::vector<double> second;
    second.reserve(VSIZE);
    for (auto i = 0; i < VSIZE; i++) {
        second.emplace_back(i);
        asm volatile("" : : : "memory"); //doesn't allow compiler to erase the loop
    }
    auto t3 = time.add();
    time.show(t1, t2);
    time.show(t2, t3);
    return 0;
}

基准测试结果:
Windows 10、C++17、LLVM-叮当声、-O 1

306300  nanoseconds
1824700 nanoseconds

Ubuntu 20.04,C17,g和叮当

root@vlad-VirtualBox:/home/vlad/Documents clang++ -O1 -std=c++17 -o test test.cpp
root@vlad-VirtualBox:/home/vlad/Documents ./test
284340 nanoseconds 
3115997 nanoseconds 
root@vlad-VirtualBox:/home/vlad/Documents g++ -O1 -std=c++17 -o test test.cpp
root@vlad-VirtualBox:/home/vlad/Documents ./test
284340 nanoseconds 
3145702 nanoseconds

-O3结果与-O 1大致相同。

ycl3bljg

ycl3bljg1#

基准存在偏差:它并不衡量你的想法。事实上,GCC 12.2和Clang 15.0都优化了第一个循环,所以实际上什么也没有写。请在GodBolt上查看。

下面是使用GCC和Clang的第一个循环的代码:

; [GCC]
        mov     eax, 1000000
.L31:
        sub     eax, 1
        jne     .L31

------------------------------

; [Clang]
        mov     ebx, 1000000
.LBB0_1:
        dec     ebx
        jne     .LBB0_1

正如你所看到的,循环是空的,没有用,所以它很快就不奇怪了。编译器优化了它,因为 * 数组没有被读取 *。
对于第二个循环,下面是循环的汇编代码:

; [GCC]
.L43:
        pxor    xmm0, xmm0
        cvtsi2sd        xmm0, eax
        movsd   QWORD PTR [rsi], xmm0
        add     rsi, 8
        mov     QWORD PTR [rsp+24], rsi
.L33:
        mov     eax, DWORD PTR [rsp+12]
        add     eax, 1
        mov     DWORD PTR [rsp+12], eax
        cmp     eax, 999999
        jg      .L42
.L34:
        mov     rsi, QWORD PTR [rsp+24]
        cmp     rsi, QWORD PTR [rsp+32]
        jne     .L43
        lea     rdx, [rsp+12]
        lea     rdi, [rsp+16]
        call    void std::vector<double, std::allocator<double> >::_M_realloc_insert<int&>(__gnu_cxx::__normal_iterator<double*, std::vector<double, std::allocator<double> > >, int&)
        jmp     .L33

------------------------------

; [Clang]
.LBB0_5:                                #   in Loop: Header=BB0_4 Depth=1
        xorps   xmm0, xmm0
        cvtsi2sd        xmm0, r15d
        movsd   qword ptr [rbx], xmm0
.LBB0_32:                               #   in Loop: Header=BB0_4 Depth=1
        add     rbx, 8
        inc     r15d
        cmp     r15d, 1000000
        je      .LBB0_6
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        cmp     rbx, rcx
        jne     .LBB0_5
[...]

正如你所看到的,GCC没有优化对_M_realloc_insert的调用。两者都保留了数组写入,更不用说昂贵的int-to-double转换。有一个昂贵的逻辑来知道数组是否需要调整大小。这是必要的,因为编译器几乎不知道这部分实际上是无用的

相关问题