iota,generate和手动循环都执行相同的操作吗？

Question

这三种填充向量的方法之间是否存在性能差异？

#include <vector>
#include <numeric>
#include <algorithm>
#include <iterator>

int main()
{
    std::vector<int> v(10);
    std::iota(v.begin(), v.end(), 0);

    std::vector<int> v2(10);
    int i = 0;
    std::generate(v2.begin(), v2.end(), [&i](){return i++; });

    std::vector<int> v3(10);
    i = 0;
    for (auto& j : v3)
    {
        j = i++;
    }

return 0;
}

我知道它们都会产生相同的结果,我只想知道较大的矢量是否存在速度差异.不同类型的答案会有所不同吗？

Answer 1

我们可以查看输出程序集(我使用gcc.godbolt.org,gcc -03,包含您的代码):

1)第一版,包括std::iota:

main:
    sub rsp, 8
    mov edi, 40
    call    operator new(unsigned long)
    mov DWORD PTR [rax], 0
    mov DWORD PTR [rax+4], 1
    mov rdi, rax
    mov DWORD PTR [rax+8], 2
    mov DWORD PTR [rax+12], 3
    mov DWORD PTR [rax+16], 4
    mov DWORD PTR [rax+20], 5
    mov DWORD PTR [rax+24], 6
    mov DWORD PTR [rax+28], 7
    mov DWORD PTR [rax+32], 8
    mov DWORD PTR [rax+36], 9
    call    operator delete(void*)
    xor eax, eax
    add rsp, 8
    ret

2)带std::generate和Lambda的版本:

main:
    sub rsp, 8
    mov edi, 40
    call    operator new(unsigned long)
    mov DWORD PTR [rax], 0
    mov DWORD PTR [rax+4], 1
    mov rdi, rax
    mov DWORD PTR [rax+8], 2
    mov DWORD PTR [rax+12], 3
    mov DWORD PTR [rax+16], 4
    mov DWORD PTR [rax+20], 5
    mov DWORD PTR [rax+24], 6
    mov DWORD PTR [rax+28], 7
    mov DWORD PTR [rax+32], 8
    mov DWORD PTR [rax+36], 9
    call    operator delete(void*)
    xor eax, eax
    add rsp, 8
    ret

3)和最后一个版本,手写循环:

main:
    sub rsp, 8
    mov edi, 40
    call    operator new(unsigned long)
    mov DWORD PTR [rax], 0
    mov DWORD PTR [rax+4], 1
    mov rdi, rax
    mov DWORD PTR [rax+8], 2
    mov DWORD PTR [rax+12], 3
    mov DWORD PTR [rax+16], 4
    mov DWORD PTR [rax+20], 5
    mov DWORD PTR [rax+24], 6
    mov DWORD PTR [rax+28], 7
    mov DWORD PTR [rax+32], 8
    mov DWORD PTR [rax+36], 9
    call    operator delete(void*)
    xor eax, eax
    add rsp, 8
    ret

结论:

正如预期的那样,所有三个都使用一个不错的编译器生成相同的程序集(全部展开),并启用了优化.

所以不,没有性能差异.

注意:

我做了比较组件与大到足以没有展开循环的向量的测试(我不知道GCC启发式,但它开始大小> ~15).

在这种情况下,对于所有3种情况,程序集仍然是相同的,我不会在这里复制输出,因为它没有带来太多答案,但问题是编译器真的非常擅长优化这种代码.

Answer 2

当然,找出的正确方法是测量和/或比较生成的代码.由于std::vector<T>对类型T编译器的对象使用连续内存可能会看到循环的所有3个版本并生成几乎相同的代码.此外,您的设置中的特定算法几乎没有智能实现.事情会有所不同,例如,当使用std::deque<T>算法可以单独处理段以提高性能时(我不知道任何实际上这样做的实现).

在情况下的性能是您最关心的问题,并且您使用大型载体,你可能想不最初创建一个大的载体,因为这可能会触及所有的内存虽然它是将被重写.相反,您将构造并清空向量,reserve()足够的内存,然后使用合适的目标迭代器(例如std::back_inserter(v)).不过,这些方法需要适当改变.在算法中构造对象时,算法实际上可以应用一些使用的天真循环,例如push_back()s或合适的附加迭代器可能不适用的智能:因为algoirthms可以看到他们将要创建多少个对象,可以对循环中的容量进行检查(尽管它需要通过迭代器类型进行一些特殊访问).即使算法中没有优化,我也希望对矢量进行单次传递比算法中的任何调整都具有更大的性能优势.