C ++ итераторы и оптимизация цикла

Question

Я вижу много кода на C ++, который выглядит следующим образом:

for( const_iterator it = list.begin(),
     const_iterator ite = list.end();
     it != ite; ++it)

В отличие от более сжатой версии:

for( const_iterator it = list.begin();
     it != list.end(); ++it)

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

Answer 1

Две версии не одинаковы. Во второй версии он сравнивает итератор с list.end() каждый раз, и то, что оценивает list.end(), может измениться в течение цикла. Теперь, конечно, вы не можете изменить list через const_iterator it; но ничто не мешает коду внутри цикла просто вызывать методы на list напрямую и изменять его, что может (в зависимости от типа структуры данных list) изменить конечный итератор. Поэтому в некоторых обстоятельствах может быть неправильным сохранять конечный итератор заранее, потому что он может перестать быть правильным конечным итератором к тому времени, когда вы доберетесь до него.

Answer 2

Я просто упомяну для записи, что стандарт C ++ предусматривает, что вызов begin() и end() для любого типа контейнера (будь то vector, list, map и т. Д. .) должно занимать только постоянное время . На практике эти вызовы почти наверняка будут встроены в сравнение с одним указателем, если вы компилируете с включенными оптимизациями.

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

Answer 3

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

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

Answer 4

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

С конкретной ссылкой на ваш пример, первая версия делает копию итератора end(), вызывая любой код, выполняемый для конструктора копирования объекта итератора. Контейнеры STL обычно содержат встроенные функции end(), поэтому у компилятора есть много возможностей оптимизировать вторую версию, даже если вы не пытаетесь помочь ей. Какой из них лучше? Измерьте их.

Answer 5

Рассмотрим этот пример:

for (const_iterator it = list.begin(); it != list.end(); ++list)
{
    if (moonFull())
        it = insert_stuff(list);
    else
        it = erase_stuff(list);
}

в этом случае вам НУЖНО вызвать list.end () в цикле, и компилятор не собирается его оптимизировать.

В других случаях, когда компилятор может доказать, что end () всегда возвращает одно и то же значение, оптимизация может иметь место.

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

Answer 6

Вы можете сделать первую версию более краткой и получить лучшее из обоих:

for( const_iterator it = list.begin(), ite = list.end();
     it != ite; ++it)

P.S. Итераторы не являются константами, они являются итераторами константной ссылки Есть большая разница.

Answer 7

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

Обратите внимание, что это предполагает, что оптимизатор включен. Если оптимизатор не включен, как это часто делается в отладочных сборках, то вторая формулировка будет включать в себя N-1 больше вызовов функций. В текущих версиях Visual C ++ отладочные сборки также будут подвергаться дополнительным ударам из-за проверки пролога / эпилога функции и более тяжелых итераторов отладки. Следовательно, в тяжелом коде STL по умолчанию в первом случае можно предотвратить непропорционально медленный код в отладочных сборках.

Вставка и удаление в цикле возможны, как указывали другие, но с таким типом цикла я считаю это маловероятным. Во-первых, контейнеры на основе узлов - list, set, map - не аннулируют end () ни в одной из операций. Во-вторых, приращение итератора часто необходимо перемещать в цикле, чтобы избежать проблем с аннулированием:

   // assuming list -- cannot cache end() for vector
   iterator it(c.begin()), end(c.end());
   while(it != end) {
       if (should_remove(*it))
           it = c.erase(it);
       else
           ++it;
   }

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

Answer 8

Ааа, похоже, люди делают догадки. Откройте свой код в отладчике, и вы увидите, что при вызовах begin (), end () и т. Д. Все оптимизировано. Нет необходимости использовать версию 1. Протестировано с компилятором Visual C ++ fullopt.

Answer 9

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

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

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

** (Где «в» означает на самом деле в нем или быть вызванным из него.)

*** (где «часто» означает значительный процент времени.)

ДОБАВЛЕНО: не просто посмотрите, сколько раз в секунду выполняется код. Это может быть 1000 раз в секунду и все еще использовать менее 1% времени.

Не время, сколько времени это займет. Это может занять миллисекунду и все еще использовать менее 1% времени.

Вы можете умножить два, чтобы получить лучшую идею, но это работает, только если они не слишком искажены.

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

Answer 10

Я всегда предпочитал первый. Хотя с встроенными функциями, оптимизацией компилятора и относительно меньшим размером контейнера (в моем случае это обычно максимум 20-25 элементов), это действительно не имеет большого значения в отношении производительности.

const_iterator it = list.begin();
const_iterator endIt = list.end();

for(; it != endIt ; ++it)
{//do something
}

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

std::for_each(list.begin(), list.end(), Functor());

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