Производительность pIter!= Cont.end() in for loop
В последнее время я получал "Исключительный С++" Херба Саттера, и у меня есть серьезные сомнения в отношении конкретной рекомендации, которую он дает в пункте 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() перед циклом, поскольку на каждой итерации создается временный объект:
Для большинства контейнеров (включая список) вызов end() возвращает временный объект, который должен быть построен и уничтожен. Поскольку значение не изменится, пересчет (и восстановление и redestroying), он на каждой итерации цикла тоже бесполезен неэффективен и неэстетичен. Значение должно вычисляться только один раз, хранится в локальном объекте и повторно используется.
И он предлагает заменить следующим:
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() в большинстве случаев, когда меня не так беспокоит производительность. Но я хочу точно знать, является ли это своего рода конструкцией, на которую я мог бы рассчитывать на оптимизацию компилятора?
Обновление
Спасибо за ваши предложения о том, как сделать этот бесполезный код лучше. Обратите внимание, мой вопрос касается компилятора, а не программирования. Единственные релевантные ответы на данный момент - NPE и Ellioh.
Ответы
Ответ 1
UPD: Книга, о которой вы говорите, была опубликована в 1999 году, если я не ошибаюсь. То, что 14 лет назад, и в современном программировании 14 лет - это много времени. Многие рекомендации, которые были хорошими и надежными в 1999 году, могут быть полностью устаревшими. Хотя мой ответ касается одного компилятора и единой платформы, есть и более общая идея.
Уход за дополнительными переменными, повторное использование возвращаемого значения тривиальных методов и подобных трюков старого С++ - это шаг назад к С++ 1990-х годов. Тривиальные методы, такие как end(), должны быть хорошо отлажены, а результат встраивания должен быть оптимизирован как часть кода, из которого он вызван. 99% ситуаций не требуют ручных действий, таких как создание переменной end. Такие вещи следует делать только в том случае, если:
- Вы знаете, что на некоторых компиляторах/платформах, которые вы должны запускать на этом коде, недостаточно оптимизированы.
- Это стало узким местом в вашей программе ( "избегайте преждевременной оптимизации" ).
Я посмотрел, что генерируется 64-битным g++:
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 <[email protected]>
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 <[email protected]>
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
Посмотрите на команды, расположенные в 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 <[email protected]>
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 <[email protected]>
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 <[email protected]>
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 <[email protected]>
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>
Но вокруг цикла много лишних вещей. По-видимому, дополнительный код сделал вещи WORSE.
Ответ 2
Я скомпилировал следующий слегка взломанный код с помощью 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 "";
}
В любом случае, я думаю, что выбор между двумя версиями должен основываться прежде всего на принципах удобочитаемости. Без профилирования данных микро-оптимизации, подобные мне, выглядят преждевременными.
Ответ 3
Вопреки распространенному мнению, я не вижу разницы между VС++ и gcc в этом отношении. Я сделал быструю проверку как с g++ 4.7.2, так и с MS С++ 17 (aka VС++ 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 "";
}
В обоих случаях результат был по существу идентичным для двух частей кода. VС++ включает в себя комментарии к номерам строк в коде, которые изменились из-за дополнительной строки, но это было единственное различие. С g++ выходные файлы были идентичны.
Выполняя то же самое с std::vector вместо std::list, дал почти такой же результат - никакой существенной разницы. По какой-то причине g++ переключил порядок операндов на одну команду, от cmp esi, DWORD PTR [eax+4] до cmp DWORD PTR [eax+4], esi, но (опять же) это совершенно не имеет значения.
Нижняя строка: нет, вы вряд ли выиграете от ручного выведения кода из цикла с помощью современного компилятора (по крайней мере с включенной оптимизацией - я использовал /O2b2 с VС++ и /O3 с g++, сравнение оптимизации с отключенной оптимизацией кажется мне совершенно бессмысленным).
Ответ 4
Несколько вещей... во-первых, что затраты на создание итератора (в режиме деблокирования, непроверенные распределители) минимальны. Обычно это обертки вокруг указателя. С проверенными распределителями (по умолчанию в VS) у вас может быть некоторая стоимость, но если вам действительно нужна производительность, после тестирования перестроить с помощью непроверенных распределителей.
Код не должен быть таким же уродливым, как то, что вы отправили:
for (list<Employee>::const_iterator it=emps.begin(), end=emps.end();
it != end; ++it )
Основное решение о том, хотите ли вы использовать один или другие подходы, должно быть в терминах того, какие операции применяются к контейнеру. Если контейнер может изменить его размер, вы можете захотеть пересчитать итератор end на каждой итерации. Если это не так, вы можете просто предварительно прекомпилировать один раз и повторно использовать его, как в приведенном выше коде.
Ответ 5
Контейнеры, такие как векторная переменная, которая хранит указатель до конца, на end() вызов, который оптимизирован. Если вы написали контейнер, который выполняет некоторые поисковые запросы и т.д. На вызов end(), рассмотрите возможность записи
for (list<Employee>::const_iterator i = emps.begin(), end = emps.end(); i != end; ++i)
{
...
}
для скорости
Ответ 6
Если вам действительно нужна производительность, вы можете написать свой блестящий новый компилятор С++ 11 для него:
for (const auto &i : emps) {
/* ... */
}
Да, это язык в щеке (вроде). Пример травы теперь устарел. Но так как ваш компилятор еще не поддерживает его, давайте перейдем к реальному вопросу:
Является ли это своего рода конструкцией, на которую я мог бы рассчитывать на оптимизацию компилятора?
Мое правило состоит в том, что авторы компилятора более умны, чем я. Я не могу полагаться на компилятор для оптимизации любой части кода, потому что он может выбрать оптимизацию чего-то еще, что имеет большее влияние. Единственный способ узнать наверняка - попробовать оба подхода в вашем компиляторе в вашей системе и посмотреть, что произойдет. Проверьте результаты профилировщика. Если вызывается вызов .end(), сохраните его в отдельной переменной. В противном случае, не беспокойтесь об этом.
Ответ 7
Он, конечно, конечно; вызов end может создавать и уничтожать временный объект, что обычно плохо.
Конечно, во многих случаях компилятор может оптимизировать это.
Существует лучшее и надежное решение: инкапсулировать ваши циклы.
Приведенный вами пример фактически std::find, дает или принимает возвращаемое значение. Многие другие циклы также имеют алгоритмы std или, по крайней мере, что-то подобное, что вы можете адаптировать, например, моя библиотека утилиты имеет реализацию transform_if.
Итак, скройте петли в функции и возьмите const& в end. То же самое, что и в вашем примере, но гораздо более чистым.
