Выполнение pIter! = Cont.end() in for loop

Question

В последнее время я получал «Исключительный C++» Херба Саттера, и у меня есть серьезные сомнения в отношении конкретной рекомендации, которую он дает в пункте 6 - «Временные объекты».

Он предлагает найти ненужные временные объекты в следующем коде:

string FindAddr(list<Employee> emps, string name) 
{ 
    for (list<Employee>::iterator i = emps.begin(); i != emps.end(); i++) 
    { 
    if(*i == name) 
    { 
     return i->addr; 
    } 
    } 
    return ""; 
} 

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

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

И он предлагает заменить следующим:

list<Employee>::const_iterator end(emps.end()); 
for (list<Employee>::const_iterator i = emps.begin(); i != end; ++i) 

Для меня это лишнее усложнение. Даже если заменить слова уродливого типа на компактные auto, он по-прежнему получает две строки кода вместо одного. Более того, у него есть эта переменная end во внешнем пространстве.

Я был уверен, что современные компиляторы будут в любом случае оптимизировать этот кусок кода, потому что я на самом деле использую здесь const_iterator, и это легко проверить, так ли содержимое контура обращается к контейнеру. Составители стали умнее в течение последних 13 лет, верно?

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

Update

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

Answer 1

UPD: Книга, о которой вы говорите, была опубликована в 1999 году, если я не ошибаюсь. Это 14 лет назад, и в современном программировании 14 лет - это много времени.Многие рекомендации, которые были хорошими и надежными в 1999 году, могут быть полностью устаревшими. Хотя мой ответ касается одного компилятора и единой платформы, есть и более общая идея.

Уход за дополнительными переменными, повторное использование возвращаемого значения тривиальных методов и подобных трюков старого C++ - это шаг назад к C++ 1990-х годов. Тривиальные методы, такие как end(), должны быть хорошо отстроены, а результат встраивания должен быть оптимизирован как часть кода, из которого он вызван. 99% ситуаций не требуют ручных действий, таких как создание переменной end. Такие вещи следует делать только в том случае, если:

1. Вы ЗНАЕТЕ, что на некоторых компиляторах/платформах, которые вы должны запускать на код, не оптимизированы хорошо.
2. Это стало узким местом в вашей программе («избегайте преждевременной оптимизации»).

Я посмотрел на то, что порождается 64-битный г ++:

gcc version 4.6.3 20120918 (prerelease) (Ubuntu/Linaro 4.6.3-10ubuntu1) 

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

#include <list> 

using namespace std; 

int main() { 
    list<char> l; 
    l.push_back('a'); 

    for(list<char>::iterator i=l.begin(); i != l.end(); i++) 
     ; 

    return 0; 
} 

int main1() { 
    list<char> l; 
    l.push_back('a'); 
    list<char>::iterator e=l.end(); 
    for(list<char>::iterator i=l.begin(); i != e; i++) 
     ; 

    return 0; 
} 

Тогда мы должны скомпилировать это с оптимизациями (я использую 64-разрядную g++, вы можете попробовать ваш компилятор) и разберите main и main1:

Для main:

(gdb) disas main 
Dump of assembler code for function main(): 
    0x0000000000400650 <+0>: push %rbx 
    0x0000000000400651 <+1>: mov $0x18,%edi 
    0x0000000000400656 <+6>: sub $0x20,%rsp 
    0x000000000040065a <+10>: lea 0x10(%rsp),%rbx 
    0x000000000040065f <+15>: mov %rbx,0x10(%rsp) 
    0x0000000000400664 <+20>: mov %rbx,0x18(%rsp) 
    0x0000000000400669 <+25>: callq 0x400630 <_Znwm@plt> 
    0x000000000040066e <+30>: cmp $0xfffffffffffffff0,%rax 
    0x0000000000400672 <+34>: je  0x400678 <main()+40> 
    0x0000000000400674 <+36>: movb $0x61,0x10(%rax) 
    0x0000000000400678 <+40>: mov %rax,%rdi 
    0x000000000040067b <+43>: mov %rbx,%rsi 
    0x000000000040067e <+46>: callq 0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt> 
    0x0000000000400683 <+51>: mov 0x10(%rsp),%rax 
    0x0000000000400688 <+56>: cmp %rbx,%rax 
    0x000000000040068b <+59>: je  0x400698 <main()+72> 
    0x000000000040068d <+61>: nopl (%rax) 
    0x0000000000400690 <+64>: mov (%rax),%rax 
    0x0000000000400693 <+67>: cmp %rbx,%rax 
    0x0000000000400696 <+70>: jne 0x400690 <main()+64> 
    0x0000000000400698 <+72>: mov %rbx,%rdi 
    0x000000000040069b <+75>: callq 0x400840 <std::list<char, std::allocator<char> >::~list()> 
    0x00000000004006a0 <+80>: add $0x20,%rsp 
    0x00000000004006a4 <+84>: xor %eax,%eax 
    0x00000000004006a6 <+86>: pop %rbx 
    0x00000000004006a7 <+87>: retq 

