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

Question

В нашем курсе C ++ они предлагают больше не использовать массивы C ++ в новых проектах. Насколько я знаю, сам Stroustroup предлагает не использовать массивы. Но есть ли существенные различия в производительности?

Answer 1

Следует избегать использования массивов 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 за то, что они меня запомнили).

Answer 2

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

Помните:

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

(благодаря метаморфозе за полную цитату)

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

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

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

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

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

В целом, он подразделяется на две категории:

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

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

Так что используйте std :: vector.

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

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

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

Так что используйте std :: array .

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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

Answer 5

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

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

1. Статика с размером, известным во время компиляции. --- std::array<T, N>
2. Динамический с размером, известным во время выполнения и никогда не изменяемым. Типичная оптимизация здесь заключается в том, что если массив может быть размещен в стеке напрямую. - Недоступно . Может быть dynarray в C ++ TS после C ++ 14. В C есть VLA
3. Динамический и изменяемый размер во время выполнения. --- 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]; в том, что вы можете изменить его размер и не указывать на указатель, как это делают обычные массивы.

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

Answer 6

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

Answer 7

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

Answer 8

О вкладе Дули .

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

Answer 9

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

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

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

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

Сложность

2-3) Линейный по счету

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

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

Answer 10

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

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