Используя массивы или std::vectors в C++, какова разница в производительности?
В нашем курсе C++ они предлагают больше не использовать массивы C++ в новых проектах. Насколько я знаю, сам Stroustroup предлагает не использовать массивы. Но есть ли существенные различия в производительности?
22 ответа
Использование массивов C++ с new (то есть, используя динамические массивы) следует избегать. Существует проблема, что вы должны следить за размером, и вам нужно удалить их вручную, и делать все виды домашнего хозяйства.
Использование массивов в стеке также не рекомендуется, поскольку у вас нет проверки диапазона, и передача массива потеряет любую информацию о его размере (преобразование массива в указатель). Вы должны использовать boost::array в этом случае, который оборачивает массив C++ в небольшой класс и обеспечивает size функция и итераторы, чтобы перебрать его.
Теперь std::vector против собственных массивов C++ (взятых из Интернета):
// 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 и размещать не классовые объекты (как обычный int) или классы без определяемого пользователем конструктора, и вы не хотите инициализировать свои элементы изначально, используя newмассивы могут иметь преимущества в производительности, потому что std::vector инициализирует все элементы значениями по умолчанию (например, 0 для int) при создании (кредиты @bernie за то, что они меня запомнили).
Преамбула для микрооптимизаторов
Помните:
"Программисты тратят огромное количество времени на размышления или беспокойство по поводу скорости некритических частей своих программ, и эти попытки повышения эффективности на самом деле оказывают сильное негативное влияние при рассмотрении вопросов отладки и обслуживания. Мы должны забыть о небольшой эффективности, скажем о 97% времени: преждевременная оптимизация - корень всего зла. Но мы не должны упускать наши возможности в эти критические 3% ".
(Спасибо за metamorphosis за полную цитату)
Не используйте массив C вместо вектора (или чего-либо еще) только потому, что вы считаете, что он быстрее, так как предполагается, что он более низкого уровня. Ты был бы неправ.
Используйте вектор по умолчанию (или безопасный контейнер, адаптированный к вашим потребностям), и затем, если ваш профилировщик скажет, что это проблема, посмотрите, можете ли вы оптимизировать его, либо используя лучший алгоритм, либо изменив контейнер.
Тем не менее, мы можем вернуться к первоначальному вопросу.
Статический / Динамический Массив?
Классы массива C++ ведут себя лучше, чем низкоуровневый массив C, потому что они много знают о себе и могут отвечать на вопросы, а массивы C - нет. Они умеют убирать за собой. И что еще более важно, они обычно пишутся с использованием шаблонов и / или встраивания, что означает, что то, что кажется для большого количества кода в отладке, разрешается практически без кода, созданного в сборке релиза, что означает отсутствие различий с их встроенной менее безопасной конкуренцией.
В целом, это падает на две категории:
Динамические массивы
Использование указателя на массив malloc-ed / new-ed будет в лучшем случае таким же быстрым, как версия std::vector, и намного менее безопасным (см. Публикацию litb).
Так что используйте std::vector.
Статические массивы
Использование статического массива будет в лучшем случае:
- так же быстро, как версия std::array
- и намного менее безопасно.
Так что используйте std::array.
Неинициализированная память
Иногда, используя vector вместо необработанного буфера несет видимую стоимость, потому что vector инициализирует буфер при построении, в то время как код, который он заменяет, этого не сделал, как заметил bernie в своем ответе.
Если это так, то вы можете справиться с этим с помощью unique_ptr вместо vector или, если случай не является исключительным в вашей кодовой строке, на самом деле написать класс buffer_owner который будет владеть этой памятью и предоставит вам простой и безопасный доступ к ней, включая бонусы, такие как изменение размера (использование realloc?) или что вам нужно.
Векторы - это массивы под капотом. Производительность такая же.
Единственное место, где вы можете столкнуться с проблемой производительности, это не правильно выбрать вектор для начала.
Когда вектор заполняется, он изменяет свой размер, что может означать новое выделение массива, за которым следуют n конструкторов копирования, за которыми следуют около n вызовов деструктора, а затем удаление массива.
Если ваша конструкция / деструктор дорогая, вам лучше сделать вектор правильного размера для начала.
Есть простой способ продемонстрировать это. Создайте простой класс, который показывает, когда он создается / уничтожается / копируется / назначается. Создайте вектор этих вещей и начните помещать их в конец вектора. Когда вектор заполнится, произойдет каскад активности при изменении размера вектора. Затем попробуйте снова с вектором, размер которого соответствует ожидаемому количеству элементов. Вы увидите разницу.
Чтобы ответить на что-то, Мехрдад сказал:
Однако могут быть случаи, когда вам все еще нужны массивы. При взаимодействии с кодом низкого уровня (т. Е. Сборкой) или старыми библиотеками, которые требуют массивов, вы не сможете использовать векторы.
Совсем не правда. Векторы хорошо разлагаются на массивы / указатели, если вы используете:
vector<double> vector;
vector.push_back(42);
double *array = &(*vector.begin());
// pass the array to whatever low-level code you have
Это работает для всех основных реализаций STL. В следующем стандарте он будет работать (хотя сегодня он работает нормально).
У вас еще меньше причин использовать простые массивы в C++11.
В природе существует 3 вида массивов, от самого быстрого до самого медленного, в зависимости от имеющихся у них функций (конечно, качество реализации может сделать вещи действительно быстрыми даже для случая 3 в списке):
- Статический размер известен во время компиляции. ---
std::array<T, N> - Динамический с размером, известным во время выполнения и никогда не изменяемым. Типичная оптимизация здесь заключается в том, что если массив может быть размещен в стеке напрямую. - Недоступно. Может быть
dynarrayв C++ TS после C++14. В C есть VLA - Динамический и изменяемого размера во время выполнения. ---
std::vector<T>
Для 1. простых статических массивов с фиксированным числом элементов используйте std::array<T, N> в C++11.
2. Для массивов фиксированного размера, указанных во время выполнения, но это не изменит их размера, есть обсуждение в C++ 14, но оно было перенесено в техническую спецификацию и наконец сделано из C++14.
За 3. std::vector<T> будет обычно просить память в куче. Это может иметь последствия для производительности, хотя вы могли бы использовать std::vector<T, MyAlloc<T>> улучшить ситуацию с помощью специального распределителя. Преимущество по сравнению с T mytype[] = new MyType[n]; в том, что вы можете изменить его размер и он не будет затухать до указателя, как это делают обычные массивы.
Используйте упомянутые стандартные типы библиотек, чтобы избежать попадания массивов в указатели. Вы сэкономите время отладки, и производительность будет точно такой же, как и для простых массивов, если вы используете тот же набор функций.
Определенно, это влияет на производительность std::vector против необработанного массива, когда вы хотите неинициализированный буфер (например, использовать в качестве места назначения для memcpy()). std::vector инициализирует все его элементы, используя конструктор по умолчанию. Необработанный массив не будет.
Спецификация C++ для std:vector конструктор, принимающий count Аргумент (это третья форма) гласит:
`Создает новый контейнер из множества источников данных, по выбору, используя предоставленный пользователем распределитель alloc.
3) Создает контейнер с количеством вставленных по умолчанию экземпляров T. Копии не создаются.
сложность
2-3) Линейный по количеству
Необработанный массив не несет затрат на инициализацию.
Смотрите также Как я могу избежать std::vector<> для инициализации всех его элементов?
Иди с STL. Там нет потери производительности. Алгоритмы очень эффективны, и они хорошо справляются с деталями, о которых большинство из нас не думает.
Вывод состоит в том, что массивы целых чисел быстрее, чем векторы целых чисел (в моем примере 5 раз). Однако массивы и векторы имеют одинаковую скорость для более сложных / не выровненных данных.
STL - сильно оптимизированная библиотека. На самом деле даже предлагается использовать STL в играх, где может потребоваться высокая производительность. Массивы слишком подвержены ошибкам, чтобы их можно было использовать в повседневных задачах. Современные компиляторы также очень умны и могут действительно генерировать отличный код с помощью STL. Если вы знаете, что делаете, STL обычно может обеспечить необходимую производительность. Например, путем инициализации векторов до требуемого размера (если вы знаете с самого начала), вы в основном можете добиться производительности массива. Однако могут быть случаи, когда вам все еще нужны массивы. При взаимодействии с кодом низкого уровня (т. Е. Сборкой) или старыми библиотеками, которые требуют массивов, вы не сможете использовать векторы.
Если вы компилируете программное обеспечение в режиме отладки, многие компиляторы не будут встроены функции доступа вектора. Это сделает реализацию вектора stl намного медленнее в условиях, когда производительность является проблемой. Это также облегчит отладку кода, поскольку в отладчике видно, сколько памяти было выделено.
В оптимизированном режиме я бы ожидал, что вектор stl приблизится к эффективности массива. Это потому, что многие из векторных методов теперь встроены.
Разница в производительности между ними очень сильно зависит от реализации - если вы сравните плохо реализованный std::vector с оптимальной реализацией массива, массив победит, но перевернет его, и вектор победит...
Пока вы сравниваете яблоки с яблоками (либо массив, и вектор имеют фиксированное количество элементов, либо оба динамически изменяются в размерах), я думаю, что разница в производительности незначительна, если вы следуете практике кодирования STL. Не забывайте, что использование стандартных контейнеров C++ также позволяет использовать предварительно свернутые алгоритмы, которые являются частью стандартной библиотеки C++, и большинство из них, вероятно, будут более эффективными, чем обычная реализация того же алгоритма, который вы создали сами,
Тем не менее, ИМХО, вектор выигрывает в сценарии отладки с отладочным STL, поскольку большинство реализаций STL с надлежащим режимом отладки могут по крайней мере выделить / скрыть типичные ошибки, допущенные людьми при работе со стандартными контейнерами.
Да, и не забывайте, что массив и вектор совместно используют одну и ту же структуру памяти, поэтому вы можете использовать векторы для передачи данных в устаревший код C или C++, который ожидает базовые массивы. Имейте в виду, что большинство ставок в этом сценарии отменены, и вы снова имеете дело с сырой памятью.
Следующий простой тест:
C++ Array vs Vector Объяснение теста производительности
противоречит выводам из "Сравнения кода ассемблера, сгенерированного для базовых операций индексации, разыменования и приращения для векторов и массивов / указателей".
Должна быть разница между массивами и векторами. Тест говорит так... просто попробуйте, код есть...
Если вы используете векторы для представления многомерного поведения, производительность снижается.
Векторы 2d+ вызывают снижение производительности?
Суть в том, что есть небольшой объем служебной информации, когда каждый субвектор имеет информацию о размере, и не обязательно будет сериализация данных (как это происходит с многомерными массивами c). Это отсутствие сериализации может предложить больше возможностей, чем микрооптимизация. Если вы работаете с многомерными массивами, лучше всего просто расширить std::vector и запустить собственную функцию get/set/resize bits.
Я бы сказал, что главная проблема не в производительности, а в безопасности. Вы можете сделать много ошибок с массивами (например, рассмотрите возможность изменения размера), когда вектор избавит вас от большой боли.
Иногда массивы действительно лучше, чем векторы. Если вы всегда манипулируете набором объектов фиксированной длины, лучше использовать массивы. Рассмотрим следующие фрагменты кода:
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() быстрее, потому что мы избегаем издержек "new" каждый раз во внутреннем цикле.
(Этот код был размещен мной на comp.lang.C++).
Может быть некоторый крайний случай, когда у вас есть векторный доступ внутри встроенной функции внутри встроенной функции, когда вы вышли за пределы того, что компилятор встроит, и это вызовет вызов функции. Это было бы настолько редко, что о них не стоит беспокоиться - в общем, я бы согласился с Литбом.
Я удивлен, что никто еще не упомянул об этом - не беспокойтесь о производительности, пока она не окажется проблемой, а затем оцените ее.
Векторы используют чуть больше памяти, чем массивы, поскольку они содержат размер массива. Они также увеличивают размер жесткого диска программ и, вероятно, объем памяти программ. Эти увеличения незначительны, но могут иметь значение, если вы работаете со встроенной системой. Хотя большинство мест, где эти различия имеют значение, это места, где вы бы использовали C, а не C++.
Если вам не нужно динамически регулировать размер, у вас есть накладные расходы памяти на сохранение емкости (один указатель /size_t). Вот и все.
Для массивов фиксированной длины производительность такая же (по сравнению с вектором <>) в сборке выпуска, но в отладочной сборке низкоуровневые массивы выигрывают в 20 раз, по моему опыту (MS Visual Studio 2015, C++ 11).
Таким образом, аргумент «сэкономьте время на отладку» в пользу STL может быть действителен, если вы (или ваши коллеги) склонны вносить ошибки в использование вашего массива, но, возможно, нет, если ваше время отладки в основном ожидает, пока ваш код дойдет до точки, в которой вы в настоящее время работают, чтобы вы могли пройти через него.
Во вторую группу иногда попадают опытные разработчики, работающие над численно насыщенным кодом (особенно если они используют вектор :)).
Предполагая массив фиксированной длины (например, int* v = new int[1000]; против std::vector<int> v(1000);с размером v при фиксированном значении 1000) единственное соображение производительности, которое действительно имеет значение (или, по крайней мере, имело значение для меня, когда я находился в подобной дилемме), - это скорость доступа к элементу. Я посмотрел векторный код STL, и вот что я нашел:
const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }
Эта функция наверняка будет встроена компилятором. Итак, пока единственное, что вы планируете делать с v это доступ к его элементам с operator[]Похоже, что не должно быть никакой разницы в производительности.
Я помню, как давным-давно задался этим вопросом, думая, что массивы в стиле C наверняка должны быть быстрее, чем std::vector.
Однако я прочитал много сообщений , в которых говорилось, что разницы в производительности нет или эта разница была незначительной (где это действительно не имело бы значения), и поэтому моя предпосылка была неверной .
Еще одним уроком, который я усвоил, было тестирование/тестирование/профилирование, поэтому я проводил свои собственные тесты, как это сделали некоторые из присутствующих здесь людей, и обнаружил, что действительно массивы в стиле C были быстрее, чем std::vector. .
Однако эти тесты провалились, потому что я не знал об оптимизации компилятора . и clang++, и g++ имеют флаги оптимизации компилятора (-O0 предназначен для отладки). С флагом -O2 std::vector действительно стал таким же быстрым, как массив в стиле C. Я действительно был не прав . Некоторые люди сказали, что компиляция без флагов - это нормально, я бы категорически не согласился с этим утверждением, использование -O2 является обычным явлением наряду со многими другими флагами, по моему опыту, возможно, использование -O3 необычно.
Какова разница в производительности при использовании массивов или std::vectors в C++? Если вы используете флаг оптимизации -O2, разрыв в производительности практически отсутствует (если вы сравниваете подобную операцию с подобной операцией ), хотя я уверен, что можно разработать сценарий, в котором он был бы, если вы очень хорошо знаете компилятор или выполняете что-то необычное...?
Нет никаких споров о том, какой из них лучше или хорош для использования. У обоих есть свои варианты использования, у них обоих есть свои плюсы и минусы. Поведение обоих контейнеров отличается в разных местах. Одна из основных трудностей с массивами заключается в том, что они фиксированы по размеру, если после их определения или инициализации вы не можете изменять значения, а с другой стороны векторы являются гибкими, вы можете изменять значение векторов, когда захотите, они не фиксированы по размеру, как массивы, потому что массив имеет статическую память распределение и вектор имеют динамическую память или распределение кучи памяти (мы можем вставлять и извлекать элементы в/из вектора), и создатель С++ Бьярн Страуструп сказал, что векторы гибки для использования больше, чем массивы.
Следует избегать использования массивов C++ с new (то есть использования динамических массивов). Есть проблема, вы должны следить за размером, и вам нужно удалять их вручную и делать все виды уборки.
Мы также можем легко вставлять, нажимать и извлекать значения в векторах, что нелегко сделать в массивах.
Если мы говорим о производительности, то, если вы работаете с небольшими значениями, вам следует использовать массивы, а если вы работаете с крупномасштабным кодом, вам следует использовать вектор (векторы хороши для обработки больших значений, чем массивы).