Является ли std :: vector намного медленнее, чем обычные массивы?

Я всегда думал, что это общая мудрость std::vector "реализована в виде массива", бла-бла-бла. Сегодня я спустился и проверил это, и, кажется, это не так:

Вот некоторые результаты теста:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

Это примерно в 3 - 4 раза медленнее! На самом деле не оправдывает vectorкомментарии « может быть медленнее для нескольких наносек».

И код, который я использовал:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

Я делаю это неправильно или что-то? Или я только что сломал этот миф о спектакле?

Я использую режим выпуска в Visual Studio 2005 .

В Visual C ++ , #define _SECURE_SCL 0уменьшает UseVectorвдвое (доведя его до 4 -х секунд). Это действительно огромно, ИМО.

Используя следующее:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray завершен за
2,196 секунды. UseVector завершен за 4,412 секунды.
UseVectorPushBack завершен за 8,017 секунды
. Все завершено за 14,626 секунд.

Таким образом, массив в два раза быстрее, чем вектор.

Но после более подробного изучения кода это ожидается; когда вы пересекаете вектор дважды, а массив - только один раз. Примечание: когда выresize() используете вектор, вы не только выделяете память, но и пробегаете вектор и вызываете конструктор для каждого члена.

Немного перестроим код, чтобы вектор инициализировал каждый объект только один раз:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Теперь снова делаем то же время:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector завершен за 2,216 секунды

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

Я также хотел бы принять во внимание, что вы неправильно инициализируете / уничтожаете объект Pixel в UseArrray()методе, так как не вызывается ни конструктор / деструктор (это может быть не проблема для этого простого класса, но что-то более сложное (например, с указателями или членами) с указателями) вызовет проблемы.

Отличный вопрос Я пришел сюда, ожидая найти какое-то простое исправление, которое ускорит векторные тесты. Это не сработало так, как я ожидал!

Оптимизация помогает, но этого недостаточно. С оптимизацией я все еще вижу разницу в производительности в 2 раза между UseArray и UseVector. Интересно, что UseVector был значительно медленнее, чем UseVectorPushBack без оптимизации.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Идея № 1 - использовать новый [] вместо malloc

Я попытался изменить , malloc()чтобы new[]в UseArray поэтому объекты будут получать построены. И переход от индивидуального назначения поля к назначению экземпляра Pixel. Да, и переименование переменной внутреннего цикла в j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Удивительно (для меня), ни одно из этих изменений не имело никакого значения вообще. Даже изменение, к new[]которому по умолчанию будут построены все пиксели. Кажется, что gcc может оптимизировать вызовы конструктора по умолчанию при использовании new[], но не при использованииvector .

Идея № 2 - Удаление повторных вызовов оператора []

Я также попытался избавиться от тройного operator[]поиска и кешировать ссылку на pixels[j]. Это на самом деле замедлило UseVector! К сожалению.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Идея № 3 - Удалить конструкторов

Как насчет полного удаления конструкторов? Тогда, возможно, gcc сможет оптимизировать построение всех объектов при создании векторов. Что произойдет, если мы изменим Pixel на:

struct Pixel
{
    unsigned char r, g, b;
};

Результат: примерно на 10% быстрее. Все еще медленнее, чем массив. Гектометр

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Идея № 4 - использовать итератор вместо индекса цикла

Как насчет использования vector<Pixel>::iteratorвместо индекса цикла?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Результат:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

Нет, не отличается. По крайней мере, это не медленнее. Я думал, что это будет иметь производительность, аналогичную # 2, где я использовалPixel& ссылку.

Вывод

Даже если некоторые умные cookie-файлы выясняют, как сделать векторный цикл таким же быстрым, как и массив, это не очень хорошо говорит о поведении по умолчанию std::vector . Так много для того, чтобы компилятор был достаточно умен, чтобы оптимизировать всю C ++ и сделать контейнеры STL такими же быстрыми, как необработанные массивы.

Суть в том, что при использовании компилятор не может оптимизировать вызовы конструктора no-op по умолчанию std::vector. Если вы используете обычный, new[]он отлично их оптимизирует. Но не с std::vector. Даже если вы можете переписать свой код, чтобы исключить вызовы конструктора, которые выглядят здесь как мантра: «Компилятор умнее вас. STL такой же быстрый, как простой C. Не беспокойтесь об этом».

