Производительность pIter! = Cont.end () в цикле for

В последнее время Херб Саттер проходил через «Исключительный 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() перед циклом, так как на каждой итерации создается временный объект:

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

Обновить

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

20

Решение

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

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

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

Я посмотрел на то, что генерируется 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 <_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

Посмотрите на команды, расположенные в 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>

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

10

Другие решения

Я скомпилировал следующий слегка взломанный код, используя 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 "";
}

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

8

Вопреки распространенному мнению, я не вижу никакой разницы между VC ++ и gcc в этом отношении. Я быстро проверил как g ++ 4.7.2, так и MS C ++ 17 (также известный как 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 с g ++; сравнивать оптимизацию с отключенной оптимизацией мне кажется довольно бессмысленным).

4

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

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

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

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

3

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

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

для скорости

2

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

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

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

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

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

2

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

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

Есть лучшее и более надежное решение: инкапсулировать ваши петли.

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

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

0
По вопросам рекламы [email protected]