Look в командах, расположенных на 0x0000000000400683-0x000000000040068b. Это тело цикла, и это, кажется, отлично оптимизирован:

0x0000000000400690 <+64>: mov (%rax),%rax 
    0x0000000000400693 <+67>: cmp %rbx,%rax 
    0x0000000000400696 <+70>: jne 0x400690 <main()+64> 

Для main1:

(gdb) disas main1 
Dump of assembler code for function main1(): 
    0x00000000004007b0 <+0>: push %rbp 
    0x00000000004007b1 <+1>: mov $0x18,%edi 
    0x00000000004007b6 <+6>: push %rbx 
    0x00000000004007b7 <+7>: sub $0x18,%rsp 
    0x00000000004007bb <+11>: mov %rsp,%rbx 
    0x00000000004007be <+14>: mov %rsp,(%rsp) 
    0x00000000004007c2 <+18>: mov %rsp,0x8(%rsp) 
    0x00000000004007c7 <+23>: callq 0x400630 <_Znwm@plt> 
    0x00000000004007cc <+28>: cmp $0xfffffffffffffff0,%rax 
    0x00000000004007d0 <+32>: je  0x4007d6 <main1()+38> 
    0x00000000004007d2 <+34>: movb $0x61,0x10(%rax) 
    0x00000000004007d6 <+38>: mov %rax,%rdi 
    0x00000000004007d9 <+41>: mov %rsp,%rsi 
    0x00000000004007dc <+44>: callq 0x400610 <_ZNSt8__detail15_List_node_base7_M_hookEPS0_@plt> 
    0x00000000004007e1 <+49>: mov (%rsp),%rdi 
    0x00000000004007e5 <+53>: cmp %rbx,%rdi 
    0x00000000004007e8 <+56>: je  0x400818 <main1()+104> 
    0x00000000004007ea <+58>: mov %rdi,%rax 
    0x00000000004007ed <+61>: nopl (%rax) 
    0x00000000004007f0 <+64>: mov (%rax),%rax 
    0x00000000004007f3 <+67>: cmp %rbx,%rax 
    0x00000000004007f6 <+70>: jne 0x4007f0 <main1()+64> 
    0x00000000004007f8 <+72>: mov (%rdi),%rbp 
    0x00000000004007fb <+75>: callq 0x4005f0 <_ZdlPv@plt> 
    0x0000000000400800 <+80>: cmp %rbx,%rbp 
    0x0000000000400803 <+83>: je  0x400818 <main1()+104> 
    0x0000000000400805 <+85>: nopl (%rax) 
    0x0000000000400808 <+88>: mov %rbp,%rdi 
    0x000000000040080b <+91>: mov (%rdi),%rbp 
    0x000000000040080e <+94>: callq 0x4005f0 <_ZdlPv@plt> 
    0x0000000000400813 <+99>: cmp %rbx,%rbp 
    0x0000000000400816 <+102>: jne 0x400808 <main1()+88> 
    0x0000000000400818 <+104>: add $0x18,%rsp 
    0x000000000040081c <+108>: xor %eax,%eax 
    0x000000000040081e <+110>: pop %rbx 
    0x000000000040081f <+111>: pop %rbp 
    0x0000000000400820 <+112>: retq 

Код для петли похоже, является:

0x00000000004007f0 <+64>: mov (%rax),%rax 
    0x00000000004007f3 <+67>: cmp %rbx,%rax 
    0x00000000004007f6 <+70>: jne 0x4007f0 <main1()+64> 

