Pull to refresh
280.52
PVS-Studio
Static Code Analysis for C, C++, C# and Java

Есть ли практический смысл использовать для итераторов префиксный оператор инкремента ++it, вместо постфиксного it++

Reading time 5 min
Views 22K
c++ or ++c
Я все-таки решил разобраться, есть ли смысл при работе с итераторами писать ++iterator, а не iterator++. Мой интерес к этому вопросу возник не из любви к искусству, а из практических соображений. Мы давно хотим развивать PVS-Studio не только в направлении поиска ошибок, но и в сторону выдачи подсказок по оптимизации кода. Выдача сообщения, что лучше писать ++iterator вполне уместна в плане оптимизации.

Но вот насколько эта рекомендация актуальна в наше время? В стародавние времена, например, советовали не повторять вычисления. Считалось хорошим тоном вместо:
X = A + 10 + B;
Y = A + 10 + C;

написать так:
TMP = A + 10;
X = TMP + B;
Y = TMP + C;


Сейчас такая мелочная ручная оптимизация бессмысленна. Компилятор справится с такой задачей не хуже. Только лишнее загромождение кода.

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

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

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

Префиксный оператор инкремента изменяет состояние объекта и возвращает себя в уже изменённом виде. Оператор префиксного инкремента в классе итератора для работы с std::vector может выглядеть так:
_Myt& operator++()
{ // preincrement
  ++_Myptr;
  return (*this);
}

В случае постфиксного инкремента ситуация сложнее. Состояние объекта должно измениться, но при этом возвращено предыдущее состояние. Возникает дополнительный временный объект:
_Myt operator++(int)
{ // postincrement
  _Myt _Tmp = *this;
  ++*this;
  return (_Tmp);
}

Если мы хотим только увеличить значение итератора, то получается, что префиксная форма предпочтительна. Поэтому, один из советов по микро-оптимизации программ писать «for (it = a.begin(); it != a.end; ++it)» вместо «for (it = a.begin(); it != a.end; it++)». В последнем случае происходит создание ненужного временного объекта, что снижает производительность.

Более подробно все это можно почитать в книге Скотта Мейерса «Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов» (Правило 6. Различайте префиксную форму операторов инкремента и декремента) [1].

Теория закончилась. Перейдем к практике. Есть ли смысл в коде заменить постфиксный инкремент на префиксный?
size_t Foo(const std::vector<size_t> &arr)
{
  size_t sum = 0;
  std::vector<size_t>::const_iterator it;
  for (it = arr.begin(); it != arr.end(); it++)
    sum += *it;
  return sum;
}

Я понимаю, что можно уйти в область философии. Мол, потом возможно контейнером будет не vector, а другой класс, где итераторы очень сложные и тяжёлые объекты. При копировании итератора надо делать новое подключение к базе данных, ну или что-то в этом духе. Следовательно, всегда следует писать ++it.

Но это в теории. А вот встретив на практике где-то в коде такой цикл, есть смысл заменить it++ на ++it? Не лучше ли положиться на компилятор, который и без нас догадается, что лишний итератор можно выбросить?

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

Да, нужно заменить it++ на ++it.

Да, компилятор произведёт оптимизацию и не будет никакой разницы, какой инкремент использовать.

Я выбрал «средний компилятор» и создал тестовый проект для Visual Studio 2008. В нём есть две функции, считающие сумму с использованием it++ и ++it, а также измерение времени их работы. Скачать проект можно здесь. Код функций, скорость которых замерялась:

1) Постфиксный инкремент. iterator++.
std::vector<size_t>::const_iterator it;
for (it = arr.begin(); it != arr.end(); it++)
  sum += *it;

2) Префиксный инкремент. ++iterator.
std::vector<size_t>::const_iterator it;
for (it = arr.begin(); it != arr.end(); ++it)
  sum += *it;

Скорость работы в Release версии:

iterator++. Total time: 0.87779

++iterator. Total time: 0.87753

Это ответ на вопрос, может ли компилятор оптимизировать постфиксный инкремент. Может. Если посмотреть реализацию (ассемблерный код), то видно, что обе функции реализованы идентичным набором инструкций.

А теперь ответим на вопрос, зачем же тогда стоит менять it++ на ++it. Замерим скорость работы Debug версии:

iterator++. Total time: 83.2849

++iterator. Total time: 27.1557

