Использование массивов или std::vectors в С++, что такое разрыв производительности?

Ответ 1

Использование С++-массивов с new (то есть с использованием динамических массивов) следует избегать. Существует проблема, которую вы должны отслеживать размер, и вам нужно удалить их вручную и сделать все виды домашнего хозяйства.

Использование массивов в стеке также обескураживается, потому что у вас нет проверки диапазона, и передача массива будет потерять любую информацию о его размере (преобразование массива в указатель). Вы должны использовать boost::array в этом случае, который обертывает массив С++ в небольшом классе и предоставляет функцию size и итераторы для итерации по ней.

Теперь std::vector и собственные С++-массивы (взяты из Интернета):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Примечание. Если вы выделяете массивы с помощью new и выделяете объекты без класса (например, plain int) или классы без определенного пользователем конструктора, и вы не хотите, чтобы ваши инициализированные элементы были первоначально инициализированы, используя new -распределенные массивы могут иметь преимущества производительности, поскольку std::vector инициализирует все элементы значениями по умолчанию (0 для int, например) при построении (кредиты для @bernie для запоминания меня).

Ответ 2

Преамбула для пользователей микро-оптимизатора

Помните:

"Программисты тратят огромное количество времени на размышления о скорости некритических частей своих программ или беспокоятся о скорости их некритических частей, и эти попытки эффективности действительно оказывают сильное негативное влияние при отладке и обслуживании. Мы должны забыть о небольшой эффективности, скажем, около 97% времени: преждевременная оптимизация - корень всего зла. Но мы не должны упускать наши возможности в этих критических 3%".

(Благодаря metamorphosis для полной цитаты)

Не используйте массив C вместо вектора (или что-то еще) только потому, что вы считаете его быстрее, поскольку он должен быть более низким. Вы ошибаетесь.

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

Это говорит о том, что мы можем вернуться к первоначальному вопросу.

Статический/динамический массив?

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

В общем, он относится к двум категориям:

Динамические массивы

Использование указателя на массив malloc-ed/new-ed будет в лучшем случае быстрее, чем версия std::vector, и намного менее безопасна (см. litb post).

Поэтому используйте std::vector.

Статические массивы

Использование статического массива будет в лучшем случае:

• так же быстро, как std:: array version
• и намного менее безопасно.

Поэтому используйте std:: array.

Неинициализированная память

Иногда использование vector вместо необработанного буфера несет видимую стоимость, потому что vector будет инициализировать буфер при построении, тогда как код, который он заменяет, не сделал, как отмечено bernie в ответе .

Если это так, вы можете обрабатывать его с помощью unique_ptr вместо vector или, если этот случай не является исключительным в вашей кодовой линии, на самом деле напишите класс buffer_owner, который будет владеть этой памятью, и дать вам легкий и безопасный доступ к нему, включая бонусы, такие как изменение размера (используя realloc?) или все, что вам нужно.

Ответ 3

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

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

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

Если ваша конструкция/деструкция дорогая, вам гораздо лучше сделать вектор правильного размера для начала.

Существует простой способ продемонстрировать это. Создайте простой класс, который показывает, когда он создан/уничтожен/скопирован/назначен. Создайте вектор этих вещей и начните толкать их на заднем конце вектора. Когда вектор заполняется, будет существовать каскад активности по мере изменения размера вектора. Затем повторите попытку с вектором, соответствующим ожидаемому числу элементов. Вы увидите разницу.

Ответ 4

Чтобы ответить на что-то Мехрдад сказал:

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

Не совсем. Векторы красиво делятся на массивы/указатели, если вы используете:

vector<double> vector;
vector.push_back(42);

double *array = &(*vector.begin());

// pass the array to whatever low-level code you have

Это работает для всех основных реализаций STL. В следующем стандарте он должен будет работать (хотя сегодня он отлично работает).

Ответ 5

У вас еще меньше причин использовать простые массивы в С++ 11.

Есть 3 типа массивов в природе от самых быстрых до самых медленных, в зависимости от особенностей, которые у них есть (конечно, качество реализации может сделать вещи действительно быстрыми даже для случая 3 в списке):

• Статический размер, известный во время компиляции. --- std::array<T, N>
• Динамический размер, известный во время выполнения и никогда не изменяющийся. Типичная оптимизация здесь заключается в том, что если массив может быть выделен в стеке напрямую. - Недоступно. Может быть, dynarray в С++ TS после С++ 14. В C есть VLA
• Динамический и изменяемый размер во время выполнения. --- std::vector<T>

Для 1. простых статических массивов с фиксированным количеством элементов используйте std::array<T, N> в С++ 11.

Для 2. массивов фиксированного размера, указанных во время выполнения, но это не изменит их размер, в С++ 14 есть обсуждение, но оно было перенесено в техническую спецификацию и составлено из Наконец, С++ 14.

Для 3. std::vector<T> обычно запрашивает память в куче. Это может иметь последствия для производительности, хотя вы можете использовать std::vector<T, MyAlloc<T>> для улучшения ситуации с помощью настраиваемого распределителя. Преимущество по сравнению с T mytype[] = new MyType[n]; заключается в том, что вы можете изменить его размер и что он не будет распадаться на указатель, как это делают обычные массивы.

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

Ответ 6

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

Ответ 7

