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

Question

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

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

Теперь я написал пример код измерить его (под Windows 7 с помощью Cygwin, с г ++ 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 (без оптимизации) доступа индекса

реального 800ms

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

реальных 2200ms

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

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

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

Я повторил тесты на другой платформе (amd64 ж/г ++ и POWER7 ж XLC) и увидеть, что все время я использовал оптимизированный код примеров программ имеют одинаковое время выполнения.

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

#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 

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

Я скомпилировал вышесказанное с помощью «icpc-fast». slavik был прав, когда ему приходилось делать вычисления по индексам против приращения при использовании итераторов (указатели ala).