Почему push_back медленнее, чем operator [] для ранее выделенного вектора

Я только что прочитал этот блог http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/, сравнивая производительность operator[] и push_back в предварительно зарезервированной памяти std::vector и Я решил попробовать сам. Операция проста:

// for vector
bigarray.reserve(N);

// START TIME TRACK
for(int k = 0; k < N; ++k)
   // for operator[]:
   // bigarray[k] = k;
   // for push_back
   bigarray.push_back(k);
// END TIME TRACK

// do some dummy operations to prevent compiler optimize
long sum = accumulate(begin(bigarray), end(array),0 0);

И вот результат:

 ~/t/benchmark> icc 1.cpp -O3 -std=c++11
 ~/t/benchmark> ./a.out
[               1.cpp:   52]     0.789123s  --> C++ new
[               1.cpp:   52]     0.774049s  --> C++ new
[               1.cpp:   66]     0.351176s  --> vector
[               1.cpp:   80]     1.801294s  --> reserve + push_back
[               1.cpp:   94]     1.753786s  --> reserve + emplace_back
[               1.cpp:  107]     2.815756s  --> no reserve + push_back
 ~/t/benchmark> clang++ 1.cpp -std=c++11 -O3
 ~/t/benchmark> ./a.out
[               1.cpp:   52]     0.592318s  --> C++ new
[               1.cpp:   52]     0.566979s  --> C++ new
[               1.cpp:   66]     0.270363s  --> vector
[               1.cpp:   80]     1.763784s  --> reserve + push_back
[               1.cpp:   94]     1.761879s  --> reserve + emplace_back
[               1.cpp:  107]     2.815596s  --> no reserve + push_back
 ~/t/benchmark> g++ 1.cpp -O3 -std=c++11
 ~/t/benchmark> ./a.out
[               1.cpp:   52]     0.617995s  --> C++ new
[               1.cpp:   52]     0.601746s  --> C++ new
[               1.cpp:   66]     0.270533s  --> vector
[               1.cpp:   80]     1.766538s  --> reserve + push_back
[               1.cpp:   94]     1.998792s  --> reserve + emplace_back
[               1.cpp:  107]     2.815617s  --> no reserve + push_back

Для всех компиляторов vector с operator[] намного быстрее, чем исходный указатель с operator[]. Это привело к первому вопросу: почему? Второй вопрос: я уже "зарезервировал" память, поэтому почему opeator[] быстрее?

Следующий вопрос: поскольку память уже выделена, почему push_back меньше времени operator[]?

Ниже приведен тестовый код:

#include <iostream>
#include <iomanip>
#include <vector>
#include <numeric>
#include <chrono>
#include <string>
#include <cstring>

#define PROFILE(BLOCK, ROUTNAME) ProfilerRun([&](){do {BLOCK;} while(0);}, \
        ROUTNAME, __FILE__, __LINE__);

template <typename T>
void ProfilerRun (T&&  func, const std::string& routine_name = "unknown",
                  const char* file = "unknown", unsigned line = 0)
{
    using std::chrono::duration_cast;
    using std::chrono::microseconds;
    using std::chrono::steady_clock;
    using std::cerr;
    using std::endl;

    steady_clock::time_point t_begin = steady_clock::now();

    // Call the function
    func();

    steady_clock::time_point t_end = steady_clock::now();
    cerr << "[" << std::setw (20)
         << (std::strrchr (file, '/') ?
             std::strrchr (file, '/') + 1 : file)
         << ":" << std::setw (5) << line << "]   "
         << std::setw (10) << std::setprecision (6) << std::fixed
         << static_cast<float> (duration_cast<microseconds>
                                (t_end - t_begin).count()) / 1e6
         << "s  --> " << routine_name << endl;

    cerr.unsetf (std::ios_base::floatfield);
}

using namespace std;

const int N = (1 << 29);

int routine1()
{
    int sum;
    int* bigarray = new int[N];
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray[k] = k;
    }, "C++ new");
    sum = std::accumulate (bigarray, bigarray + N, 0);
    delete [] bigarray;
    return sum;
}