Это старый, но популярный вопрос.

На данный момент многие программисты будут работать на C ++ 11. А в C ++ 11 написанный код OP работает одинаково быстро для UseArrayили UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Основная проблема заключалась в том, что в то время как ваша Pixelструктура была неинициализирована, она std::vector<T>::resize( size_t, T const&=T() )принимает построенный по умолчанию Pixelи копирует его . Компилятор не заметил, что его просили скопировать неинициализированные данные, поэтому он фактически выполнил копирование.

В C ++ 11 std::vector<T>::resizeесть две перегрузки. Первое std::vector<T>::resize(size_t), другое std::vector<T>::resize(size_t, T const&). Это означает, что когда вы вызываете resizeбез второго аргумента, он просто конструирует по умолчанию, и компилятор достаточно умен, чтобы понять, что конструкция по умолчанию ничего не делает, поэтому пропускает пропуск через буфер.

(Две перегрузки были добавлены для обработки подвижных, конструируемых и не копируемых типов - повышение производительности при работе с неинициализированными данными является преимуществом).

push_backРешение также делает fencepost проверку, которая замедляет его вниз, так что остается медленнее , чемmalloc версия.

живой пример (я также заменил таймер chrono::high_resolution_clock).

Обратите внимание, что если у вас есть структура, которая обычно требует инициализации, но вы хотите обработать ее после увеличения буфера, вы можете сделать это с помощью специального std::vectorраспределителя. Если вы хотите затем перевести его в более нормальное русло std::vector, я считаю, что осторожное использование allocator_traitsи переопределение ==могут это осуществить, но я не уверен.

Если честно, вы не можете сравнить реализацию C ++ с реализацией C, как я бы назвал вашу версию malloc. malloc не создает объекты - он только выделяет необработанную память. То, что вы затем обрабатываете эту память как объекты без вызова конструктора, является плохим C ++ (возможно, недействительным - я оставлю это юристам по языку).

Тем не менее, простое изменение malloc на new Pixel[dimensions*dimensions]и free на delete [] pixelsне имеет большого значения с простой реализацией Pixel, которая у вас есть. Вот результаты на моей коробке (E6600, 64-битная версия):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Но с небольшим изменением таблицы поворачиваются:

Pixel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Скомпилировано так:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

мы получаем очень разные результаты:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

С помощью встроенного конструктора для Pixel std :: vector теперь превосходит необработанный массив.

Может показаться, что сложность выделения через std :: vector и std: allocator слишком велика, чтобы ее можно было оптимизировать так же эффективно, как и простую new Pixel[n]. Тем не менее, мы видим, что проблема заключается просто в распределении, а не в доступе к вектору, путем настройки нескольких тестовых функций для создания вектора / массива один раз путем перемещения его за пределы цикла:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

и

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Мы получаем эти результаты сейчас:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Из этого мы можем узнать, что std :: vector сравним с необработанным массивом для доступа, но если вам нужно многократно создавать и удалять вектор / массив, создание сложного объекта займет больше времени, чем создание простого массива. когда конструктор элемента не встроен. Я не думаю, что это очень удивительно.

Попробуйте с этим:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Я получаю почти такую ​​же производительность, как с массивом.

Дело в том, vectorчто это гораздо более общий инструмент, чем массив. А это значит, что вы должны подумать как вы его используете. Его можно использовать по-разному, предоставляя функции, которых у массива даже нет. И если вы используете это «неправильно» для своих целей, вы несете много накладных расходов, но если вы используете это правильно, это обычно в основном структура данных с нулевыми издержками. В этом случае проблема заключается в том, что вы отдельно инициализируете вектор (в результате чего для всех элементов вызывается их ctor по умолчанию), а затем перезаписываете каждый элемент по отдельности с правильным значением. Компилятору гораздо сложнее оптимизировать, чем когда вы делаете то же самое с массивом. Вот почему вектор предоставляет конструктор, который позволяет вам делать именно это: .NX

И когда вы используете это, вектор так же быстро, как массив.

