Как std::vector быстрее, чем простой массив?

Я наткнулся на это, сравнивая круговой буфер. Может ли кто-нибудь объяснить, как std::vector удается превзойти простой массив в этом экземпляре?

#include <iostream>
#include <vector>

struct uint_pair {
    unsigned int a, b;
    uint_pair (unsigned int x = 0, unsigned int y = 0) : a(x), b(y) {}
};

struct container {
    unsigned int pos;

#ifdef USE_VECTOR
    std::vector<uint_pair> data;
    container() : pos(0) { data.resize(16); }
#else
    uint_pair data[16];
    container() : pos(0) {}
#endif

    void add(uint_pair val) {
        data[++pos % 16] = val;
    }
};

int main() {
    container c;
    for (unsigned int i = 0; i < 1000000000; i++) c.add(uint_pair{i, i});
    std::cout << c.data[0].a << " " << c.data[0].b << std::endl;
}

Это результаты, которые я получаю с помощью GCC (аналогично Clang):

g++ -o bench -std=c++0x -Os main.cpp -D'USE_VECTOR'
real    0m8.757s
user    0m8.750s
sys     0m0.002s

g++ -o bench -std=c++0x -Os main.cpp
real    0m9.215s
user    0m9.209s
sys     0m0.002s

Ответ 1

Вот как вы можете устранить разницу. Вместо add используйте следующую функцию:

void set(unsigned int x, unsigned int y) {
    ++pos;
    data[pos % 16].a = x;
    data[pos % 16].b = y;
}

называется так:

for (unsigned int i = 0; i < 1000000000; i++) c.set(i, i);

Это делает то же самое, что и у вас, но это позволяет избежать семантического создания временного объекта. Похоже, что когда вы используете вектор, компилятор лучше может оптимизировать временный.

$ g++-4.8 -o bench -std=c++11 -Os main.cpp -DUSE_VECTOR
$ time ./bench 
999999999 999999999

real    0m0.635s
user    0m0.630s
sys 0m0.002s

$ g++-4.8 -o bench -std=c++11 -Os main.cpp
$ time ./bench 
999999999 999999999

real    0m0.644s
user    0m0.639s
sys 0m0.002s

На моей машине методы set и add дают идентичную производительность с векторами. Только массив показывает разницу. Чтобы повысить доверие к оптимизации, если вы скомпилируете с -O0, тогда метод массива будет немного быстрее (но в 10 раз медленнее, чем с -Os).

Это не объясняет, почему компилятор рассматривает эти два по-разному. В конце концов, вектор подкрепляется массивом. Кроме того, std::array ведет себя одинаково с вашим массивом в стиле C.

Ответ 2

Одна проблема заключается в размещении члена "pos" в вашей структуре.

Для c-массива помните, что он хранится смежно в памяти рядом с вашим членом "pos" . Когда данные вставляются в c-массив, дополнительные инструкции должны выдаваться для смещения в структуру, расположенную за элементом "pos" . Однако запись в вектор не делает такого ограничения, поскольку его память находится где-то в другом месте.

Чтобы выжать больше производительности, убедитесь, что ваши самые горячие данные находятся в передней части строки кэша.

Edit:

Чтобы c-массив выполнялся так же быстро, как вектор, c-массив должен быть выделен на 8 байтовых границах на 64-битной машине. Так что-то вроде:

uint_pair* data;
unsigned int pos;

container() : pos(0) {
    std::size_t bufSize = sizeof(uint_pair) * 17;
    void* p = new char[bufSize];
    p = std::align(8, sizeof(uint_pair), p, bufSize);
    data = reinterpret_cast<uint_pair*>(p);
}

Со слегка измененной функцией добавления:

void add(unsigned int x, unsigned int y) {
    auto& ref = data[pos++ % 16];
    ref.a = x;
    ref.b = y;
}

С-массив теперь раз:

real    0m0.735s
user    0m0.730s
sys     0m0.002s

И std::vector:

real    0m0.743s
user    0m0.736s
sys     0m0.004s

Стандартные разработчики библиотек вытаскивают все остановки для вас:)

Ответ 3

Кажется, компилятор С++ 11 генерирует лучший код для вектора из-за оператора = (rvalue reference). Во-первых, в С++ 03 компилятор простой массив в два раза быстрее, чем вектор. Во-вторых, tehre не имеет значения, если вы используете набор void (unsigned int x, unsigned int y), предложенный Адамом.

Ассемблерный код для вектора

.L49:
leal    (%rdi,%rax), %esi
andl    $15, %esi
leaq    (%rdx,%rsi,8), %rsi
movl    %eax, (%rsi)
movl    %eax, 4(%rsi)
incq    %rax
cmpq    $1000000000, %rax
jne .L49

для простого массива

.L3:
movl    12(%rsp), %edx
incl    %edx
movl    %edx, 12(%rsp)
andl    $15, %edx
leaq    12(%rsp,%rdx,8), %rdx
movl    %eax, 4(%rdx)
movl    %eax, 8(%rdx)
incl    %eax
cmpl    $1000000000, %eax
jne .L3