C++ vector访问的优化

这段时间在写一个高精度整数库，写一些std::vector元素访问的时候发现了一个有意思的地方。

vector<int> func1(const vector<int> & a)
{
    vector<int> r(a.size());
    for (size_t i = 0; i < a.size(); ++i)
    {
        r[i] = a[i];
        r[i] += a[i];
        r[i] += a[i];
        r[i] += a[i];
    }
    return r;
}

vector<int> func2(const vector<int> & a)
{
    int t;
    vector<int> r(a.size());
    for (size_t i = 0; i < a.size(); ++i)
    {
        t = a[i];
        t += a[i];
        t += a[i];
        r[i] = t + a[i];
    }
    return r;
}

这两个函数都是对r的元素进行了4次加法，但是在相同的编译条件下clang-10 -O3，产生的代码会有显著的区别。

# func1
movl    (%rax,%rdx,4), %esi
movl    %esi, (%rbx,%rdx,4)
addl    (%rax,%rdx,4), %esi
movl    %esi, (%rbx,%rdx,4)
addl    (%rax,%rdx,4), %esi
movl    %esi, (%rbx,%rdx,4)
addl    (%rax,%rdx,4), %esi
movl    %esi, (%rbx,%rdx,4)

# func2
movl    (%rax,%rdx,4), %esi
shll    $2, %esi
movl    %esi, (%rbx,%rdx,4)

编译器可以直接将func2中的加法优化成左移，然而func1中因为要每次写回r[i]，没有任何优化，性能会有非常大的差距。

但是有趣的是，如果把r换成一个普通的int数组的话，编译器会对两种代码做一样的优化。

int * func1(const vector<int> & a)
{
    int * r = new int[a.size()];
    for (size_t i = 0; i < a.size(); ++i)
    {
        r[i] = a[i];
        r[i] += a[i];
        r[i] += a[i];
        r[i] += a[i];
    }
    return r;
}

int * func2(const vector<int> & a)
{
    int t;
    int * r = new int[a.size()];
    for (size_t i = 0; i < a.size(); ++i)
    {
        t = a[i];
        t += a[i];
        t += a[i];
        r[i] = t + a[i];
    }
    return r;
}

# func1 and func2 are the same
movl    (%rbx,%rcx,4), %edx
shll    $2, %edx
movl    %edx, (%rax,%rcx,4)

不过还有一个有意思的点，用最新版本的gcc -O3编译数组版本的话，gcc竟然没能优化func1。gcc和clang的差距可能真的是不小了。

所以说如果对std::vector的元素有连续的操作的话，最好声明一个局部变量去操作，编译器会有更大的优化空间 (对普通数组最好也是如此，毕竟gcc没能优化）。