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

212

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

kizzx2
источник
23
В некоторых версиях vector, когда вы находитесь в режиме отладки, добавьте дополнительные инструкции, чтобы убедиться, что у вас нет доступа за пределами массива, и тому подобное. Чтобы получить реальные сроки, вы должны встроить режим релиза и включить оптимизацию.
Мартин Йорк,
40
Это хорошо, что вы измерили вместо того, чтобы верить заявлениям, которые вы услышали в Интернете
P Швед
51
вектор будет реализован в виде массива. Это не "общепринятая мудрость", это правда. Вы обнаружили, что vectorэто массив общего назначения с изменяемыми размерами. Поздравляю. Как и со всеми инструментами общего назначения, можно придумать специализированные ситуации, когда они неоптимальны. Вот почему общепринятая мудрость заключается в том, чтобы начать с vectorи рассмотреть альтернативы, если это необходимо.
Деннис Зикефуз
37
смеется, какова разница в скорости «бросания грязной посуды в раковину» и «бросания грязной посуды в раковину и проверки, не сломались ли они»?
Imre L
9
По крайней мере, на VC2010 кажется, что главное отличие в том, что malloc () быстрее, чем resize (). Удалите выделение памяти из времени, скомпилируйте с _ITERATOR_DEBUG_LEVEL == 0, и результаты будут такими же.
Андреас Магнуссон

Ответы:

260

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

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

Loki Astari
источник
48
@ kizzx2: Вам нужно использовать reserve()вместо resize(). Это выделяет пространство для объектов (то есть изменяет емкость вектора), но не создает объекты (то есть размер вектора остается неизменным).
Джеймс МакНеллис
25
Вы делаете 1 000 000 000 обращений к массиву. Разница во времени составляет 0,333 секунды. Или разница в 0,000000000333 для доступа к массиву. Предполагая, что процессор с тактовой частотой 2,33 ГГц, как мой, имеет 0,7 ступени конвейера команд на каждый доступ к массиву. Таким образом, вектор выглядит так, как будто он использует одну дополнительную инструкцию для доступа.
Мартин Йорк,
3
@James McNellis: Вы не можете просто заменить resize()на reserve(), потому что это не корректирует внутреннее представление вектора о его собственном размере, поэтому последующие записи в его элементы технически «записывают за конец» и приводят к UB. Хотя на практике каждая реализация STL будет «вести себя» в этом отношении, как вы синхронизируете размер вектора? Если вы попытаетесь вызвать resize() после заполнения вектора, вполне вероятно, что все эти элементы будут перезаписаны значениями, созданными по умолчанию!
j_random_hacker
8
@j_random_hacker: Разве это не то, что я сказал? Мне показалось, что мне очень ясно, что reserveменяется только емкость вектора, а не его размер.
Джеймс МакНеллис
7
Хорошо, пойди разберись. В векторных методах было много ошибок, связанных с исключениями. Добавление /EHscк ключам компиляции убрало это, и assign()фактически превосходит массив. Ура.
Павел Минаев
55

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

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

Джон Кугельман
источник
2
Опять же, спасибо за фактический запуск кода. Иногда легко получить травму без причины, когда кто-то пытается бросить вызов популярному мнению.
kizzx2
3
«Так много для того, чтобы компилятор был достаточно умен, чтобы оптимизировать все возможности C ++ и сделать контейнеры STL такими же быстрыми, как необработанные массивы». Хорошие комментарии. У меня есть теория, что этот «умный компилятор» - просто миф - синтаксический анализ C ++ чрезвычайно сложен, а компилятор - просто машина.
kizzx2
3
Понятия не имею. Конечно, он смог замедлить тест массива, но он не ускорил векторный тест . Я редактировал выше, где я удалил конструкторы из Pixel и сделал его простой структурой, и это было все еще медленно. Это плохая новость для тех, кто использует простые типы, такие как vector<int>.
Джон Кугельман
2
Хотелось бы, чтобы я мог дважды подтвердить ваш ответ. Умные идеи, чтобы попробовать (хотя никто не работал), что я даже не мог придумать!
kizzx2
9
Просто хотел отметить, что сложность парсинга C ++ (который безумно сложен, да) не имеет ничего общего с качеством оптимизации. Последнее обычно происходит на этапах, когда результат анализа уже много раз трансформируется в гораздо более низкоуровневое представление.
Павел Минаев
44

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

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

