Вопрос по performance, c++, c++11 – Является ли ранжированный цикл for выгодным для производительности?

32

Читая различные вопросы здесь, в Stack & # xA0; Переполнение об итераторах C ++ и производительности **, я начал задаваться вопросом,for(auto& elem : container) становится "расширенным" компилятором в лучшую возможную версию? (Вроде какauto, который компилятор сразу выводит в правильный тип и поэтому никогда не медленнее, а иногда и быстрее).

** Например, имеет ли значение, если вы пишете

for(iterator it = container.begin(), eit = container.end(); it != eit; ++it)

или же

for(iterator it = container.begin(); it != container.end(); ++it)

для недействительных контейнеров?

Как использование auto вместо typedefs помогает повысить производительность? Jonathan Wakely
@JonathanWakely Извините, упоминание typedefs было ошибкой с моей стороны. Я не могу найти подходящую ссылку, но то, что я имею в виду, - это то, что Стивен Т. Лававей отмечает в 49: 30+ в channel9.msdn.com/Events/GoingNative/GoingNative-2012/STL11-Magic-Secrets TeaOverflow

Ваш Ответ

5   ответов
30

[stmt.ranged]/1

For a range-based for statement of the form

for ( for-range-declaration : expression ) statement

let range-init be equivalent to the expression surrounded by parentheses

( expression )

and for a range-based for statement of the form

for ( for-range-declaration : braced-init-list ) statement

let range-init be equivalent to the braced-init-list. In each case, a range-based for statement is equivalent to

{
  auto && __range = range-init;
  for ( auto __begin = begin-expr,
             __end = end-expr;
        __begin != __end;
        ++__begin )
  {
    for-range-declaration = *__begin;
    statement
  }
}

Так что да, Стандарт гарантирует, что будет достигнута наилучшая форма.

И для ряда контейнеров, таких какvector, это неопределенное поведение, чтобы изменить (вставить / стереть) их во время этой итерации.

@Evgeni: изменение контейнера во время его циклирования проблематично в целом (также во многих других языках). Обычно есть способы сделать это правильно, но они часто более сложны, чем тривиальный цикл, основанный на диапазоне. То же самое и здесь: вы должны выполнить итерацию вручную и обновить итератор, например, результатомerase
@thc: Я не говорю о наилучшей производительности, но о наилучшей форме. В частности, обратите внимание, что (1)range-init оценивается только один раз, (2)begin-expr а такжеend-expr оцениваются только один раз и (3) используется предварительное увеличение. С точки зрения алгоритма, это форма наименьшей сложности. Оптимизация производительности до наилучшей возможной, вероятно, но не гарантируется. Оптимизаторы непостоянны.
Как вы пришли к выводу, что это гарантированно лучшая производительность? Мне не ясно, как этот вывод сделан.
4

for цикл с итераторами. В конце концов, на основе диапазонаfor работает с итераторами внутри. Компилятор просто создает эквивалентный код для обоих.

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

в:

int foo1(const std::vector<int>& v) {
    int res = 0;
    for (auto x : v)
        res += x;
    return res;
}

int foo2(const std::vector<int>& v) {
    int res = 0;
    for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); ++it)
      res += *it;
    return res;
}

И код ассемблера (с -O3 и gcc 4.6) одинаков для обоих подходов (код дляfoo2 опущен, так как он точно такой же):

080486d4 <foo1(std::vector<int, std::allocator<int> > const&)>:
80486d4:       8b 44 24 04             mov    0x4(%esp),%eax
80486d8:       8b 10                   mov    (%eax),%edx
80486da:       8b 48 04                mov    0x4(%eax),%ecx
80486dd:       b8 00 00 00 00          mov    $0x0,%eax
80486e2:       39 ca                   cmp    %ecx,%edx
80486e4:       74 09                   je     80486ef <foo1(std::vector<int, std::allocator<int> > const&)+0x1b>
80486e6:       03 02                   add    (%edx),%eax
80486e8:       83 c2 04                add    $0x4,%edx
80486eb:       39 d1                   cmp    %edx,%ecx
80486ed:       75 f7                   jne    80486e6 <foo1(std::vector<int, std::allocator<int> > const&)+0x12>
80486ef:       f3 c3                   repz ret 

