Будет ли неэффективность постфиксных операторов ++/ оптимизирована для итераторов STL?

Я знаю, что постфиксные версии операторов инкремента/декремента, как правило, оптимизируются компилятором для встроенных типов (т. е. копирование не производится), но относится ли это к iterators?

По сути, это просто перегруженные операторы, и их можно реализовать любым количеством способов, но, поскольку их поведение строго определено, можно их оптимизировать, и если да, то используются ли они каким-либо/многими компиляторами?

#include <vector> 

void foo(std::vector<int>& v){
  for (std::vector<int>::iterator i = v.begin();
       i!=v.end();
       i++){  //will this get optimised by the compiler?
    *i += 20;
  }
}

c++ iterator post-increment
person Dominic Gurto    schedule 21.06.2011    source источник
comment
Это интересный вопрос, даже если это это микрооптимизация.   -  person jpm    schedule 21.06.2011
comment
если операции итератора не имеют побочных эффектов, компилятору разрешено оптимизировать постинкрементную версию в соответствии с правилом как если бы. Будет это или нет, зависит от компилятора. Сборка Indebug, она, вероятно, не будет оптимизирована, так зачем замедлять отладку? Я не вижу проблемы в том, чтобы выработать полезную привычку использовать постинкремент только тогда, когда он вам действительно нужен.   -  person Gene Bushuyev    schedule 21.06.2011
comment
@ Джин, я согласен, и у меня есть привычка использовать предварительный приращение всякий раз, когда я могу. Мне просто интересно :)   -  person Dominic Gurto    schedule 21.06.2011

Ответы (1)


arrow_upward
9
arrow_downward

В конкретном случае std::vector в реализации STL GNU GCC (версия 4.6.1) я не думаю, что будет разница в производительности на достаточно высоких уровнях оптимизации.

Реализация прямых итераторов на vector предоставлена ​​__gnu_cxx::__normal_iterator<typename _Iterator, typename _Container>. Давайте посмотрим на его конструктор и постфиксный оператор ++:

  explicit
  __normal_iterator(const _Iterator& __i) : _M_current(__i) { }

  __normal_iterator
  operator++(int)
  { return __normal_iterator(_M_current++); }

И его экземпляр в vector:

  typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;

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

Но действительно ли он оптимизирован? Давай выясним. Тестовый код:

#include <vector>

void test_prefix(std::vector<int>::iterator &it)
{
    ++it;
}

void test_postfix(std::vector<int>::iterator &it)
{
    it++;
}

Выходная сборка (на -Os):

    .file   "test.cpp"
    .text
    .globl  _Z11test_prefixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE
    .type   _Z11test_prefixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE, @function
_Z11test_prefixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE:
.LFB442:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    movl    8(%ebp), %eax
    addl    $4, (%eax)
    popl    %ebp
    .cfi_def_cfa 4, 4
    .cfi_restore 5
    ret
    .cfi_endproc
.LFE442:
    .size   _Z11test_prefixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE, .-_Z11test_prefixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE
    .globl  _Z12test_postfixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE
    .type   _Z12test_postfixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE, @function
_Z12test_postfixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE:
.LFB443:
    .cfi_startproc
    pushl   %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset 5, -8
    movl    %esp, %ebp
    .cfi_def_cfa_register 5
    movl    8(%ebp), %eax
    addl    $4, (%eax)
    popl    %ebp
    .cfi_def_cfa 4, 4
    .cfi_restore 5
    ret
    .cfi_endproc
.LFE443:
    .size   _Z12test_postfixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE, .-_Z12test_postfixRN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE
    .ident  "GCC: (Debian 4.6.0-10) 4.6.1 20110526 (prerelease)"
    .section    .note.GNU-stack,"",@progbits

Как видите, в обоих случаях выводится одна и та же сборка.

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

person bdonlan    schedule 21.06.2011
comment
Хороший анализ. Я ожидаю, что любой хороший оптимизирующий компилятор будет работать так же. - person Mark Ransom; 21.06.2011
comment
Спасибо за этот ответ. Я подозреваю, что @Mark прав, хотя мне интересны другие компиляторы. - person Dominic Gurto; 21.06.2011
comment
Не стесняйтесь тестировать и с другими компиляторами :) - person bdonlan; 21.06.2011
comment
Однако является ли это действительным тестом? Вы уверены, что не просто видите, как оптимизатор заменяет it++ на ++it, когда видит, что результат игнорируется? Казалось бы, это хорошая оптимизация, учитывая широкое использование постфикса ++ в циклах for. (Не смейтесь, я видел, как оптимизатор заменял printf("foo\n"); на puts("foo");.) - person Mike DeSimone; 21.06.2011
comment
Это именно то, что я вижу и что я тестирую :) Очевидно, что если вы действительно где-то храните возвращаемое значение it++, для этого нужно выполнить дополнительную работу; то же самое относится и к x = ++it. Вопрос в том, достаточно ли умен оптимизатор, чтобы не выполнять дополнительную работу, когда она не нужна. - person bdonlan; 21.06.2011