Но есть много лишних вещей вокруг цикла. Видимо, дополнительный код сделал вещи ХОРОШЕЕ.

Answer 2

Контейнеры, такие как вектор, возвращают переменную, которая хранит указатель до конца, на end() вызов, который оптимизирован. Если вы написали контейнер, который делает некоторую Lookups и т.д. на end() вызове рассмотреть написание

for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i) 
{ 
... 
} 

скорость

Answer 3

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

Код не должен быть столь же некрасиво как то, что вы писали:

for (list<Employee>::const_iterator it=emps.begin(), end=emps.end(); 
            it != end; ++it) 

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

Answer 4

Если вам действительно нужна производительность, то пусть ваш новенький C++ 11 компилятор писать для вас:

for (const auto &i : emps) { 
    /* ... */ 
} 

Да, это лукавый (вроде). Пример Херба здесь устарел. Но так как ваш компилятор еще не поддерживает его, давайте перейдем к реальному вопросу:

Является ли это своего рода строительством, я мог бы рассчитывать на компилятор для оптимизации?

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

Answer 5

я составил следующий немного Hacky код, используя g++ 4.7.2 с -O3 -std=c++11, и получили одинаковую сборку для обеих функций:

#include <list> 
#include <string> 

using namespace std; 

struct Employee: public string { string addr; }; 

string FindAddr1(list<Employee> emps, string name) 
{ 
    for (list<Employee>::const_iterator i = emps.begin(); i != emps.end(); i++) 
    { 
    if(*i == name) 
    { 
     return i->addr; 
    } 
    } 
    return ""; 
} 

string FindAddr2(list<Employee> emps, string name) 
{ 
    list<Employee>::const_iterator end(emps.end()); 
    for (list<Employee>::const_iterator i = emps.begin(); i != end; i++) 
    { 
    if(*i == name) 
    { 
     return i->addr; 
    } 
    } 
    return ""; 
} 

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

Answer 6

Использование std algorithms

право Хэ конечно; вызов end может создавать и уничтожать временный объект, что обычно плохо.

Конечно, компилятор во многих случаях может его оптимизировать.

Существует лучшее и надежное решение: инкапсулируйте ваши петли.

Пример, который вы указали на самом деле std::find, приведите или возьмите возвращаемое значение. Многие другие циклы также имеют алгоритмы std или, по крайней мере, что-то подобное, что вы можете адаптировать - например, в моей библиотеке утилиты реализована реализация transform_if.

Итак, спрячьте петли в функции и возьмите const& до end. То же самое, что и ваш пример, но гораздо более чистым.

Answer 7

Вопреки распространенному мнению, я не вижу разницы между VC++ и gcc в этом отношении. Я сделал быструю проверку как с g ++ 4.7.2, так и с MS C++ 17 (aka VC++ 2012).

В обоих случаях я сравнил код, сгенерированный с кодом, как в вопросе (с заголовками и такие, добавленных, чтобы она компилировать), на следующий код:

string FindAddr(list<Employee> emps, string name) 
{ 
    auto end = emps.end(); 
    for (list<Employee>::iterator i = emps.begin(); i != end; i++) 
    { 
     if(*i == name) 
     { 
      return i->addr; 
     } 
    } 
    return ""; 
} 

В обоих случаях результат был по существу идентичны для двух частей кода. VC++ включает в себя комментарии к номерам строк в коде, которые изменились из-за дополнительной строки, но это было единственное различие. С g ++ выходные файлы были идентичны.

Выполнение то же самое с std::vector вместо std::list, дало почти такой же результат - никаких существенных различий. По какой-то причине g ++ переключил порядок операндов на одну команду, от cmp esi, DWORD PTR [eax+4] до cmp DWORD PTR [eax+4], esi, но (опять же) это совершенно не имеет значения.

Итог: нет, вы, вероятно, не получит ничего от ручного грузоподъемных код из цикла с современным компилятором (по крайней мере, с включенной оптимизацией - я использую /O2b2 с VC++ и /O3 с г ++; сравнения оптимизация с выключенной оптимизацией кажется мне совершенно бессмысленной).