std :: vector - индексы всегда быстрее?

Question

При использовании std :: vector всегда ли быстрее проходить через все элементы вектора через индексы, чем при использовании итераторов?

Я написал простой тупой тест, VS 2010, оптимизация отключена

#include <vector>
#include <iostream>
#include <ctime>

const int SIZE = 100000;    

int main()
{    
    std::vector<int> vInt;
    int i, temp;
    srand(time(0));
    for(i = 0; i<SIZE; i++)
        vInt.push_back(rand());

    time_t startTime, endTime;
    std::vector<int>::iterator it = vInt.begin(), itEnd = vInt.end();
startTime = clock();
for( ; it != itEnd; it++)
        temp = *it;
    endTime = clock();
    std::cout<<"Result for iterator: "<<endTime - startTime;

    i = 0;
    int size = vInt.size();
    startTime = clock();
    for(; i<size; i++)
        temp = vInt[i];
    endTime = clock();
    std::cout<<"\nResult for index: "<<endTime - startTime;    

    return 0;
}

Режим отладки:

Без оптимизации результаты:

Result for iterator: 143
Result for index: 5

для const int SIZE = 1000;

Result for iterator: 0
Result for index: 0

для const int SIZE = 10000;

Result for iterator: 15
Result for index: 2

для const int SIZE = 1000000;

Result for iterator: 1377
Result for index: 53

С / O2 флагом

для const int SIZE = 10000;

Result for iterator: 0 - 2
Result for index: 0

для const int SIZE = 100000;

Result for iterator: 12 - 15
Result for index: 0

для const int SIZE = 1000000;

Result for iterator: 133 - 142
Result for index: 0 - 3

Так что лучше всегда использовать индексы с вектором?

ОБНОВЛЕНИЕ :

РЕЖИМ ВЫПУСКА

С флагом / O2 все результаты равны 0.

Когда оптимизация отключена / Od индексы быстрее

для const int SIZE = 100000000;

Result for iterator: 2182
Result for index: 472

для const int SIZE = 1000000;

Result for iterator: 22
Result for index: 5

для const int SIZE = 100000;

Result for iterator: 2 - 3
Result for index: 0 - 1

Answer 1

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

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

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

int *it=&v[0], *end=it+v.size();
for (; it!=end; ++it) temp=*it;

Это должно дать вам базовую строку для сравнения вашего итератора. Любое различие в производительности между итератором и этой базовой строкой связано с дополнительными проверками, которые ваш компилятор / поставщик библиотеки использует для отладки. Прочитайте документы о том, как их отключить. Также обратите внимание, что ваш шаг (it++) требует создания одной копии it, в случае указателя, который в принципе не имеет никакого эффекта, но если итератор вообще поддерживает какое-либо состояние, стоимость it++ будет доминировать во всем цикле , Всегда предпочитайте ++it.

Следующее, что вы хотите измерить, и что компилятор считает нужным. Вы хотите измерить итерацию, но компилятор не знает ее, он видит только ваш код, и оптимизатор приложит все усилия, чтобы создать эквивалентный код, который будет максимально быстрым. Взяв только один из циклов, компилятор может понять, что вся итерация не имеет побочных эффектов, кроме установки временного значения v[v.size()-1], и в худшем случае (для вашего измерения) он может фактически выполнить это преобразование, полностью удалив циклы, что приводит нас к следующему пункту:

Дьявол кроется в деталях. Я предполагаю, что вы намерены измерять относительную стоимость итерации в общем случае, но ваша программа измеряет стоимость итерации по вектору постоянного размера. Почему это важно? Компиляторы выполняют развертывание циклов, чтобы избежать затрат на тестирование, когда они могут. Если компилятор знает, что ваш цикл всегда будет содержать несколько X итераций, он может проверить выполнение цикла только в одном из X этапов. Оптимизация не гарантируется, и в общем случае приложения компилятор не будет знать количество итераций, поэтому вы должны убедиться, что тест не дает компилятору больше шансов на оптимизацию, чем в реальной программе. В этих двух случаях вы хотите убедиться, что компилятор не имеет дополнительной информации, которой он не имел бы в реальном случае, то есть вы хотите скрыть знание теста и заставить его сосредоточиться на проблеме. Я бы посоветовал вам переместить циклы в функции в другой единице перевода, передать вектор по ссылке и убедиться, что он не может избежать зацикливания (взять в качестве аргумента целое число и применить двоичный оператор с временным и каждым элементом). в векторе вернуть результат всех операций вызывающей стороне, и, обрабатывая эту функцию, мы надеемся, что компилятор не сможет сделать что-то слишком умное)

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

Answer 2

Сравнение несправедливо из-за эффекта кэша.

Во-первых, скомпилируйте в режиме «Release», если вы используете VS. Или -O2 в gcc.

После доступа к элементам массива с помощью итератора большинство из них будет кэшировано. Поэтому, когда вы сразу получаете к ним доступ по индексу, кеш уже «прогрелся». Попробуйте сделать это в два отдельных запуска: один только с использованием итератора, а другой только с использованием индекса. Кроме того, попробуйте более большой набор данных, скажем, 1 ГБ. Поскольку clock не очень точный таймер, вы можете также использовать rdtsc.

К вашему сведению, это поток, в котором говорится о stl: векторный итератор и индекс.

Answer 3

Нет, это зависит от компилятора и флагов оптимизации, установленных для компиляции.

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

Кроме того, вместо постинкремента следует использовать оператор предварительного увеличения, это должно быть быстрее:

for( ; it != itEnd; ++it)

Answer 4

я думаю, что ваши времена итераторов в режиме отладки показывают накладные расходы на расширенную проверку итераторов.

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