Писать код так, чтобы замедляться в 30, а не в 90 раз вполне имеет практический смысл.

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

Дополнительно я провел эксперимент, что будет, если использовать для индексации старый добрый size_t. Это, конечно, к рассматриваемой теме не относится. Я понимаю, что итераторы нельзя сравнивать с индексами, и что это более высокоуровневые сущности. Но всё равно из любопытства написал и замерил скорость следующих функций:

1) Классический индекс типа size_t. i++.
for (size_t i = 0; i != arr.size(); i++)
  sum += arr[i];

2) Классический индекс типа size_t. ++i.
for (size_t i = 0; i != arr.size(); ++i)
  sum += arr[i];

Скорость работы в Release версии:

iterator++. Total time: 0.18923

++iterator. Total time: 0.18913

Скорость работы в Debug версии:

iterator++. Total time: 2.1519

++iterator. Total time: 2.1493

Как и следовало ожидать, скорость работы i++ и ++i совпала.
Примечание. Код с size_t работает быстрее по сравнению с итераторами за счет того, что отсутствует проверка на выход за границу массива. Цикл с итераторами можно сделать столь же быстрым в Release-версии, вписав "#define _SECURE_SCL 0".
Чтобы было проще оценить результаты замеров скорости, представлю их виде таблицы (рисунок 1). Результаты я пересчитал, взяв за единицу время работы Release версии с iterator++. И еще немного округлил числа для простоты.
Рисунок 1. Время работы алгоритмов вычисления суммы.
Рисунок 1. Время работы алгоритмов вычисления суммы.

Каждый сам может сделать для себя выводы. Они зависят от типа решаемых задач. Для себя лично я сделал следующие:
  1. Я убедился в целесообразности такой микрооптимизации. В PVS-Studio стоит реализовать поиск постфиксного увеличения итератора, если его предыдущее состояние не используется. Некоторые программисты сочтут эту функциональность полезной. А остальные, если она мешает, всегда смогут в настройках отключить данную диагностику.
  2. Я всегда буду писать ++it. Я и раньше так делал. Но делал это «на всякий случай». Теперь я вижу пользу от этого, так как мне важен регулярный запуск отладочных версий. Конечно, в целом на время работы ++it окажет очень маленький эффект. Но если в разных местах не делать вот такие небольшие оптимизации, то потом будет поздно. Профайлер мало чем поможет. Медленные места будут «размазаны тонким слоем» по всему коду.
  3. Я замечаю, что все больше времени анализатор PVS-Studio проводит внутри различных функций классов std::vector, std::set, std::string и так далее. Это время растёт и растёт, так как появляются все новые и новые диагностические правила, а их удобно писать как раз с использованием STL. Вот думаю, не пришло ли то самое страшное время, когда в программе появляются свои собственные специализированные классы строк, массивов и так далее. Но это я о своём… Вы меня не слушайте! Я крамольные вещи говорю… Тссс...

P. S.

Сейчас кто-то скажет, что преждевременная оптимизация — это зло [2]. Когда нужна оптимизация, надо брать профайлер и искать узкие места. Это я всё знаю. И конкретных узких мест у меня давно нет. Но вот когда ждёшь завершения тестов в течение 4 часов, начинаешь подумывать, что выиграть даже 20% скорости — это уже хорошо. А складывается вот такая оптимизация из итераторов, размеров структур, местами отказом от STL или Boost и так далее. Думаю, некоторые разработчики меня хорошо поймут.

Библиографический список


  1. Мейерс С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов: Пер. с англ. — М.: ДМК Пресс, 2000. — 304 с.: ил. (Серия «Для программистов»). ISBN 5-94074-033-2. ББК 32.973.26-018.1.
  2. Елена Сагалаева. Преждевременная оптимизация. http://alenacpp.blogspot.com/2006/08/blog-post.html


UPDATE: После статьи "Учимся правильно бенчмаркать (в том числе итераторы)" я поправил код проекта, сделал новые замеры и немного скорректировал статью. Для Release версий никаких изменений нет, а вот Debug показал сильное отличие. Впрочем на корректность статьи, её содержание и выводы это не влияет.
Tags:
Hubs:
+89
Comments 112
Comments Comments 112

Articles

Information

Website
pvs-studio.com
Registered
Founded
2008
Employees
31–50 employees