Так что нет, вы не разрушили миф о производительности. Но вы показали, что это верно только в том случае, если вы используете вектор оптимально, что тоже довольно неплохо. :)

С другой стороны, это действительно простое использование, которое оказывается самым быстрым. Если вы сравните мой фрагмент кода (единственную строку) с ответом Джона Кугельмана, содержащим кучи и кучу настроек и оптимизаций, которые до сих пор не совсем устраняют разницу в производительности, то становится ясно, что vectorвсе-таки довольно умно разработан. Вам не нужно прыгать через обручи, чтобы получить скорость, равную массиву. Наоборот, вы должны использовать самое простое решение.

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

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

Я думал, что при такой настройке они должны быть точно такими же. Оказывается, я был не прав.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

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

Я думал, что именно так цикл инициализирует все значения конструктору по умолчанию. Итак, я выполнил тест:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Результаты были, как я и подозревал:

Default Constructed: 1
Copy Constructed: 300

Это явно источник замедления, тот факт, что вектор использует конструктор копирования для инициализации элементов из созданного по умолчанию объекта.

Это означает, что при построении вектора происходит следующий порядок псевдоопераций:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Который, благодаря неявному конструктору копирования, созданному компилятором, расширен до следующего:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

Таким образом , по умолчанию Pixelостается не-инициализирован, в то время как остальные инициализируются с по умолчанию Pixel«s не-инициализируются значения.

По сравнению с альтернативной ситуацией с New[]/ Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Все они оставлены на их неинициализированные значения и без двойной итерации по последовательности.

Вооружившись этой информацией, как мы можем ее проверить? Давайте попробуем переписать неявный конструктор копирования.

Pixel(const Pixel&) {}

И результаты?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Итак, подведем итог: если вы часто создаете сотни векторов, переосмыслите свой алгоритм .

В любом случае реализация STL не медленнее по неизвестной причине, она просто делает то, что вы просите; надеюсь, что вы знаете лучше.

Попробуйте отключить проверенные итераторы и построить в режиме релиза. Вы не должны видеть большую разницу в производительности.

В GNU STL (и других), заданный по vector<T>(n)умолчанию, создается прототип объекта T()- компилятор оптимизирует пустой конструктор, но затем копия того мусора, который оказался в адресах памяти, теперь зарезервированных для объекта, берется STL.__uninitialized_fill_n_aux , что циклы, заполняющие копии этого объекта в качестве значений по умолчанию в векторе. Итак, «мой» STL - это не циклическое конструирование, а конструирование затем циклическое копирование. Это противоречит интуиции, но я должен был вспомнить, как я прокомментировал недавний вопрос о стековом потоке по этому поводу: конструкция / копия может быть более эффективной для объектов с подсчетом ссылок и т. Д.

Так:

vector<T> x(n);

или

vector<T> x;
x.resize(n);

это - на многих реализациях STL - что-то вроде:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

Проблема заключается в том, что текущее поколение оптимизаторов компилятора, похоже, не работает из-за понимания, что temp является неинициализированным мусором, и не может оптимизировать вызовы цикла и вызовы конструктора копирования по умолчанию. Вы могли бы с уверенностью утверждать, что компиляторы абсолютно не должны оптимизировать это, поскольку программист, пишущий выше, имеет разумное ожидание, что все объекты будут идентичны после цикла, даже если мусор (обычные предостережения о «тождественном» / operator == vs memcmp / operator = и т.д. применяются). Нельзя ожидать, что компилятор будет иметь какое-либо дополнительное понимание более широкого контекста std :: vector <> или более позднего использования данных, которое предполагает безопасную оптимизацию.

Это можно противопоставить более очевидной прямой реализации:

for (int i = 0; i < n; ++i)
    x[i] = T();

Что мы можем ожидать от компилятора для оптимизации.

Чтобы быть немного более явным в обосновании этого аспекта поведения вектора, рассмотрим:

std::vector<big_reference_counted_object> x(10000);

Очевидно, что это большая разница, если мы создадим 10000 независимых объектов против 10000 ссылок на одни и те же данные. Существует разумный аргумент, что преимущество защиты случайных пользователей C ++ от случайного выполнения чего-либо столь дорогостоящего перевешивает очень небольшую реальную стоимость трудно оптимизируемой конструкции копирования.