Итак, да, оба подхода одинаковы.

UPDATE: То же самое относится и к другим контейнерам (или типам элементов), таким какvector<string> а такжеmap<string, string>, В этих случаях особенно важно использовать ссылку в циклическом цикле. В противном случае создается временный объект и появляется много дополнительного кода (в предыдущих примерах он не был нужен, так какvector содержится толькоint ценности).

Для случаяmap<string, string> используемый фрагмент кода C ++:

int foo1(const std::map<std::string, std::string>& v) {
    int res = 0;
    for (const auto& x : v) {
        res += (x.first.size() + x.second.size());
    }
    return res;
}

int foo2(const std::map<std::string, std::string>& v) {
    int res = 0;
    for (auto it = v.begin(), end = v.end(); it != end; ++it) {
        res += (it->first.size() + it->second.size());
    }
    return res;
}

И ассемблерный код (для обоих случаев):

8048d70:       56                      push   %esi
8048d71:       53                      push   %ebx
8048d72:       31 db                   xor    %ebx,%ebx
8048d74:       83 ec 14                sub    $0x14,%esp
8048d77:       8b 74 24 20             mov    0x20(%esp),%esi
8048d7b:       8b 46 0c                mov    0xc(%esi),%eax
8048d7e:       83 c6 04                add    $0x4,%esi
8048d81:       39 f0                   cmp    %esi,%eax
8048d83:       74 1b                   je     8048da0 
8048d85:       8d 76 00                lea    0x0(%esi),%esi
8048d88:       8b 50 10                mov    0x10(%eax),%edx
8048d8b:       03 5a f4                add    -0xc(%edx),%ebx
8048d8e:       8b 50 14                mov    0x14(%eax),%edx
8048d91:       03 5a f4                add    -0xc(%edx),%ebx
8048d94:       89 04 24                mov    %eax,(%esp)
8048d97:       e8 f4 fb ff ff          call   8048990 <std::_Rb_tree_increment(std::_Rb_tree_node_base const*)@plt>
8048d9c:       39 c6                   cmp    %eax,%esi
8048d9e:       75 e8                   jne    8048d88 
8048da0:       83 c4 14                add    $0x14,%esp
8048da3:       89 d8                   mov    %ebx,%eax
8048da5:       5b                      pop    %ebx
8048da6:       5e                      pop    %esi
8048da7:       c3                      ret    
в ОП также включена опция кешированияv.end() и код сборки все равно будет выглядеть так же. Если вам удобнее с этим ...
Компилятор оптимизированv.end() в этом случае он не всегда может это сделать (для других контейнеров).
обратите внимание, что использование std :: for_each также приводит к тому же скомпилированному коду.
Как говорит @Motti, это не доказательство.
@ Евгений: нет, вы не правы. Это зависит от сложностиendпрозрачность тела цикла (если вы передаете ссылку на контейнер непрозрачным функциям, все ставки отключены) и достаточно ли хорош оптимизатор для его вывода или нет. Несмотря на то, что делают большинство книг, этоunconditionally лучше кешироватьend() призываем к каждому эквиваленту. Это также документирует, чтоend() не будет выпуклым для будущих читателей.
24

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

так что если вы склонны писать:

for(iterator i = cont.begin(); i != cont.end(); i++) { /**/ }

Тогда да, диапазон может бытьslightly быстрее, поскольку также легче писать, что нет причин не использовать его (когда это уместно).

N.B. Я сказал, что это как можно быстрее, но это не так.faster than possible, Вы можете достичь точно такой же производительности, если будете тщательно писать свои ручные циклы.

5

в редких случаях. Поскольку вы не можете назвать итератор, оптимизатор может легче доказать, что ваш цикл не может модифицировать итератор. Это влияет, например, Раскрутка цикла оптимизации.

Похожие вопросы