int routine2()
{
    int sum;
    vector<int> bigarray (N);
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray[k] = k;
    }, "vector");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}

int routine3()
{
    int sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "reserve + push_back");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}

int routine4()
{
    int sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray.emplace_back(k);
    }, "reserve + emplace_back");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}

int routine5()
{
    int sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "no reserve + push_back");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}


int main()
{
    long s0 = routine1();
    long s1 = routine1();
    long s2 = routine2();
    long s3 = routine3();
    long s4 = routine4();
    long s5 = routine5();
    return int (s1 + s2);
}

Ответы

Ответ 1

push_back выполняется проверка границ. operator[] нет. Поэтому, даже если вы зарезервировали место, push_back получит дополнительную условную проверку, которой не будет operator[]. Кроме того, он увеличит значение size (только резерв устанавливает capacity), поэтому он будет обновлять его каждый раз.

Короче говоря, push_back делает больше, чем делает operator[], поэтому он медленнее (и точнее).

Ответ 2

Как выяснил Якк и я, может быть еще один интересный фактор, который способствует явной медлительности push_back.

Первое интересное наблюдение заключается в том, что в исходном тесте использование new и работа на необработанном массиве происходит медленнее, чем использование vector<int> bigarray(N); и operator[] - более чем в 2 раза. Еще более интересно то, что вы можете получить такую ​​же производительность для обоих, добавив дополнительный memset для варианта с необработанным массивом:

int routine1_modified()
{
    int sum;
    int* bigarray = new int[N];

    memset(bigarray, 0, sizeof(int)*N);

    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray[k] = k;
    }, "C++ new");
    sum = std::accumulate (bigarray, bigarray + N, 0);
    delete [] bigarray;
    return sum;
}

Конечно, вывод состоит в том, что PROFILE измеряет что-то иное, чем ожидалось. Якк и я предполагаем, что это имеет какое-то отношение к управлению памятью; от комментария Якка к OP:

resize коснется всего блока памяти. reserve будет выделяться без касания. Если у вас есть ленивый распределитель, который не получает или не назначает страницы физической памяти до тех пор, пока не получит доступ, reserve на пустом векторе может быть почти бесплатным (даже не нужно найти физическую память для страниц!), Пока вы не напишете страниц (в какой момент они должны быть найдены).

Я подумал о чем-то подобном, поэтому попробовал небольшой тест для этой гипотезы, прикоснувшись к определенным страницам с помощью "strided memset" (инструмент профилирования может получить более надежные результаты):

int routine1_modified2()
{
    int sum;
    int* bigarray = new int[N];

    for(int k = 0; k < N; k += PAGESIZE*2/sizeof(int))
        bigarray[k] = 0;

    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray[k] = k;
    }, "C++ new");
    sum = std::accumulate (bigarray, bigarray + N, 0);
    delete [] bigarray;
    return sum;
}

Изменяя шаг с каждой страницы на каждую четвертую страницу, чтобы полностью исключить ее, мы получаем хороший переход таймингов из случая vector<int> bigarray(N); в случай new int[N], где не используется memset.

На мой взгляд, это сильный намек на то, что управление памятью является основным фактором результатов измерений.

Другой проблемой является ветвление в push_back. Во многих ответах утверждается, что это основная причина, по которой push_back намного медленнее, чем при использовании operator[]. Действительно, сравнивая raw-pointer w/o memset с использованием reserve + push_back, первый в два раза быстрее.

Аналогично, если добавить немного UB (но проверить результаты позже):

int routine3_modified()
{
    int sum;
    vector<int> bigarray;
    bigarray.reserve (N);

    memset(bigarray.data(), 0, sizeof(int)*N); // technically, it UB

    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "reserve + push_back");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}

эта модифицированная версия примерно в 2 раза медленнее, чем при использовании new + полного memset. Таким образом, похоже, что вызов push_back выполняется, это приводит к замедлению фактора 2 по сравнению с просто установкой элемента (через operator[] в случае vector и необработанного массива).

