Вопрос по stl, performance, c++ – Динамически распределяемые массивы или std :: vector

6

Я пытаюсь оптимизировать свой код C ++. Я искал в интернете использование динамически распределенных массивов C ++ по сравнению с использованием std :: vector и обычно видел рекомендацию в пользу std :: vector, и что разница в производительности между ними незначительна. Например здесь -Используя массивы или std :: vectors в C ++, какова разница в производительности?.

Тем не менее, я написал некоторый код для проверки производительности итерации по массиву / вектору и присвоения значений элементам, и я в целом обнаружил, что использование динамически размещаемых массивов было почти в 3 раза быстрее, чем использование векторов (я заранее определил размер для векторов ). Я использовал g ++ - 4.3.2.

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

Спасибо

Используемый код -

#include <time.h>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i;
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}
Итак, где же код? wilhelmtell
@ Нил, я думаю, что твой комментарий должен быть принятым ответом. Может быть, вы должны сделать это ответом, чтобы мы могли проголосовать и Сид мог принять это. 8v) Fred Larson
Да, давайте посмотрим ваш эталонный код. Часто проблемы производительности с контейнерами STL связаны с использованием. Fred Larson
Оптимизации не были включены во время компиляции. std :: vector теперь быстрее. Спасибо за помощь. Opt
и убедитесь, что тест компилируется с отладкой и оптимизацией на anon

Ваш Ответ

10   ответов
3

что причина, по которой вы обнаружили, что итерация и добавление в std :: vector в 3 раза медленнее, чем в обычном массиве, заключается в комбинации стоимости итерации вектора и выполнения задания.

Edit:

Это было мое первоначальное предположение перед тестом; Однако запуск теста (скомпилировано с-O3) показывает обратное - std :: vector на самом деле в 3 раза быстрее, что меня удивило.

Я не вижу, как std :: vector может быть быстрее (конечно, не в 3 раза быстрее), чем копия ванильного массива - я думаю, что некоторая оптимизация применяется к скомпилированному коду std :: vector, что не происходит для версия массива.

Исходные результаты теста:

$ ./array
array:  0.059375
vector: 0.021209

std::vector is 3x faster. Same benchmark again, except add an additional outer loop to run the test iterater loop 1000 times:

$ ./array array: 21.7129 vector: 21.6413

std::vector is now ~ the same speed as array.

Edit 2

Нашел это! Таким образом, проблема с вашим тестовым примером состоит в том, что в векторном случае память, содержащая данные, кажется, уже находится в кэше ЦП - или по тому, как они инициализируются, или из-за вызоваvec.end(), Если я "теплый" вверх кэш процессора перед каждым тестом синхронизации, я получаю одинаковые числа для массива и вектора:

#include <time.h>
#include <iostream>
#include <vector>

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  // get vec into CPU cache.
  for (int i = 0; vecIt != vecEnd; i++) { *(vecIt++) = i; }
  vecIt = vec.begin();
  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i;
  }
  end = clock();
  std::cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;

  int* arr = new int[9999999];

  // get arr into CPU cache.
  for (int i = 0; i < 9999999; i++) { arr[i] = i; }
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  std::cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<std::endl;
}

Это дает мне следующий результат:

$ ./array
vector: 0.020875
array: 0.020695
Error: User Rate Limit Exceeded Opt
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
5

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

21

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
1

  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = i; // <-- quick offset calculation
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i; // <-- not fair play :) - offset = arr + i*size(int)
  }
0

проблема в том, что вы скомпилировали свой код с отключенными оптимизациями. На моей машине OS X 10.5.7 с g ++ 4.0.1 я на самом деле вижу, что вектор быстрее, чем примитивные массивы, в 2,5 раза.

С gcc попробуй пройти-O2 компилятору и посмотрите, есть ли улучшения.

1

это не имеет значения. Как сказал Джалф, код будет примерно таким же, но даже если это не так, посмотрите на цифры. Код, который вы разместили, создает огромный массив из 10 МИЛЛИОНОВ элементов, но итерация по всему массиву занимает всего несколько сотых долей секунды.

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

Чтобы доказать мою точку зрения, вот код с одним изменением: назначение i для элемента массива заменяется назначением sqrt (i). На моей машине, использующей -O2, время выполнения утроится с 0,02 до 0,06 секунды.

#include <time.h>
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int main() {
  clock_t start,end;
  std::vector<int> vec(9999999);
  std::vector<int>::iterator vecIt = vec.begin();
  std::vector<int>::iterator vecEnd = vec.end();

  start = clock();
  for (int i = 0; vecIt != vecEnd; i++) {
    *(vecIt++) = sqrt(i);
  }
  end = clock();
  cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;

  int* arr = new int[9999999];
  start = clock();
  for (int i = 0; i < 9999999; i++) {
    arr[i] = i;
  }
  end = clock();
  cout<<"array: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
}
5

std::vector в том, что да, наивно, это гораздо больше кода, чем необработанный массив. Но все это может быть тривиально встроено компилятором, что означает, что если оптимизация включена, она становится по существуthe same код, как если бы вы использовали необработанный массив. Разница в скорости не является ничтожной, но не существует. Все накладные расходы удаляются во время компиляции.

Но это требует, чтобы оптимизация компилятора была включена.

0

по которой ваш код может не выполнять то же самое, состоит в том, что в вашей версии std :: vector вы инкриминируете два значения, целое числоi и std :: vector :: iteratorvecIt, Чтобы действительно быть эквивалентным, вы можете рефакторинг

start = clock();
for (int i = 0; i < vec.size(); i++) {
  vec[i] = i;
}
end = clock();
cout<<"vector: "<<(double)(end-start)/CLOCKS_PER_SEC<<endl;
0

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

0

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

С вектором вы увеличиваете итератор (vecIT) и отдельную переменную (i) для генерации значений присваивания.

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

Похожие вопросы