Подтвердить что ты не робот

Производительность 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.

4b9b3361

Ответ 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

Используйте std алгоритмы

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

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

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

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

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