Но это ветвление, требуемое в push_back, или дополнительная операция?

// pseudo-code
void push_back(T const& p)
{
    if(size() == capacity())
    {
        resize( size() < 10 ? 10 : size()*2 );
    }

    (*this)[size()] = p; // actually using the allocator
    ++m_end;
}

Это действительно так просто, см., например, реализация libstdС++.

Я тестировал его с помощью варианта vector<int> bigarray(N); + operator[] и вставлял вызов функции, который имитирует поведение push_back:

unsigned x = 0;
void silly_branch(int k)
{
    if(k == x)
    {
        x = x < 10 ? 10 : x*2;
    }
}

int routine2_modified()
{
    int sum;
    vector<int> bigarray (N);
    PROFILE (
    {
        for (unsigned int k = 0; k < N; ++k)
        {
            silly_branch(k);
            bigarray[k] = k;
        }
    }, "vector");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0);
    return sum;
}

Даже при объявлении x как изменчивого, это влияет только на 1% на измерение. Конечно, вам нужно было убедиться, что ветвь на самом деле находится в коде операции, но мои знания ассемблера не позволяют мне проверить это (в -O3).

Интересным моментом является то, что происходит, когда я добавляю приращение к silly_branch:

unsigned x = 0;
void silly_branch(int k)
{
    if(k == x)
    {
        x = x < 10 ? 10 : x*2;
    }
    ++x;
}

Теперь модифицированный routine2_modified работает в 2 раза медленнее исходного routine2, находясь наравне с предложенным выше routine3_modified, который включает UB для фиксации страниц памяти. Я не нахожу этого особенно удивительным, так как он добавляет еще одну запись к каждой записи в цикле, поэтому мы имеем два раза больше работы и в два раза больше.

Заключение

Ну, вам нужно было внимательно изучить инструменты сборки и профилирования, чтобы проверить гипотезы управления памятью, а дополнительная запись - хорошая гипотеза ( "правильная" ). Но я думаю, что подсказки достаточно сильны, чтобы утверждать, что там происходит что-то более сложное, чем просто ветвь, которая замедляет push_back.

Здесь полный тестовый код:

#include <iostream>
#include <iomanip>
#include <vector>
#include <numeric>
#include <chrono>
#include <string>
#include <cstring>

#define PROFILE(BLOCK, ROUTNAME) ProfilerRun([&](){do {BLOCK;} while(0);}, \
        ROUTNAME, __FILE__, __LINE__);
//#define PROFILE(BLOCK, ROUTNAME) BLOCK

template <typename T>
void ProfilerRun (T&&  func, const std::string& routine_name = "unknown",
                  const char* file = "unknown", unsigned line = 0)
{
    using std::chrono::duration_cast;
    using std::chrono::microseconds;
    using std::chrono::steady_clock;
    using std::cerr;
    using std::endl;

    steady_clock::time_point t_begin = steady_clock::now();

    // Call the function
    func();

    steady_clock::time_point t_end = steady_clock::now();
    cerr << "[" << std::setw (20)
         << (std::strrchr (file, '/') ?
             std::strrchr (file, '/') + 1 : file)
         << ":" << std::setw (5) << line << "]   "
         << std::setw (10) << std::setprecision (6) << std::fixed
         << static_cast<float> (duration_cast<microseconds>
                                (t_end - t_begin).count()) / 1e6
         << "s  --> " << routine_name << endl;

    cerr.unsetf (std::ios_base::floatfield);
}

using namespace std;

constexpr int N = (1 << 28);
constexpr int PAGESIZE = 4096;

