Итераторы С++ и оптимизация циклов

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

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

P.S. Итераторы не const, они итераторы для ссылки const. Там большая разница.

Ответ 6

Рассмотрим следующий пример:

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() не входит в одну и ту же единицу перевода, тогда оптимизация должна произойти во время соединения. Я очень мало знаю о оптимизации времени ссылки, но я поставил бы на то, что большинство линкеров не будут делать такую ​​оптимизацию.

Ответ 7

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

Ответ 8

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

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

Вставка и удаление внутри цикла - это возможность, как указывали другие, но с этим стилем цикла я нахожу это маловероятным. Во-первых, контейнеры node - список, набор, карта - не делают недействительными 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() для причин mutate-in-loop и все еще имеет ++ в заголовке цикла, чтобы быть подозрительным.

Ответ 9

Я всегда предпочитал первый. Хотя с встроенными функциями, оптимизацией компилятора и относительно меньшим размером контейнера (в моем случае это обычно не более 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 не позволяет вам разбивать цикл, если не генерируется исключение).

Ответ 10

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

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

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

** (Где "в" означает на самом деле в нем или вызывается из него.)

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

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

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

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

Сэмплирование стека вызовов сообщит вам, использует ли он достаточно высокий процент времени.

Ответ 11

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

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