Якк - Адам Невраумонт
источник
Также было бы интересно посмотреть, как здесь emplace_backпротив push_back.
Даниэль
1
Я не могу воспроизвести ваши результаты. Компиляция вашего кода clang++ -std=c++11 -O3имеет UseArray completed in 2.02e-07 secondsи UseVector completed in 1.3026 seconds. Я также добавил UseVectorEmplaceBackверсию, которая составляет ок. В 2,5 раза быстрее UseVectorPushBack.
Даниэль
1
@daniel odds - оптимизатор удалил все из версии массива. Всегда риск с микро тестами.
Якк - Адам Невраумонт
4
да, вы правы, просто посмотрел на сборку (или ее отсутствие) .. Наверное, должен был подумать об этом, учитывая разницу ~ 6448514x! Интересно, почему векторная версия не может выполнить такую ​​же оптимизацию? Она делает это, если построена с размерами, а не с измененным размером.
Даниэль
34

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

CAMH
источник
3
У вас все еще есть встроенный конструктор - конструктор копирования.
Бен Фойгт
26

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

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

jalf
источник
1
Я все еще сомневаюсь, что это справедливое сравнение. Если вы избавляетесь от внутреннего цикла, то эквивалент массива будет состоять в том, чтобы создать один объект Pixel, а затем скопировать его по всему массиву.
Джон Кугельман
1
Использование new[]выполняет те же конструкции по умолчанию, что vector.resize()и при этом, но гораздо быстрее. new[]+ внутренний цикл должен быть такой же скорости, как и vector.resize()+ внутренний цикл, но это не так, он почти в два раза быстрее.
Джон Кугельман
@Джон: это честное сравнение. В исходном коде выделен массив, mallocкоторый ничего не инициализирует и не создает, поэтому он, по сути, является однопроходным алгоритмом, как и мой vectorпример. А что касается new[]ответа, очевидно, что оба требуют двух проходов, но в этом new[]случае компилятор может оптимизировать эти дополнительные издержки, чего не происходит в этом vectorслучае. Но я не понимаю, почему интересно, что происходит в неоптимальных случаях. Если вы заботитесь о производительности, вы не пишете такой код.
Джалф
@ Джон: Интересный комментарий. Если бы я хотел перетаскивать весь массив, я думаю, что массив снова является оптимальным решением - поскольку я не могу сказать, vector::resize()чтобы дать мне много памяти, не тратя время на вызов бесполезных конструкторов.
kizzx2
@ kizzx2: да и нет. Массив обычно инициализируется также в C ++. В C вы бы использовали, mallocкоторый не выполняет инициализацию, но это не будет работать в C ++ с не POD-типами. Так что в общем случае массив C ++ будет таким же плохим. Возможно, вопрос в том, что если вы собираетесь часто выполнять этот процесс, не будете ли вы использовать один и тот же массив / вектор? И если вы сделаете это, то вы заплатите стоимость «бесполезных конструкторов» только один раз, в самом начале. Фактически блиттинг так же быстр в конце концов.
Джалф
22

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

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

deceleratedcaviar
источник
3
Судя по тому веселью, которое у нас (у нас с вами и у других умных людей) было, «надежда» реализации STL действительно довольно требовательна: P По сути, мы можем преувеличить и сделать вывод, что она надеется, что я прочитал и проанализировал все ее источники код. Во всяком случае: P
kizzx2
1
Awsome! В VS 2013 это делало вектор быстрее, чем массивы. Хотя кажется, что для систем, критичных к производительности, вам нужно много тестировать STL, чтобы иметь возможность эффективно его использовать.
Розина
7

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

kloffy
источник
1
Пробовал #define _SECURE_SCL 0. Это сделало UseVectorгде-то около 4 секунд (похоже на gccниже), но все же это в два раза медленнее.
kizzx2
Это почти наверняка причина. Microsoft любезно поддерживает отладку по умолчанию для отладки и выпуска. Мы обнаружили, что это стало основной причиной значительного замедления после обновления с 2003 по 2008 год. Определенно, это одна из самых пагубных ошибок визуальной студии.
Дуг Т.
2
@ kizzx2 есть еще один макрос для отключения: HAS_ITERATOR_DEBUGGING или что-то подобное.
Дуг Т.
Как показывают @Martin и мои ответы, gcc показывает тот же шаблон, даже с оптимизацией при -O3.
Джон Кугельман
1
@Doug: Глядя на документ, я думаю, что _HAS_ITERATOR_DEBUGGINGон отключен в сборке релиза: msdn.microsoft.com/en-us/library/aa985939(VS.80).aspx
kizzx2
4

В 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 ++ от случайного выполнения чего-либо столь дорогостоящего перевешивает очень небольшую реальную стоимость трудно оптимизируемой конструкции копирования.

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