ОРИГИНАЛЬНЫЙ ОТВЕТ (для справки / понимания комментариев): Нет шансов. вектор так же быстр, как массив, по крайней мере, если вы разумно резервируете пространство. ...

Ответ Мартина Йорка беспокоит меня, потому что это похоже на попытку отмахнуться от проблемы инициализации под ковром. Но он прав, если определит избыточную конструкцию по умолчанию как источник проблем с производительностью.

[РЕДАКТИРОВАТЬ: ответ Мартина больше не предлагает изменить конструктор по умолчанию.]

Для решения ближайшей проблемы вы, конечно, могли бы vector<Pixel>вместо этого вызвать 2-параметрическую версию ctor:

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Это работает, если вы хотите инициализировать с постоянным значением, что является распространенным случаем. Но более общая проблема заключается в следующем: как эффективно инициализировать что-то более сложное, чем постоянное значение?

Для этого вы можете использовать back_insert_iteratorадаптер-итератор. Вот пример с вектором ints, хотя общая идея работает так же хорошо для Pixels:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

В качестве альтернативы вы можете использовать copy()или transform()вместо generate_n().

Недостатком является то, что логику для конструирования начальных значений необходимо перенести в отдельный класс, что менее удобно, чем иметь его на месте (хотя лямбда-выражения в C ++ 1x делают это намного приятнее). Кроме того, я ожидаю, что это все равно будет не так быстро, как на malloc()основе не-STL версии, но я ожидаю, что это будет близко, так как он только делает одну конструкцию для каждого элемента.

Векторные дополнительно называют конструкторами Pixel.

Каждый из них вызывает почти миллион циклов, которые вы рассчитываете.

edit: тогда есть внешний цикл 1 ... 1000, так что сделайте, чтобы миллиард ctor звонил!

edit 2: было бы интересно увидеть разборку для случая UseArray. Оптимизатор может оптимизировать все это, так как он не имеет никакого эффекта, кроме горения процессора.

Вот как работает push_backметод в векторе:

1. Вектор выделяет количество X пространства при его инициализации.
2. Как указано ниже, он проверяет, есть ли место в текущем базовом массиве для элемента.
3. Создает копию элемента в вызове push_back.

После вызова push_backX предметов:

3. Вектор перераспределяет kX количество пространства во 2-й массив.
4. Копирует записи первого массива во второй.
5. Сбрасывает первый массив.
6. Теперь второй массив используется как хранилище, пока не достигнет kX записей.

Повторение. Если вы не в reservingкосмосе, это определенно будет медленнее. Более того, если копировать предмет дорого, то «push_back» как будто съест вас заживо.

Что касается vector вещи против массива, мне придется согласиться с другими людьми. Запустите в выпуске, включите оптимизацию и добавьте еще несколько флагов, чтобы дружелюбные люди в Microsoft не поняли вас.

Еще одна вещь, если вам не нужно изменять размер, используйте Boost.Array.

Некоторые данные профилировщика (пиксель выровнен до 32 бит):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

вздор

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

В allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector:

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

массив

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

