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

    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 показал сильное отличие. Впрочем на корректность статьи, её содержание и выводы это не влияет.

    PVS-Studio

    266,15

    Ищем ошибки в C, C++ и C# на Windows, Linux, macOS

    Поделиться публикацией
    Комментарии 112
      +5
      А не могли бы вы сравнить ещё два варианта? — Когда написано

      for (it = arr.begin(); it != arr.end(); )
      sum += *(it++);


      и когда написано

      for (it = arr.begin(); it != arr.end(); )
      sum += *(++it);


      Не обращая внимание на правильность ответа. Просто интересно.
        0
        В смысле, в последнем предполагается поменять условие it != arr.end() на другое, а то не запустится.
          0
          Померил. Картина прежняя.
          Скорость работы Release версий совпадает.
          В Debug версии разница между it++ и ++it почему то увеличилась. Было в 3 раза. Теперь в 7.
          • НЛО прилетело и опубликовало эту надпись здесь
              +1
              Зачем +1? Вот так и сажаются в программах ошибки. :) Когда хочется написать как-то «особенно». :)
              Попробовал. Получается что немного быстрей (Release):
              iterator++. Total time : 2.35
              ++iterator. Total time : 2.35
              
              it < end_. iterator++. Total time : 2.22
              it < end_. ++iterator. Total time : 2.24
              
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  В end() уже +1, иначе стоп-условие != end() бы не работало.
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      begin() соответствует первому элемент, end() — последнему+1, т.е. для 10 элементов будет 0 и 10 соответственно: for (i=0; i != 10; ++i)
                      • НЛО прилетело и опубликовало эту надпись здесь
                          +1
                          У меня получилось, что < end работает быстрее чем != end из-за оптимизации компилятора:
                          при < end он фактически немного разворачивает цикл:
                          sum += a[i];
                          sum += a[i+1];

                          в то время как при != end он почему-то этого не делает. Если развернуть ручками, то < end и != end сравниваются по скорости.
                            0
                            Так( < end_ ) писать можно не для всякого контейнера, наверно, даже только вектора.
                              0
                              Конечно, поэтому в STL и пишут всегда != end а не < end
                            0
                            В вашем примере дело не в знаке, а в том, что вызов end() вынесен за пределы цикла.
                      0
                      ууу… :))
            0
            Непонятен смысл сравнения именно vector::iterator, ведь во всех вменяемых реализациях в релизе он оптимизируется в T*. Гораздо любопытнее было бы посмотреть как обстоят дела с другими конейнерами (map, set).
              0
              Увеличение/уменьшение vector::iterator это самая типовая ситуация. При работе с тем же set, перебирать все элементы, мне кажется редкое явление. Там типовое использование это find. А смысл сравнение прост. Стоит сказать программисту, что лучше писать ++it или не отвлекать его почём зря.
                0
                Поддерживаю комментарий Tasman99. «Типовой ситуацией» использования итераторов назвал бы итераторы списков, а никак не векторов, у которых [] за константу и которые многими используются просто как динамические массивы без осознания из STL-совместимости. (Я не про себя, если что, а про типовую ситуацию.)
              +11
              Ну вообще, это типа бритвы оккама. Если вам не нужно предыдущее значение (копирование его из функции, и всё что с этим связано), не надо использовать постфиксный оператор. Тогда вопроса постфикс VS префикс вообще не будет стоять. Переформулирую проще: если можно что-то не делать, то лучше этого не делать :)

              Поэтому пишите ++it, и всё будет хорошо. Надо уметь ломать свои привычки ради достижения великой цели. :D
                0
                Я то и так пишу. Вопрос, навязывать ли это другим программистам, реализовав соответствующую диагностику в PVS-Studio.
                  +7
                  Конечно навязывать! Зачем копировать, если можно не копировать. :)
                    +5
                    Конечно, не навязывать!
                    Скорость в релизе одинаковая? Одинаковая. Читабельность одинаковая? Одинаковая.
                    Не фиг голову лишний раз морочить.
                      +4
                      Навязывать. Пусть приучаются к аккуратности, и используют синтаксические конструкции обоснованно.
                        0
                        whoozle VS tangro — А вот и не подерётесь!
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Не делал. Я уверен, что картина будет в точности такая же. Если есть желание — исходники прилагаются, можно попробовать собрать чем-то ещё.
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Получается, что компилятор не смог соптимизировать постфиксный вариант?
                            • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            Было бы интересно посмотреть на результаты STLPort — может статься, что у него не будет существенной разницы между Release и Debug. Тогда окажется, что это проблема только MS STL.
                          +8
                          Не считаю это оптимизацией, тем более преждевременной. Всегда пишу ++smth, если не нужно предыдущее значение и smth++, если нужно. В циклах for оно, как правило, ни к чему, поэтому ++smth. Просто, хороший тон, имхо.

                          Где-то видел ещё замеры скорости компиляции для разных случаев, если уж совсем с ума сходить :)
                            +3
                            Именно так. Если где-то видишь i++, уже на автомате воспринимаешь ожидаешь каког-то изврата с возвратом значения до инкремента.
                            +4
                            Насколько я знаю, это даже нельзя назвать «преждевременной оптимизацией» — просто признак хорошего стиля, т.е. нечто что должно быть «на кончиках пальцев» и применяться всегда без лишних размышлений. Это из Саттера или Александреску и я полностью с ними согласен :)
                              +2
                              Совершенно согласен. Это типа передачи данных, где возможно, по константным ссылкам. Просто хороший стиль, дающий некоторые преимущества сразу же.
                                0
                                Да, тоже соглашаюсь. Саттер и Александреску называют код типа i++ там, где старое значение не используется, «преждевременной пессимизацией».
                                –17
                                Заебали со своим PVS-Studio. На НЛП уже какое-то похоже.
                                  +10
                                  могу порекомендовать блог, в котором PVS-Studio не упоминается.
                                    –1
                                    кстати, в php потеря скорости при $i++ по сравнению ++$i в пределах 10-20% )
                                    +7
                                    А причем здесь PVS-Studio? Решил написать об экспериментах с итераторами. И если судить по голосам, то людям понравилось. Значит не зря.
                                    Но зачем мне врать то? Мол, дело было вечером, делать было нечего… Дай думаю займусь с итераторами… Терпеть не могу стиль «мне _случайно_ в руки попал телефон/гаджет, и он мне так понравился, что сейчас и вам про него расскажу». Тьфу. Лучше честно написать, чем так.
                                      0
                                      Стиль «мне PVS-Studio в руки попал PVS-Studio, и он мне PVS-Studio так понравился, что сейчас PVS-Studio и вам про него расскажу» конечно лучше, что сказать.
                                      +7
                                      Заебали со своим «Заебали».
                                        +4
                                        stack overflow :)
                                      +1
                                      Вы занимаетесь оптимизацией вместо компилятора.
                                      Не нужно этого делать.

                                      ИМХО, обе приведенный ниже рекомендации плохие:
                                      1) Рекомендуется заменить *(it++) на *(++it), т.к. компилятор еще не оптимизирует / плохо оптимизирует эту задачу.

                                      2) Рекомендуется заменить if (x==3) на (3==x) т.к. это позволит избежать потенциальных ошибок.
                                        +6
                                        Ваша первая «рекомендация» особенно плохая, потому что *(it++) и *(++it) отличаются не только синтаксисом, а приведут к разным результатам.
                                        0
                                        Может немного не в тему, но:
                                        1. Есть ли смысл перебирать массивы с конца, когда не важен порядок? Если есть, то --i или i--?
                                        2. Есть ли смысл использовать итератор типа uint?
                                          0
                                          1 — Странный вопрос. Если всё равно, перебирать элементы с начала или с конца, то какой смысл должен быть? :-)

                                          2 — Когда как. Часто для циклов лучше использовать size_t и т.п. Так безопасней при работе с большими массивами. Плюс в ряде случаев 64-битный код работает быстрее. Пример такого кода и замер скорости я приводил в этой статье — Разработка ресурсоемких приложений в среде Visual C++ (см. четвертый раздел).
                                            +1
                                            1. Ну по идее смысл существует — если перебирать с начала, то по идее будет минимизировано количество кэш промахов. Правда все зависит от типа данных и их расположения в памяти, но в любом случае это очень интересная и не простая тема с множеством разных нюансов. Лет 10 назад Крис Касперски писал ряд интересных исследований по этому поводу в журнале «Программист».
                                              0
                                              Кажется, когда-то читал где-то, что разницы нет. Кэш умеет работать и с чтением в одну сторону и в другую. Могу и ошибаться. В любом случае это очень тонкие материи.
                                                +2
                                                Скорость может оказаться выше в случае обратного обхода, так как цикл в таком случае можно будет описать парой инструкций
                                                mov eax, iterations_count
                                                loop_iteration:
                                                ... // тело цикла
                                                loop loop_iteration

                                                что на некоторых системах может дать прирост производительности.
                                                Но это всё экономии на спичках, и когда такого рода вопросы становятся реальными (а не праздного интереса ради),, следует подумать о написании критичных участков на ассемблере. Если это неважно, пускай компилятор сам решит, что на target-платформе будет работать быстрее.
                                                +1
                                                А почему промахи должны увеличиться? Заполняем мы всю строку кэша, а не одно значение. Что так, что эдак.
                                                +2
                                                >> Странный вопрос. Если всё равно, перебирать элементы с начала или с конца, то какой смысл должен быть? :-)

                                                Ну так-то машинный код разным будет. Сейчас написал программу, проверил дизассемблером: некоторые инструкции отличаются. Например, при декременте компилятор генерирует:

                                                sub esi, 1
                                                jns short loc_401011

                                                А при инкременте:

                                                inc esi
                                                cmp esi, edi
                                                jle short loc_401016


                                                Так что разница в скорости может и быть.
                                                  +3
                                                  Разница может быть, а может её и не будет — при таких нано-оптимизациях уже нужно смотреть на логику конкретного процессора, как у него реализован конвейер и предсказатель переходов. Скорее всего, на современных десктопных процах разница если и будет, то очень небольшая, особенно если не забывать, что внутри цикла должно что-то делаться.
                                                    0
                                                    Core2 и выше умеют склеивать cmp/jxx в 1 макрокоманду, которая, по-идее будет убрана предсказателем ветвлений.
                                                    А вот на других процах (в особенности на in-order) разница будет
                                                  0
                                                  1. смысл есть. сравнение с нулем как минимум не медленнее (а как максимум быстрее и компактнее). На java у меня получилось, что наиболее оптимальным циклом будет

                                                  for ( int i = max; --i >= 0; )
                                                  {
                                                  [...]
                                                  }

                                                  Если же гарантировано, что max > 0, то еще чуток можно сэкономить, использовав do-while
                                                    0
                                                    Это только для чисел. Для прочих же итераторов разницы, скорее всего, не будет.
                                                  +1
                                                  Есть ли практический смысл использовать в каком бы то ни было контексте постфиксный оператор инкремента i++ вместо префиксного ++i? Нет, такого смысла нет.
                                                    +1
                                                    Покажите, пожалуйста, как вы будете удалять элементы из map\set в цикле
                                                      –7
                                                      Я не буду этого делать: я не использую C++.
                                                        +5
                                                        Тогда, что Ваш комментарий делает в С++ топике? Показываете свою неосведомленность?
                                                          +1
                                                          Я сначала не обратил внимание, что это блог C++, и высказался о синтаксисе вообще. Об особенностях таких конструкций, как map, set и iterator, я не осведомлён, но слабо верю, что невозможно написать удаление элементов из map в цикле без использования постфиксного инкремента. Существование двух видов инкремента и декремента само по себе изначально бессмысленно. Единственное, чему могут послужить постфиксные операторы, — это внесение путаницы и неясности, лучший пример чему — названия языка C++.
                                                            0
                                                            На самом деле в силу некоторых особенностей, бывает необходимо использовать постфиксный оператор. Иногда, использование постфиксного оператора улучшает читаемость.
                                                            Ну, а насчет map\set и итераторов, после вызова функции erase(it) итератор становится невалидным и разумным действием здесь будет именно erase(it++), который сместит итератор и удалит предыдущий. Конечно этого можно достичь введение дополнительного, временного итератора. Но зачем?
                                                        +1
                                                        Очень просто — сохранив предыдущее значение итератора во временную переменную, ровно также как это и делает постфиксный ++. То, что конструкция будет немного сложнее — это естественно, в этом и есть различие между понятным и cryptic кодом (можно вообще на perl писать, тогда всё ещё короче получится).
                                                      +1
                                                      Итераторы… Я думал, их нормальное высокоуровневое использование в c++ выглядит так:
                                                      for (std::vector<size_t>::iterator it(v); ! it.end(); it.next()) { /**/ }

                                                      И никакого инкремента, и безболезненный обход списков.
                                                        +1
                                                        Тогда в перегрузке операторов не будет никакого смысла. А ведь это часто упрощает читаемость кода.
                                                          0
                                                          Что, ++ у вас упрощает читабельность кода?

                                                          Еще расскажите мне, что ++ читабельнее слова «next». Или вы за байты исходного кода боретесь?
                                                            +2
                                                            Ну расскажу, для меня читабельнее
                                                              –1
                                                              Ну а я пока еще не стал роботом и предпочитаю читать слова, а не разгадывать знаки.
                                                          +3
                                                          В STL не высокоуровневые итераторы, а самые что ни на есть пойнтеры — они не знают про конец вектора, так что !it.end() работать не будет.
                                                          0
                                                          Никогда не слышал о том, чтобы итераторы в релизе были 5 раз (sic!) медленнее чем счётчик. По моим представлениям код должен генерироваться в обоих случаях чуть ли не идентичный. Или это какие-то фокусы связанные с x64?
                                                            0
                                                            Просто не надо всегда верить теоретикам, которые рассказывают сказки, что stl код за счет оптимизации компилятора, будет такой же эффективный, как написанный в стиле Си. :-)
                                                              0
                                                              Оснований не верить вашим измерениям у меня больше :)
                                                              На моей машине результаты с итераторами и счётчиками одинаковые, но у меня 32 бита. Можете выложить ваш код и сгенерированный ассемблер (/FAs) на какой-нибудь pastebin?
                                                                0
                                                                Я посланник тёмных сил и моя цель всех обмануть. :)
                                                                www.viva64.com/external-pictures/TestSpeedExp-cpp-and-asm.zip
                                                                  0
                                                                  ; Generated by VC++ for Common Language Runtime

                                                                  Так у вас что не native C++, а CLR что-ли? Почему тогда об этом в статье ни слова, это же принципиально другое дело!
                                                                    0
                                                                    Это я баловался. Не то выложил. Исправился.
                                                                      +3
                                                                      Вы ведь Release версию asm выложили, я так понимаю? Тогда такой момент. Судя по всему, версии MSVC до 2010-ой делают проверку итераторов (checked iterators) даже в Release билде (_SECURE_SCL = 1). А вот 2010, которая у меня, её включает только в Debug. Естественно, эта проверка может нехило всё замедлить. Попробуйте её отключить для Release, как это скажется на результатах?
                                                                      #ifndef _DEBUG
                                                                      #define _SECURE_SCL 0
                                                                      #endif
                                                                        0
                                                                        Спасибо. Вот и выяснилось, почему size_t работал быстрее. После добавления "#define _SECURE_SCL 0" время работы Release версии с iterator и size_t сравнялось. Спасибо за замечание.

                                                                        Был не прав. Признаю. Здесь компилятор смог полностью оптимизировать stl код.
                                                                          0
                                                                          Добавьте, пожалуйста, примечание об этом в статью, чтобы не вводить людей в заблуждение.
                                                                            0
                                                                            А где я ввожу в заблуждение? В каком абзаце я написал неправду?
                                                                              +2
                                                                              В заблуждение вводит табличка, которая показывает что счётчики существенно быстрее итераторов, но не объясняет причину этого.
                                                                                –5
                                                                                В статье отмечено: «Я понимаю, что итераторы нельзя сравнивать с индексами, и что это более высокоуровневые сущности».

                                                                                Например, они могут осуществлять проверку выхода за рамки массива. Где же здесь введение в заблуждение? Если просто взять и использовать итераторы — будет медленнее. Это как раз наоборот вводят в заблуждение, когда говорят «просто используйте stl и будет не менее быстро». Это как раз неправда и надо знать тонкости. :)
                                                                                  +3
                                                                                  И это — ваше обоснование того, что не стоит мельком упомянуть в статье, откуда взялось различие в 5 раз? Мол, раз они недоговаривают, то и мы не будем?
                                                                                    –5
                                                                                    Невозможно упомянуть про всё. Я уже немало статей здесь опубликовал и знаю, что как подробно не пиши, кто-то скажет, а почему вот так не померено, а почему вот тут про X/Y/Z не сказано. Когда опубликуете здесь еще несколько статей, то поймете, откуда такая моя равнодушная позиция к тому, что статья в чем-то неполная. :-)

                                                                                    Пока просто можете считать меня бякой.
                                                                                      +4
                                                                                      Если вы посмотрите на другие статьи, то увидите, что зачастую авторы добавляют небольшие примечания в конец статьи по комментариям. Думаю, что это занимает уж точно меньше времени, чем вы тратите на обсуждение в комментариях. Так что вашу позицию я не понимаю, а считать буду что у вас есть какие-то свои причины этого не делать, либо это проявление каких-то своеобразных принципы.
                                                                                0
                                                                                Я не думаю, что вы вводите людей в заблуждение, но информацию, по-моему, надо обязательно добавить к посту — она весьма интересна и релевантна теме.
                                                              –2
                                                              собственно говоря, а почему замеры времени осуществляются таким вот способом?
                                                              Что-то сомнительна точность будет. Так как работа функций будет затрачивать время.
                                                              И почему именно этот метод? Ведь можно было бы применить и запрос времени выполнения потока в юзермоде, полученное через GetThreadTimes lpUserTime.
                                                              А вообще столь небольшие изменения проверяются не счетчиками и таймерами, а непосредственным дизассемблированием исполняемого файла. И там уже будет сразу видно какие инструкции и в каком кол-ве используются.
                                                              К томуже тест необходимо производить не только на одном компиляторе. Допустим lcc тоже используется, но он практически не умеет нормально оптимизировать код.
                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                  0
                                                                  Предлагаю написать более обстоятельную статью. Я честно буду благодарен. Я написал, как смог. :)
                                                                  –1
                                                                  Написал 2 пример, скомпилил прогу в VS 2008 с отключенной оптимизацией.
                                                                  Примеры вида:
                                                                  int x;

                                                                  for (x = 0; x < 1000; ++x)
                                                                  {
                                                                    Sleep(0);
                                                                  }




                                                                  и

                                                                  int x;

                                                                  for (x = 0; x < 1000; x++)
                                                                  {
                                                                    Sleep(0);
                                                                  }




                                                                  Далее каждый EXE файл дизассемблировал через IDA и получил 2 абсолютно одинаковых исходника.
                                                                  Так что для простых операций в цикле данные конструкции дают одинаковый код.
                                                                    +3
                                                                    И что дальше?
                                                                      0
                                                                      Вот именно, что для простых. Между банальным int и сложным классом итератора есть существенная разница не только для программиста, но и для компилятора. Мне казалось, это очевидно.
                                                                      +1
                                                                      С++: возвращает старую версию C, а работает уже с новым объектом? :)))
                                                                        –1
                                                                        И то, что тут описано в целую статью, проверяется за пару минут и не требует таких неточных методов, как замеры времени выполнения кода.
                                                                          0
                                                                          Дали бы свою оценку, товарищ, чем кидаться…
                                                                          +1
                                                                          Писать код так, чтобы замедляться в 60, а не в 180 раз вполне имеет практический смысл.

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


                                                                          А что вы хотели при /Od против /O2?
                                                                            0
                                                                            Зря вы поместили картинку с результатами в начале статьи. Ответ на вопрос дали, дальше можно по идее не читать :).
                                                                              +1
                                                                              Изначально пост начали люто минусовать. :-( Видимо условный рефлекс на слово PVS-Studio. Решил сделать картинку, что пост будет о чем-то интересном. Дело сразу наладилось.
                                                                              0
                                                                              Можно было ещё посмотреть на ассемблерный выхлоп. И префиксная, и постфиксная реализация для целочисленных переменных без использования результата комилируются в машинную инструкцию inc, т.е. никакой разницы и быть не может.
                                                                              А оптимизировать дебаговую сборку иногда бывает очень сильно нужно: у меня был один проект (реалтайм), который в дебаге изначально вообще не работал, только после ручной оптимизации и включения inline стало хватать скорости.
                                                                                +1
                                                                                В критичных по производительности местах практически всегда итератор следует предпочесть индексации числу. Связано это с тем, что для векторов итератор становится обычным указателем, и в условиях нехватки регистров внутри вложенных циклов обращение к элементу идёт через итератор-указатель, а не через пару база+смещение, что даёт нам лишний свободный регистр и меньшее число операций.
                                                                                В реальной задаче (построение поверхности Безье по сетке значений) индексация итератором увеличила фреймрейт с 16 до 21 (в данном случае узким местом были как раз математические расчёты, а не вывод графики).
                                                                                А по поводу статьи я бы порекомендовал провести исследование не только вектора, где голые указатели, но ещё и для ассоциативных контейнеров с нелинейным обходом элементов (потому что производительность может уже не упереться в скорость памяти и кэша, как в случае с вектором).
                                                                                  +3
                                                                                  Вполне возможно, что вы делаете неправильные выводы. Всё сильно зависит от конкретного случая, от того какая информация доступна компилятору, как он справился с оптимизацией, а потом ещё и на более низком уровне — от логики процессора. В частности, совсем не обязательно что доступ по индексу компилятор будет представлять как базу+смещение, а не одним регистром аналогично указателю.
                                                                                    0
                                                                                    В конкретно моём случае я любое действие сверял с ассемблер-листингом оптимизированного кода, и произошло как раз то, о чём я говорил.
                                                                                    Компилятор действительно волен выбирать, как именно выполнять индексацию, но это не имеет большого значения, если в теле цикла производится мало операций. Если же там что-то вроде умножения вектора на матрицу или несколько различных простых операций с индексируемым элементом, то не всегда есть гарантия отсутствия alias'ов на содержимое вектора, и компилятору придётся сгенерировать код с базово-индексной адресацией. Если же программист уверен в отсутствии «коварных» мест, он может явно помочь компилятору с генерацией оптимизированного кода.
                                                                                      +1
                                                                                      В вашем конкретном случае это могло быть так, но вы же обобщаете, говоря «практически всегда». Но в целом согласен — чем больше информации (отсутствие побочных эффектов и прочее) программист предоставит компилятору, тем эффективнее может быть оптимизация. Не уверен, правда, что дело именно в alias'ах, это вроде не должно мешать если компилятору известно, что база не поменяется — в этом случае достаточно просто пересчитать относительные смещения в абсолютные.
                                                                                        –1
                                                                                        Так точно.

                                                                                        «Очень часто» — можно согласиться, наверное.

                                                                                        «Практически всегда» — нет, конечно, бывают случаи и бывают случаи.

                                                                                        Зачем вообще вектору итераторы отдельный непонятный вопрос.

                                                                                        Особенно настолько толковые, что 200x тормоза в дебаге ж)
                                                                                          0
                                                                                          Суть и назначение итераторов хорошо описаны у самого Страуструпа, а именно: итераторы нужны для того, чтобы унифицировать понятие контейнера, чтобы вне зависимости от конкретного вида контейнера можно было по нему пробежаться, имея пару итераторов. Механизм итераторов обеспечивает для контейнеров полиморфизм времени компиляции; без этого важного свойства было бы тяжело написать унифицированную версию, скажем, алгоритма for_each() и многих других. А так его можно написать всего в пару строк, и не нужно делать каких-то исключений для конкретных типов контейнеров.
                                                                                          Итераторы в дебаге медленные оттого, что в коде делаются проверки на каждый чих, чтобы некоторые баги можно было выловить в процессе написания кода и предварительного тестирования. А при /O2 и выше все проверки вырезаются, чтоы «даёт» 200-кратный «прирост».
                                                                                            0
                                                                                            Проверки не всегда вырезаются даже при /O2, в вижуал студии 2005/2008 по крайней мере — смотрите про _SECURE_SCL выше.
                                                                                            Кстати, если не писать обобщённых (templated) алгоритмов, то итераторы действительно менее удобно использовать, чем индексы, об этом насколько я помню упоминал в том числе и Александреску в его «Iterators must go». А использовать встроенные в STL алгоритмы без поддержки lambda как в C++0x — тоже то ещё счастье. Слишком медленно язык развивается, то что хотят добавить в C++0x должно было давно уже быть там, как только STL стал популярным :(
                                                                                              –1
                                                                                              Эта, книжку вслух мне зачитывать необязательно. Я картину мира представляю довольно хорошо, не одна реализация STL обследована, да и не один вектор написан, собственно.

                                                                                              Зачем вектору (!) именно итераторы, плохо понятно все равно. Внятный юзкейс, который требует (!) итераторов вектора не могу себе представить.

                                                                                              Впрочем польза от этого обсуждения уже похоже есть, а именно: в предыдущем комментарии число 200 считать числом 10.
                                                                                    –1
                                                                                    Пока я читал эту статью, я потратил времени в 10n больше, чем сэкономлю на оптимизации :)
                                                                                      +1
                                                                                      Андрей, я специально протестировал для других видов контейнеров для константных и неконстантных итераторов, постфиксный и префиксный итераторы. И результаты показывают, что разницы почти нет, кроме постфиксного ++ у константного итератора: std::list на 1-2% больше, std::map на 5-6% больше,.
                                                                                      Удивительные результаты показывает std::multimap — префиксный на 12-13% больше постфиксного! Неожиданно? Да!
                                                                                      Идем дальше: std::set показывает, что постфиксные++ для двух видов итераторов константный и некостантный на 15-16% и 10% дороже чем префиксный, соответственно. Для std::multiset постфиксный ++ константного итератора проигрывает на 2-3%, и для неконстантного, наоборот, префиксный проигрывает на 11%.

                                                                                      Но нельзя забывать, что помимо стандартных контейнорв, разработчики которых постарались на славу, и хвала писателям компиляторов, которые много что оптимизируют, остается некоторая ниша, где могут появиться деградация производительности. Где-то оно мало проявляется (map, set), а где-то может проявиться больше, если объект итератора будет сложным и объемным в памяти.
                                                                                      Как говорится, преждевременная оптимизация это зло.
                                                                                      Но большее зло писать код, который не говорит сам за себя, что оно делает, что составляет некоторую культуру написания кода. Там где нет нужды в постфиксном ++, стоит писать префиксный, что дает знание читающему чужой код понимание, для чего этот кусок был написан (просьба не сводить к простому примеру с for). Эт также важно, как и важно применять правильные *_cast вместо C-like кастинга, что дает понимание, что хотел сделать программист.

                                                                                      Да, с этой точки зрения в вашем продукте нет нужды делать такие проверки, и не потому, что в основных итераторах нет разницы, а в некоторых творятся чудеса. А потому, что культура кода вещь немного из другой области, хоть и может проверяться статическими анализаторами.
                                                                                        0
                                                                                        установка _SECURE_SCL в 0, affinity на то или иное ядро на разных прогонах немного снизил расхождения, но они не исчезли.
                                                                                        размер контейнеров = 10000 элементов (чтобы меньше влияли кешмисы и пейджфолты), 100000 прокруток прохода по контейнеру.

                                                                                        пример тяжелого итератора, где лучше писать префиксный: у меня есть код итерации слиянием по множеству отсортированных массивов уникальных элементов сразу, и итератор на каждом шаге дает перечень индексов идентичных элементов в различных массивах, и его копирование будет сложностью O(m) где m — ичсло массивов на входе.
                                                                                        0
                                                                                        хорошая статья
                                                                                        сам люблю читать Скот Майерса и стараюсь придерживаться его советов.
                                                                                          0
                                                                                          Вы тестировали на std::vector::iterator. Какой в этом большой смысл? Там итератор прост как три копейки.

                                                                                          А в шаблонном коде совершенно непредсказуемо с какими итераторами будет инстанцироваться шаблон, вполне возможно что с каким-нибудь decltype(a | join(b) | filter©)::iterator, для которого компилятор не соптимизирует код. Не проще ли просто привыкнуть писать префиксный инкремент там где его хватает? Неужели так некрасиво выглядят плюсики слева, нежели справа? Разве это война тупоконечников против остроконечников?
                                                                                            0
                                                                                            Я, например, вообще не парюсь на этот счёт: как привык ставить плюсики слева, так и ставлю.
                                                                                            0
                                                                                            Надо сказать, что ваши замеры доказывают главу «7.2.6 The Increment and Decrement Problem of Vector Iterators» из книги The C++ Standard Library: A Tutorial and Reference 1999 года выпуска.

                                                                                            Там говорится — «fact that vector iterators are typically implemented as ordinary pointers».

                                                                                            То есть для вектора итератор зависит от имплементации, и в общем случае может быть вырожден/оптимизирован в обычный указатель на тип.
                                                                                            В случае Debug однозначно используется класс (см. _HAS_ITERATOR_DEBUGGING || _SECURE_SCL) со всеми вытекающими накладными расходами.

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

                                                                                            Самое читаемое