Тони Делрой
источник
6
Я действительно не могу оправдать, что этот ответ хоть немного полезен для кого-либо. Я надеюсь, что смогу понизить голос дважды.
kizzx2
-1, там идет моя поддержка на kizzx2. вектор никогда не будет таким же быстрым как массив из-за дополнительной функции, которую он предоставляет, правило вселенной, у всего есть цена!
YeenFei
Ты пропускаешь, Тони ... это пример искусственного теста, но он доказывает, к чему он стремится.
Potatoswatter
Розы зеленые, фиалки оранжевые, отрицательные голоса горькие, но ответ напрашивается на них.
Павел Минаев
3

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

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

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

j_random_hacker
источник
2

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

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

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

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

Грэм Перкс
источник
Вы правы, но вопрос в том: как отключить эти бессмысленные вызовы ctor? Это легко для подхода без STL, но трудно / безобразно для подхода STL.
j_random_hacker
1

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

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

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

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

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

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

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

Wheaties
источник
Я понимаю, что людям не нравится читать кучу кода, когда он публикуется дословно. Но я использовал, reserveкак я должен.
kizzx2
Извините, я пропустил это. Неужели я больше ничего не помогал?
2010 года
push_backамортизировала постоянное время. Похоже, вы описываете процесс O (N). (Шаги 1 и 3 кажутся совершенно неуместными.) Что push_backзамедляет OP, так это проверка диапазона, чтобы увидеть, должно ли произойти перераспределение, обновление указателей, проверка NULL внутри размещения newи другие мелочи, которые обычно заглушаются фактическая работа программы.
Potatoswatter
Это будет медленнее даже с тем, reserveчто он все еще должен делать эту проверку (нужно ли это перераспределять) на каждом push_back.
Павел Минаев
Все хорошие моменты. То, что я описываю, звучит как процесс O (N), но это не так, ну не совсем. Большинство людей, которых я знаю, не понимают, как vectorвыполняет функцию изменения размера, это просто «волшебство». Здесь, позвольте мне прояснить это немного больше.
пшеница
1

Некоторые данные профилировщика (пиксель выровнен до 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;
    }

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

Anycorn
источник
2
К сожалению, после того, как «решение», которое вы дали, pixels.size()будет сломано.
kizzx2
1
это неправильно, вы не можете вызвать резерв и затем использовать элементы, вы все равно должны использовать push_back для добавления элементов
paulm
1

Мой ноутбук - 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 практически одинаковы.

StereoMatching
источник
Даже когда я изменяю malloc на new, в первом тестовом примере под O3 производительность вектора по-прежнему ниже, чем у массива. Но при изменении значения присваивания с (255, 0, 0) на (i, i, i) производительность вектор и массив почти одинаковы для O2 и O3, это довольно странно
StereoMatching
Извините, я забываю сменить free на delete. После смены free для удаления производительность под O3 вектора и массива теперь одинакова, похоже, распределитель - главная причина?
StereoMatching
1

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

$ 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;
}
Михал Щепаняк
источник
1

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

Это моя машина с двойной загрузкой 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.

Nikos
источник
0

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


источник
1
В этом случае они, похоже, не генерируют одну и ту же сборку. В частности, кажется, что нет способа подавить вызов конструкторов, использующих векторы. Вы можете обратиться к ответам здесь для этой проблемы (это длинное чтение, но оно объясняет, почему существует разница в производительности в случаях, отличных от простого теста в приведенной вами ссылке.) (На самом деле, кажется, что есть способ - - написание собственного распределителя STL, как было предложено. Лично я считаю, что это излишне больше работы, чем использование malloc)
kizzx2
1
@ kizzx2: То, что вы должны идти на все, чтобы использовать неструктурированные объекты, - это хорошо, потому что это ошибка 99% (я могу быть сильно недооценена) времени. Я прочитал другие ответы и понял, что не обращаюсь к вашей конкретной ситуации (нет необходимости, другие ответы верны), но я все же хотел представить вам этот пример того, как векторы и массивы могут вести себя точно так же.
@ Роджер: это здорово! Спасибо за ссылку
kizzx2 26.09.10
0

Кстати, замедление просмотра в классах с использованием вектора также происходит со стандартными типами, такими как 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;
}

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

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

Захария Крауса
источник
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 ()).

Чарльз Чоу
источник
0

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

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

YeenFei
источник
0

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

user2189731
источник
0

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

#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

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

shuhalo
источник
0

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

Mгор ме
источник