Большая часть накладных расходов находится в конструкторе копирования. Например,

    std::vector < Pixel > pixels;//(dimension * dimension, Pixel());

    pixels.reserve(dimension * dimension);

    for (int i = 0; i < dimension * dimension; ++i) {

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Он имеет ту же производительность, что и массив.

Мой ноутбук - Lenova G770 (4 ГБ оперативной памяти).

ОС Windows 7 64-битная (та, что с ноутбуком)

Компилятор MinGW 4.6.1.

Средой разработки является Code :: Blocks .

Я тестирую исходники первого поста.

Результаты

O2 оптимизация

Использование массива завершено за 2,841 секунды

UseVector завершен за 2,548 секунды

UseVectorPushBack завершено за 11,95 секунд

Все завершено за 17,342 секунды

системная пауза

O3 оптимизация

Использование массива завершено за 1.452 секунды

UseVector завершен за 2,514 секунды

UseVectorPushBack завершено за 12,967 секунд

Все закончено за 16,937 секунд

Похоже, производительность вектора хуже при оптимизации O3.

Если вы измените цикл на

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

Скорость массива и вектора под O2 и O3 практически одинаковы.

Лучший тест (я думаю ...), компилятор за счет оптимизации может изменить код, потому что результаты распределенных векторов / массивов нигде не используются. Полученные результаты:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Составитель:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

ЦПУ:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

И код:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        results[i] = pixels;

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

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

Это моя машина с двойной загрузкой i7-3770, Ram 16 ГБ, x86_64, на Windows 8.1 и на Ubuntu 16.04. Более подробная информация и выводы, замечания ниже. Протестировано как MSVS 2017, так и g ++ (как на Windows, так и на Linux).

Тестовая программа

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Полученные результаты

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Ноты

• Собран в среднем за 10 прогонов.
• Сначала я std::sort()тоже проводил тесты (вы можете видеть это закомментировано), но позже удалил их, потому что не было значительных относительных различий.

Мои выводы и замечания

• обратите внимание, что глобальный массив c-style занимает почти столько же времени, сколько массив heap c-style
• Из всех тестов я заметил замечательную стабильность в std::array временных вариаций между последовательными запусками, в то время как другие, особенно структуры std :: data, сильно отличались по сравнению
• Оптимизация O3 не показала заметных временных различий
• Удаление оптимизации в Windows cl (нет -O2) и в g ++ (в Win / Linux нет -O2, нет -march = native) значительно увеличивается в разы. Особенно для структур std :: data. В целом более высокие времена на MSVS, чем на g ++, но std::arrayи массивы в стиле c быстрее на Windows без оптимизации
• G ++ производит более быстрый код, чем компилятор Microsoft (очевидно, он работает быстрее даже в Windows).

решение суда

Конечно, это код для оптимизированной сборки. И так как вопрос был оstd::vector да то да! Много! медленнее, чем простые массивы (оптимизированные / неоптимизированные). Но когда вы делаете тест, вы, естественно, хотите создавать оптимизированный код.

Звезда шоу для меня хоть и была std::array.

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

Кстати, замедление просмотра в классах с использованием вектора также происходит со стандартными типами, такими как int. Вот многопоточный код:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

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

Кстати игнорируйте абсолютно безумное количество включений. Я использовал этот код для тестирования проекта, поэтому число включений продолжает расти.

Я просто хочу упомянуть, что vector (и smart_ptr) - это просто добавление тонкого слоя поверх необработанных массивов (и необработанных указателей). И на самом деле время доступа вектора в непрерывной памяти быстрее, чем в массиве. Следующий код показывает результат инициализации и доступа к вектору и массиву.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

Выход:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Так что скорость будет почти такой же, если вы используете ее правильно. (как другие упоминали, используя Reserve () или Resize ()).

Ну, потому что vector :: resize () выполняет намного больше обработки, чем обычное выделение памяти (по malloc).

Попробуйте установить точку останова в конструкторе копирования (определите ее так, чтобы вы могли использовать точку останова!), И тогда уйдет дополнительное время обработки.

Я должен сказать, что я не эксперт в C ++. Но чтобы добавить некоторые результаты экспериментов:

компилировать: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

машина:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

ОПЕРАЦИОННЫЕ СИСТЕМЫ:

2.6.32-642.13.1.el6.x86_64

Вывод:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Здесь единственное, что мне кажется странным, - это производительность UseFillConstructor по сравнению с UseConstructor.

Код:

void UseConstructor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension);
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}


void UseFillConstructor()
{
    TestTimer t("UseFillConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension*dimension, Pixel(255,0,0));
    }
}

Таким образом, дополнительное «значение» значительно снижает производительность, что, я думаю, связано с многократным вызовом конструктора копирования. Но...

Обобщение:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Вывод:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

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

Кажется, это зависит от флагов компилятора. Вот эталонный код:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Различные флаги оптимизации дают разные ответы:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

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

По моему опыту, иногда, просто иногда, vector<int>может быть во много раз медленнее, чем int[]. Следует помнить, что векторы векторов очень разные int[][]. Поскольку элементы, вероятно, не являются смежными в памяти. Это означает, что вы можете изменять размеры разных векторов внутри основного, но ЦП может не иметь возможности кэшировать элементы так же, как и в случае int[][].