Эффективность векторного индексного доступа и итераторского доступа

Question

У меня есть вопрос, чтобы исправить мое понимание эффективности доступа к элементам вектора, используя индексный доступ (с оператором []) или итератор.

Насколько я понимаю, «итератор» более эффективен, чем «индексный доступ». (также я думаю, что vector::end() более эффективен, чем vector::size()).

Теперь я написал пример кода для его измерения (под Windows 7 с использованием Cygwin, с g ++ 4.5.3)

Версия цикла доступа индекса (ранее помеченная как произвольный доступ):

int main()
{
  std::vector< size_t > vec ( 10000000 );
  size_t value = 0;

  for( size_t x=0; x<10; ++x )
  {
    for ( size_t idx = 0; idx < vec.size(); ++idx )
    {
      value += vec[idx];
    }
    return value;
  }
}

Код цикла итератора таков:

    for (std::vector< size_t >::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        value = *iter;
    }

Я удивлен, увидев, что версия с индексным доступом гораздо быстрее. Я использовал команду time для «измерения». Числа были:

результаты с использованием g++ source.cpp (без оптимизации) индекс доступа

реальные 800 мс

доступ к итератору

реальное 2200мс

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

результаты с использованием g ++ -O2 индексный доступ, реальное время: ~ 200 мс

доступ к итератору, реальное время: ~ 200 мс

Я повторил тесты на разных платформах (amd64 w / g ++ и power7 w xlC) и увидел, что все время, когда я использовал оптимизированный код, примеры программ имели одинаковое время выполнения.

edit изменен код для добавления значений (value += *iter) вместо использования присваивания. Добавлены подробности о параметрах компилятора. Добавлены новые номера для использования -O2. * edit2 изменен заголовок, исправляющий «эффективность итератора» на «эффективность доступа».

Answer 1

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

Что касается вашего «понимания», в типе итератора и егоспектакль.Вы можете писать прямые итераторы, которые очень быстрые или очень медленные, так же, как вы можете писать произвольные итераторы, которые очень быстрые или очень медленные.Глобально, типы структур данных, которые будут поддерживать итераторы произвольного доступа, вероятно, будут иметь лучшую локальность, чем те, которые не поддерживают, что может работать в пользу итераторов произвольного доступа;но этого на самом деле недостаточно, чтобы иметь возможность делать какие-либо разумные обобщения.

Answer 2

Когда я компилирую обе программы с -O2 (Linux, GCC 4.6.1), они работают одинаково быстро.

Тогда: ваша первая программа не с использованием итераторов, она использует indexes . Это разные понятия.

Ваша вторая программа фактически использует итераторы произвольного доступа, потому что это std::vector<T>::iterator s. Ограничения на std::vector разработаны таким образом, что итератор может быть реализован в виде простого указателя на динамический массив, который vector инкапсулирует.

begin должно быть так же быстро, как size. Единственное различие между ними в типичной реализации std::vector заключается в том, что end может потребоваться вычислить begin() + size(), хотя size также может быть реализовано как (примерно) end() - begin(). Хотя компилятор может оптимизировать оба в цикле.

Answer 3

При оптимизации два кода должны быть (почти) идентичны.Попробуйте -O2.

Без оптимизации и отладочной информации ваши измерения будут вводить в заблуждение.

Answer 4

Я считаю, что итераторы быстрее. Попробуйте изменить рефакторинг вашего цикла итератора на что-то вроде следующего, и вы также можете увидеть это:

#include <ctime>
#include <vector>
#include <iostream>
using namespace std;

int main()
{   
  std::vector< size_t > vec ( 1000000 );
  size_t value = 0;
  srand ( time(NULL) );
  clock_t start,stop;
  int ncycle = 10000;

  start = std::clock();
  for( size_t x=0; x<ncycle; ++x ) { 
    for ( size_t idx = 0; idx < vec.size(); ++idx )
      vec[idx] += rand();
  }   
  stop = std::clock();
  cout << start << " " << stop << endl;
  cout << "INDEX: " << (double((stop - start)) / CLOCKS_PER_SEC) / ncycle << " seconds per cycle" << endl;

  start = std::clock();
  for( size_t x=0; x<ncycle; ++x ) { 
    for (std::vector< size_t >::iterator iter = vec.begin(), end = vec.end(); iter != end; ++iter)
        *iter += rand();
  }   
  stop = std::clock();
  cout << "ITERATOR: " << (double((stop - start)) / CLOCKS_PER_SEC) / ncycle << " seconds per cycle" << endl;
}   

Результат на моем компьютере следующий, показывающий, что итераторы имеют небольшое преимущество:

INDEX: 0.012069 seconds per cycle
ITERATOR: 0.011482 seconds per cycle

Вы должны заметить, что я использовал дополнение rand (); это мешает компилятору оптимизировать то, что он может вычислить во время компиляции. Похоже, что компиляторам намного проще справиться с собственными массивами, чем с векторами, и это может ввести в заблуждение преимущество массивов над векторами.

Я скомпилировал вышеупомянутое с "icpc -fast". Славик был прав в том, что при использовании итераторов (ala pointers) необходимо выполнять вычисления индексов и инкрементов.

Answer 5

В первом примере вы разыменовываете каждый отдельный элемент, используя value = vec[idx];, что приводит к вычислению смещения element_size * index при каждом доступе к элементу.

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

Если вы включите оптимизацию (попробуйте -O2 или -O3), однако, компилятор, скорее всего, оптимизирует ваш цикл в первом примере до уровня, аналогичного второму, что сделает производительность практически идентичной.