STL - это сильно оптимизированная библиотека. Фактически, он даже предложил использовать STL в играх, где может потребоваться высокая производительность. Массивы слишком подвержены ошибкам, которые могут использоваться в повседневных задачах. Сегодня компиляторы также очень умны и могут действительно создавать отличный код с STL. Если вы знаете, что делаете, STL обычно может обеспечить необходимую производительность. Например, инициализируя векторы требуемым размером (если вы знаете с начала), вы можете в основном добиться производительности массива. Однако могут быть случаи, когда вам все еще нужны массивы. При взаимодействии с низкоуровневым кодом (например, сборкой) или старыми библиотеками, требующими массивы, вы, возможно, не сможете использовать векторы.

Ответ 8

О вкладе duli.

Вывод состоит в том, что массивы целых чисел быстрее, чем векторы целых чисел (5 раз в моем примере). Тем не менее, массивы и векторы имеют одинаковую скорость для более сложных/не выровненных данных.

Ответ 9

Если вы компилируете программное обеспечение в режиме отладки, многие компиляторы не будут встраивать функции доступа вектора. Это приведет к тому, что реализация stl-вектора будет намного медленнее при обстоятельствах, когда производительность является проблемой. Это также упростит отладку кода, поскольку вы можете видеть в отладчике, сколько памяти было выделено.

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

Ответ 10

Определенно влияние производительности на использование std::vector по сравнению с необработанным массивом, если вы хотите использовать неинициализированный буфер (например, использовать в качестве адресата для memcpy()). std::vector инициализирует все свои элементы с помощью конструктора по умолчанию. Необработанный массив не будет.

спецификация С++ для конструктора std:vector, принимающего аргумент count (это третья форма), гласит:

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

3) Создает контейнер со значениями, установленными по умолчанию для экземпляров T. Копии не создаются.

Сложность

2-3) Линейный счетчик

Необработанный массив не несет этой стоимости инициализации.

См. также Как я могу избежать std::vector < > для инициализации всех его элементов?

Ответ 11

Разница в производительности между ними очень зависит от реализации - если вы сравните плохо реализованный std::vector с оптимальной реализацией массива, массив победит, а повернет его, и вектор победит...

Пока вы сравниваете яблоки с яблоками (либо массив, и вектор имеют фиксированное количество элементов, либо оба динамически изменяются), я думаю, что разница в производительности пренебрежимо мала, если вы будете следовать практике кодирования STL, Не забывайте, что использование стандартных контейнеров С++ также позволяет использовать предварительно прокатанные алгоритмы, которые являются частью стандартной библиотеки С++, и большинство из них, вероятно, будут лучше работать, чем средняя реализация того же алгоритма, который вы сами создаете.

Тем не менее, ИМХО, вектор выигрывает в сценарии отладки с отладочным STL, поскольку большинство реализаций STL с надлежащим режимом отладки могут по крайней мере выделить /cathc типичные ошибки, допущенные людьми при работе со стандартными контейнерами.

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

Ответ 12

Если вам не нужно динамически настраивать размер, у вас есть накладные расходы памяти для сохранения емкости (один указатель/размер_t). Что это.

Ответ 13

Может существовать некоторый крайний случай, когда у вас есть векторный доступ внутри встроенной функции внутри встроенной функции, где вы вышли за пределы встроенного компилятора, и это вызовет вызов функции. Это было бы настолько редко, что не стоит беспокоиться - в общем, я согласен с litb.

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

Ответ 14

Иногда массивы действительно лучше, чем векторы. Если вы всегда манипулируете набор объектов с фиксированной длиной, массивы лучше. Рассмотрим следующие фрагменты кода:

int main() {
int v[3];
v[0]=1; v[1]=2;v[2]=3;
int sum;
int starttime=time(NULL);
cout << starttime << endl;
for (int i=0;i<50000;i++)
for (int j=0;j<10000;j++) {
X x(v);
sum+=x.first();
}
int endtime=time(NULL);
cout << endtime << endl;
cout << endtime - starttime << endl;

}

где векторная версия X есть

class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};

а версия массива X:

class X {
int f[3];

public:
X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];}
int first() { return f[0];}
};

Версия массива main() будет быстрее, потому что мы избегаем накладные расходы "нового" каждый раз во внутреннем цикле.

(Этот код был отправлен на comp.lang.С++ мной).

Ответ 15

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

Ответ 16

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

Ответ 17

Следующий простой тест:

С++ Array vs Vector описание теста производительности

противоречит выводам из "Сравнение кода сборки, сгенерированного для базового индексирования, разыменования и операций инкремента по векторам и массивам/указателям".

Между массивами и векторами должна быть разница. Тест говорит так... просто попробуйте, код там...

Ответ 18

Если вы используете векторы для представления многомерного поведения, производительность снижается.

Приводят ли векторы 2d+ к снижению производительности?

Суть в том, что существует небольшой объем служебной информации, когда каждый субвектор имеет информацию о размере, и не обязательно будет сериализация данных (как в случае многомерных массивов c). Это отсутствие сериализации может предложить больше возможностей, чем микрооптимизация. Если вы работаете с многомерными массивами, лучше всего просто расширить std :: vector и запустить собственную функцию get/set/resize bits.

Ответ 19

Предполагая массив фиксированной длины (например, int* v = new int[1000]; vs std::vector<int> v(1000); с фиксированным размером v, равным 1000), единственное соображение производительности, которое действительно вопросы (или, по крайней мере, для меня имели значение, когда я сталкивался с подобной дилеммой) - это скорость доступа к элементу. Я посмотрел векторный код STL, и вот что я нашел:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

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