uint64_t __attribute__((noinline)) routine1()
{
    uint64_t sum;
    int* bigarray = new int[N];
    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new (routine1)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine2()
{
    uint64_t sum;
    int* bigarray = new int[N];

    memset(bigarray, 0, sizeof(int)*N);

    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new + full memset (routine2)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine3()
{
    uint64_t sum;
    int* bigarray = new int[N];

    for(int k = 0; k < N; k += PAGESIZE/2/sizeof(int))
        bigarray[k] = 0;

    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new + strided memset (every page half) (routine3)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine4()
{
    uint64_t sum;
    int* bigarray = new int[N];

    for(int k = 0; k < N; k += PAGESIZE/1/sizeof(int))
        bigarray[k] = 0;

    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new + strided memset (every page) (routine4)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine5()
{
    uint64_t sum;
    int* bigarray = new int[N];

    for(int k = 0; k < N; k += PAGESIZE*2/sizeof(int))
        bigarray[k] = 0;

    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new + strided memset (every other page) (routine5)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine6()
{
    uint64_t sum;
    int* bigarray = new int[N];

    for(int k = 0; k < N; k += PAGESIZE*4/sizeof(int))
        bigarray[k] = 0;

    PROFILE (
    {
        for (int k = 0, *p = bigarray; p != bigarray+N; ++p, ++k)
            *p = k;
    }, "new + strided memset (every 4th page) (routine6)");
    sum = std::accumulate (bigarray, bigarray + N, 0ULL);
    delete [] bigarray;
    return sum;
}

uint64_t __attribute__((noinline)) routine7()
{
    uint64_t sum;
    vector<int> bigarray (N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray[k] = k;
    }, "vector, using ctor to initialize (routine7)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine8()
{
    uint64_t sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "vector (+ no reserve) + push_back (routine8)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine9()
{
    uint64_t sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "vector + reserve + push_back (routine9)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine10()
{
    uint64_t sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    memset(bigarray.data(), 0, sizeof(int)*N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.push_back (k);
    }, "vector + reserve + memset (UB) + push_back (routine10)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

template<class T>
void __attribute__((noinline)) adjust_size(std::vector<T>& v, int k, double factor)
{
    if(k >= v.size())
    {
        v.resize(v.size() < 10 ? 10 : k*factor);
    }
}

uint64_t __attribute__((noinline)) routine11()
{
    uint64_t sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
        {
            adjust_size(bigarray, k, 1.5);
            bigarray[k] = k;
        }
    }, "vector + custom emplace_back @ factor 1.5 (routine11)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine12()
{
    uint64_t sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
        {
            adjust_size(bigarray, k, 2);
            bigarray[k] = k;
        }
    }, "vector + custom emplace_back @ factor 2 (routine12)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine13()
{
    uint64_t sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
        {
            adjust_size(bigarray, k, 3);
            bigarray[k] = k;
        }
    }, "vector + custom emplace_back @ factor 3 (routine13)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine14()
{
    uint64_t sum;
    vector<int> bigarray;
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.emplace_back (k);
    }, "vector (+ no reserve) + emplace_back (routine14)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine15()
{
    uint64_t sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.emplace_back (k);
    }, "vector + reserve + emplace_back (routine15)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

uint64_t __attribute__((noinline)) routine16()
{
    uint64_t sum;
    vector<int> bigarray;
    bigarray.reserve (N);
    memset(bigarray.data(), 0, sizeof(bigarray[0])*N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
            bigarray.emplace_back (k);
    }, "vector + reserve + memset (UB) + emplace_back (routine16)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

unsigned x = 0;
template<class T>
void /*__attribute__((noinline))*/ silly_branch(std::vector<T>& v, int k)
{
    if(k == x)
    {
        x = x < 10 ? 10 : x*2;
    }
    //++x;
}

uint64_t __attribute__((noinline)) routine17()
{
    uint64_t sum;
    vector<int> bigarray(N);
    PROFILE (
    {
        for (int k = 0; k < N; ++k)
        {
            silly_branch(bigarray, k);
            bigarray[k] = k;
        }
    }, "vector, using ctor to initialize + silly branch (routine17)");
    sum = std::accumulate (begin (bigarray), end (bigarray), 0ULL);
    return sum;
}

template<class T, int N>
constexpr int get_extent(T(&)[N])
{  return N;  }

int main()
{
    uint64_t results[] = {routine2(),
    routine1(),
    routine2(),
    routine3(),
    routine4(),
    routine5(),
    routine6(),
    routine7(),
    routine8(),
    routine9(),
    routine10(),
    routine11(),
    routine12(),
    routine13(),
    routine14(),
    routine15(),
    routine16(),
    routine17()};

    std::cout << std::boolalpha;
    for(int i = 1; i < get_extent(results); ++i)
    {
        std::cout << i << ": " << (results[0] == results[i]) << "\n";
    }
    std::cout << x << "\n";
}

Пример прогона на старом и медленном компьютере; Примечание:

  • N == 2<<28, а не 2<<29, как в OP
  • скомпилировано с g++ 4.9 20131022 с -std=c++11 -O3 -march=native
[            temp.cpp:   71]     0.654927s  --> new + full memset (routine2)
[            temp.cpp:   54]     1.042405s  --> new (routine1)
[            temp.cpp:   71]     0.605061s  --> new + full memset (routine2)
[            temp.cpp:   89]     0.597487s  --> new + strided memset (every page half) (routine3)
[            temp.cpp:  107]     0.601271s  --> new + strided memset (every page) (routine4)
[            temp.cpp:  125]     0.783610s  --> new + strided memset (every other page) (routine5)
[            temp.cpp:  143]     0.903038s  --> new + strided memset (every 4th page) (routine6)
[            temp.cpp:  157]     0.602401s  --> vector, using ctor to initialize (routine7)
[            temp.cpp:  170]     3.811291s  --> vector (+ no reserve) + push_back (routine8)
[            temp.cpp:  184]     2.091391s  --> vector + reserve + push_back (routine9)
[            temp.cpp:  199]     1.375837s  --> vector + reserve + memset (UB) + push_back (routine10)
[            temp.cpp:  224]     8.738293s  --> vector + custom emplace_back @ factor 1.5 (routine11)
[            temp.cpp:  240]     5.513803s  --> vector + custom emplace_back @ factor 2 (routine12)
[            temp.cpp:  256]     5.150388s  --> vector + custom emplace_back @ factor 3 (routine13)
[            temp.cpp:  269]     3.789820s  --> vector (+ no reserve) + emplace_back (routine14)
[            temp.cpp:  283]     2.090259s  --> vector + reserve + emplace_back (routine15)
[            temp.cpp:  298]     1.288740s  --> vector + reserve + memset (UB) + emplace_back (routine16)
[            temp.cpp:  325]     0.611168s  --> vector, using ctor to initialize + silly branch (routine17)
1: true
2: true
3: true
4: true
5: true
6: true
7: true
8: true
9: true
10: true
11: true
12: true
13: true
14: true
15: true
16: true
17: true
335544320

Ответ 3

Когда вы выделяете массив в конструкторе, компилятор/библиотека может в основном memset() заполнить оригинал, а затем просто установить каждое отдельное значение. Когда вы используете push_back(), класс std::vector<T> должен будет:

  • Проверьте, достаточно ли места.
  • Измените конечный указатель на новое местоположение.
  • Установите фактическое значение.

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

Ответ 4

Я могу ответить на ваш второй вопрос. Хотя вектор предварительно распределен, push_back все равно должен проверять доступное пространство каждый раз, когда вы вызываете push_back. С другой стороны, оператор [] не выполняет никаких проверок и просто предполагает, что пространство доступно.

Ответ 5

Это расширенный комментарий, а не ответ, предназначенный для улучшения вопроса.

Процедура 4 вызывает поведение undefined. Вы пишете конец конца size массива. Замените резерв с изменением размера, чтобы устранить это.

Рутина с 3 по 5 ничего не могла сделать после оптимизации, поскольку у них нет видимого результата.

An insert( vec.end(), src.begin(), src.end() ) где src - это диапазон генератора произвольного доступа (boost, возможно, имеет его), может эмулировать версию new, если ваш insert умный.

Дублирование routine1 кажется забавным - случайно это изменит тайминги?