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

Question

Я всегда думал, что это общая мудрость, что 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 секунд). Это действительно огромно, ИМО.

Answer 1

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

g ++ -O3 Time.cpp -I
./a.out
Использование массива завершено за 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
./a.out
UseVector завершено за 2,216 секунды

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

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

Answer 2

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

Оптимизация помогает, но этого недостаточно. С оптимизацией я все еще вижу разницу в производительности в 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% быстрее. Все еще медленнее, чем массив. Hm.

# ./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. Не беспокойтесь об этом».

Answer 3

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

На данный момент многие программисты будут работать на 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 также выполняет проверку ограждения, что замедляет его, поэтомуон остается медленнее, чем malloc версия.

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

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

Answer 4

Если честно, вы не можете сравнить реализацию 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 сопоставим с необработанным массивом для доступа, но если вам нужно многократно создавать и удалять вектор / массив, создание сложного объекта займет больше времени, чем создание простой массив, когда конструктор элемента не встроен. Я не думаю, что это очень удивительно.

Answer 5

Попробуйте с помощью этого:

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 по умолчанию), а затем перезаписываете каждый элемент по отдельности с правильным значением.Компилятору гораздо сложнее оптимизировать, чем когда вы делаете то же самое с массивом.Вот почему вектор предоставляет конструктор, который позволяет вам делать именно это: инициализировать N элементов со значением X.

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

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

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

Answer 6

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

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 неинициализированные значения.

По сравнению с альтернативной ситуацией с 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 не замедляется по неизвестной причине, она просто выполняет то, что вы просите;надеясь, что ты знаешь лучше.

Answer 7

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

Answer 8

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 == vsmemcmp / operator = и т.д. применяются).Нельзя ожидать, что компилятор получит какое-либо дополнительное понимание более широкого контекста std :: vector <> или более позднего использования данных, которое предполагает безопасную оптимизацию.

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

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

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

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

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

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

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

Answer 9

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

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

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

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

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

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

#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-версии, но я ожидаю, что она будет близкой, так как она делает только одну конструкцию для каждого элемента.

Answer 10

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

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

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

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