Free Heroes of might and magic 2 – open-source проект, в котором хочется участвовать

    Недавно в сети появилась новость о релизе новой версии проекта fheroes2. У нас в компании многие сотрудники являются поклонниками серии игр Heroes of Might and Magic, и естественно, мы не могли пройти мимо и в процессе ознакомления с проектом проверили его анализатором PVS-Studio.

    Знакомство с проектом

    Free Heroes of Might and Magic II – реализация игрового движка Heroes of Might and Magic II с открытым исходным кодом. Для того чтобы поиграть в обновлённую версию, нужна оригинальная Heroes of Might and Magic II или хотя бы её демоверсия, которую можно скачать при помощи распространяемого вместе с исходным кодом скрипта (в зависимости от операционной системы нужно выбрать соответствующую версию).

    После успешной сборки проекта я решил немного поностальгировать и запустить игру. Для удобства я немного отредактировал файл fheroes2.cfg, проставив параметры:

    heroes speed = 10
    ai speed = 10
    battle speed = 10
    

    А также выставил своё разрешение в параметре videomode.

    После всех манипуляций я запустил игру и увидел знакомый главный экран:

    Если вы проставили не своё разрешение экрана или не хотите заморачиваться с конфигом, развернуть игру в полноэкранный режим можно при помощи клавиши f4.

    Далее, я зашёл в standard game. Так как я выкачал демоверсию, доступна лишь одна карта – Broken Alliance.

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

    Последней доступной версией проекта на момент написания статьи была 0.8.4, в ней была улучшена работа игры на низкопроизводительных устройствах, добавлено большое количество геймплейных и косметических нововведений, о которых можно почитать здесь. Также моё внимание привлекла надпись: "устранено более ста багов по сравнению с предыдущей версией". Что ж, видимо, разработчики серьёзно следят за качеством исходного кода и, как видно по странице проекта на GitHub, уже используют статический анализатор Sonar Cxx на постоянной основе, а иногда проверяют проект анализатором Cppcheck.

    Мне кажется, что, если астрологи объявят неделю статического анализа и разработчики добавят к списку своих утилит PVS-Studio, багов станет ещё меньше. Давайте же убедимся в этом, рассмотрев несколько найденных мной с его помощью проблемных фрагментов кода. Тем более что открытые проекты могут использовать анализатор PVS-Studio бесплатно.

    Микрооптимизации

    Начнём для разнообразия не с ошибок, а с фрагментов кода, которые можно немножко оптимизировать. Немножко потому, что настоящую оптимизацию нужно выполнять, используя профилировщики. Статические анализаторы не имеют данных, как часто выполняется тот или иной код, и поэтому не способны показать, где действительно узкое место. Поэтому мы, кстати, называем "микрооптимизациями" набор предупреждений PVS-Studio, касающихся увеличения скорости работы.

    Мы не рассчитываем, что описанное здесь поможет хоть сколько-то заметно ускорить работу игры. Просто хотелось уделить внимание этому набору диагностик, который обычно не освещается в наших серийных статьях про проверки открытых проектов и поэтому остаётся в тени.

    Предупреждение N1

    V823 Decreased performance. Object may be created in-place in the 'list' container. Consider replacing methods: 'push_back' -> 'emplace_back'. tools.cpp 231

    std::list<std::string> StringSplit( const std::string & str, ....)
    {
      std::list<std::string> list;
      size_t pos1 = 0;
      size_t pos2 = std::string::npos;
      
      while (   pos1 < str.size()
             && std::string::npos != (pos2 = str.find(sep, pos1))) 
      {
        list.push_back( str.substr( pos1, pos2 - pos1 ) );
        pos1 = pos2 + sep.size();
      }
      ....
    }

    Анализатор подсказывает, что в данном случае было бы более эффективно использовать метод emplace_back. В общем случае, простая замена метода push_back на emplace_back не даст ускорения производительности, если аргумент является rvalue. Однако, в нашем случае у класса std::string есть конструктор, создающий объект из двух итераторов (см. конструктор N6). И именно он позволит нам устранить лишний вызов конструктора перемещения в сочетании с emplace_back:

    std::list<std::string> StringSplit( const std::string & str, ....)
    {
      std::list<std::string> list;
      size_t pos1 = 0;
      size_t pos2 = std::string::npos;
      
      while (   pos1 < str.size()
             && std::string::npos != (pos2 = str.find(sep, pos1))) 
      {
        list.emplace_back(str.begin() + pos1, str.begin() + pos2);
        pos1 = pos2 + sep.size();
      }
      ....
    }

    Это полезно для улучшения производительности, так как данная операция выполняется в цикле. Хочется отметить, что данное предупреждение важно, ведь в ходе проверки было обнаружено более ста подобных сообщений. Вот некоторые из них:

    • V823 Decreased performance. Object may be created in-place in the 'loop_sounds' container. Consider replacing methods: 'push_back' -> 'emplace_back'. agg.cpp 461

    • V823 Decreased performance. Object may be created in-place in the 'projectileOffset' container. Consider replacing methods: 'push_back' -> 'emplace_back'. bin_info.cpp 183

    • V823 Decreased performance. Object may be created in-place in the 'actions' container. Consider replacing methods: 'push_back' -> 'emplace_back'. ai_normal_battle.cpp 264

    • V823 Decreased performance. Object may be created in-place in the 'actions' container. Consider replacing methods: 'push_back' -> 'emplace_back'. ai_normal_battle.cpp 288

    • V823 Decreased performance. Object may be created in-place in the 'actions' container. Consider replacing methods: 'push_back' -> 'emplace_back'. ai_normal_battle.cpp 433

    • и так далее

    Предупреждение N2

    V814 Decreased performance. The 'strlen' function was called multiple times inside the body of a loop. tools.cpp 216

    void StringReplace( std::string & dst, 
                        const char * pred, 
                        const std::string & src )
    {
      size_t pos = std::string::npos;
      while ( std::string::npos != ( pos = dst.find( pred ) ) )
      {
        dst.replace( pos, std::strlen( pred ), src );
      }
    }
    

    В данном случае функция strlen вызывается на каждой итерации цикла, при этом размер строки pred не меняется. Код можно упростить самым банальным образом, вынеся вычисление длины строки за пределы цикла и обозначив его в виде константы.

    void StringReplace( std::string & dst,
                        const char * pred, 
                        const std::string & src )
    {
      size_t pos = std::string::npos;
      const size_t predSize = std::strlen( pred);
      while ( std::string::npos != ( pos = dst.find( pred ) ) )
      {
        dst.replace( pos, predSize, src );
      }
    }
    

    Предупреждение N3

    V827 Maximum size of the 'optionAreas' vector is known at compile time. Consider pre-allocating it by calling optionAreas.reserve(6) battle_dialogs.cpp 217

    void Battle::DialogBattleSettings( .... )
    {
      std::vector optionAreas;
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 36, 
                                             pos_rt.y + 47, 
                                             panelWidth, 
                                             panelHeight ) ); 
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 128, 
                                             pos_rt.y + 47, 
                                             panelWidth, 
                                             panelHeight ) ); 
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 220, 
                                             pos_rt.y + 47, 
                                             panelWidth, 
                                             panelHeight ) ); 
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 36, 
                                             pos_rt.y + 157, 
                                             panelWidth, 
                                             panelHeight ) ); 
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 128, 
                                             pos_rt.y + 157, 
                                             panelWidth, 
                                             panelHeight ) );
      optionAreas.push_back( fheroes2::Rect( pos_rt.x + 220, 
                                             pos_rt.y + 157, 
                                             panelWidth, 
                                             panelHeight ) );
    }
    

    Анализатор обнаружил std::vector, максимальный размер которого известен на этапе компиляции. Перед заполнением контейнера гораздо эффективнее было бы вызвать:

    optionAreas.reserve(6);
    

    В этом случае вызовы push_back не приведут к реаллокации внутреннего буфера в векторе и перемещению элементов в новую область памяти. Ну или, как альтернатива, этот код можно переписать с использованием std::array.

    Предупреждения N4.0, 4.1...4.7

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (armyBar)' check can be removed. kingdom_overview.cpp 62

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (artifactsBar)' check can be removed. kingdom_overview.cpp 64

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (secskillsBar)' check can be removed. kingdom_overview.cpp 66

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (primskillsBar)' check can be removed. kingdom_overview.cpp 68

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (armyBarGuard)' check can be removed. kingdom_overview.cpp 279

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (armyBarGuest)' check can be removed. kingdom_overview.cpp 281

    • V809 Verifying that a pointer value is not NULL is not required. The 'if (dwellingsBar)' check can be removed. kingdom_overview.cpp 283

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

    void Clear( void )
    {
      if ( armyBar )
        delete armyBar;
      if ( artifactsBar )
        delete artifactsBar;
      if ( secskillsBar )
        delete secskillsBar;
      if ( primskillsBar )
        delete primskillsBar;
    }
    
    void Clear( void )
    {
      if ( armyBarGuard )
        delete armyBarGuard;
      if ( armyBarGuest )
        delete armyBarGuest;
      if ( dwellingsBar )
        delete dwellingsBar;
    }
    

    В данном случае можно произвести рефакторинг кода, убрав из функций все проверки на нулевые указатели, ведь оператор delete корректно его обрабатывает. Возможно, это и не даст выигрыша в производительности (компилятор сам уберёт проверки), однако упростит код и сделает его более читабельным.

    General Analysis

    Предупреждение N5

    На данный фрагмент кода анализатор выдал 2 предупреждения:

    • V654 The condition 'i < originalPalette.size()' of loop is always false. battle_interface.cpp 3689

    • V621 Consider inspecting the 'for' operator. It's possible that the loop will be executed incorrectly or won't be executed at all. battle_interface.cpp 3689

    void Battle::Interface::RedrawActionBloodLustSpell( Unit & target )
    {
      std::vector > originalPalette;
      if ( target.Modes( SP_STONE ) ) 
      {
        originalPalette.push_back( PAL::GetPalette( PAL::GRAY ) );
      }
      else if ( target.Modes( CAP_MIRRORIMAGE ) ) 
      {
        originalPalette.push_back( PAL::GetPalette( PAL::MIRROR_IMAGE ) );
      }
      if ( !originalPalette.empty() ) 
      {
        for ( size_t i = 1; i < originalPalette.size(); ++i )
        {
          originalPalette[0] = PAL::CombinePalettes( originalPalette[0],
                                                     originalPalette[i] );
        }
        fheroes2::ApplyPalette( unitSprite, originalPalette[0] );
      }
    ....
    }
    

    Как мы видим, здесь программист ошибся в алгоритме. По ходу выполнения функции вектор originalPalette увеличивается в размере на единицу или остаётся пустым. В if находящийся над циклом, мы войдём, только когда originalPalette.size() равен единице. Соответственно, переменная i никогда не будет меньше размера вектора, и из-за этого мы получаем фрагмент недостижимого кода.

    Предупреждение N6

    V547 Expression 'palette.empty()' is always true. image_tool.cpp 32

    const std::vector PALPAlette()
    {
      std::vector palette;
      if (palette.empty()) //<=
      {
        palette.resize( 256 * 3 );
        for ( size_t i = 0; i < palette.size(); ++i ) 
        {
          palette[i] = kb_pal[i] << 2;
        }
      }
      return palette;
    }
    

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

    Предупреждение N7

    V668 There is no sense in testing the 'listlog' pointer against null, as the memory was allocated using the 'new' operator. The exception will be generated in the case of memory allocation error. battle_interface.cpp 986

    Battle::Interface::Interface(....)
    {
      ....
      listlog = new StatusListBox();
      ....
    
      if ( listlog )
      {
        ....
      }
      ....
    }
    

    Анализатор обнаружил ситуацию, когда значение указателя, возвращаемого оператором new, сравнивается с нулём. Как правило, это значит, что программа при невозможности выделить память будет вести себя не так, как ожидает программист. Если оператор new не смог выделить память, то, согласно стандарту языка С++, генерируется исключение std::bad_alloc() Значит, данная проверка избыточна.

    Также было обнаружено ещё два подобных срабатывания:

    • V668 There is no sense in testing the 'elem' pointer against null, as the memory was allocated using the 'new' operator. The exception will be generated in the case of memory allocation error. battle_arena.cpp 1079

    • V668 There is no sense in testing the 'image' pointer against null, as the memory was allocated using the 'new' operator. The exception will be generated in the case of memory allocation error. battle_arena.cpp 1095

    Предупреждение N8

    V595 The '_currentUnit' pointer was utilized before it was verified against nullptr. Check lines: 2336, 2358. battle_interface.cpp 2336

    void Battle::Interface::MouseLeftClickBoardAction( .... )
    {
      ....
      themes = GetSwordCursorDirection( Board::GetDirection( index, 
                                      _currentUnit->GetHeadIndex()));
      ....
      if ( _currentUnit )
      {
        ....
      }
      ....
    }
    

    Указатель _currentUnit сначала разыменовывается, а потом проверяется на NULL. Это может означать одну из двух очевидных вещей: возникнет неопределённое поведение, если указатель действительно нулевой, или указатель никогда не может иметь нулевое значение, и программа всегда работает корректно. Если подразумевается первый вариант, то проверку стоит произвести до разыменования. Во втором варианте можно опустить избыточную проверку.

    Заключение

    Как по мне, проект сейчас очень близок к оригинальной версии игры. Код проекта довольно качественный, что неудивительно, ведь разработчики используют несколько статических анализаторов. Однако нет пределов совершенству, и ещё меньшего количества багов можно добиться, добавив к используемым решениям PVS-Studio, который, как уже упоминалась ранее, бесплатен для open-source проектов.

    В заключение хочется сказать разработчикам спасибо, движок действительно крутой. Если же вы ищете хороший и интересный open-source проект, в котором можно поучаствовать, то fheroes2 – то, что вам нужно.

    Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Vladislav Stolyarov. Free Heroes of Might and Magic II: Open-Source Project that You Want to Be Part of.

    PVS-Studio
    Статический анализ кода для C, C++, C# и Java

    Комментарии 10

      0
      Регулярно читаю ваши статьи, спасибо.

      Позвольте спросить, а вот в функции очистки Clear, не следует ли ещё советовать присваивать NULL / nullptr? Я просто почитал поверхностно этот тред на SO, и поэтому спрашиваю вас?

      Я сейчас посмотрел код в репозитории, этот блок переписали на smart pointers. Поэтому рекомендация по поводу delete, возможно уже устарела, но всё равно интересно ваше мнение.
        0
        Здравствуйте, с точки зрения человека, читающего код — это безусловно полезная практика, как минимум может защитить от двойного освобождения памяти (выстрел в ногу, защита). Но по факту такое обнуление компилятор, скорее всего, оптимизирует. А, вообще, я бы порекомендовал пользоваться умными указателми с явной семантикой владения и выделения памяти.
        0
        Спасибо за статью!

        Извините, а рекомендация анализатора N1 точно поможет хоть что-то улучшить? По идее, для вызова конструкторов копирования/перемещения emplace_back и push_back ведут себя практически эквивалентно.

        Функция substr вернёт rvalue, push_back практически у всех контейнеров имеет перегрузку, принимающую правостороннюю ссылку, а значит, в контейнер вставится объект всего лишь с двумя вызовами конструктора (внутри substr, и move-конструктор при запихивании объекта в список).

        Ну а emplace_back примет аргумент по универсальной ссылке, которая так же преобразуется в rvalue reference, и явно вызовет конструктор копирования с этой ссылкой. То есть опять конструктор внутри substr и move-конструктор.

        Попробовал проверить на вот таком вот коде, моё предположение вроде как подтверждается.

        С другой стороны, если в коде из предложения N3 optionAreas — это std::vector<fheroes2::Rect>, то здесь emplace_back как раз-таки не помешает, поскольку укоротит код, и позволит действительно создать подобъекты внутри вектора, а не копировать их снаружи.

        В код самой игры лезть времени, к сожалению, не было, поэтому контекст не учитывал.
          0
          Спасибо за замечание, вы действительно правы, просто замена push_back на emplace_back не даст выигрыша в производительности и по моему описанию предупреждения было не особо понятно что я имел в виду. Более подробно расписал пример N1.
            0
            Также, если не хочется создавать строчку через итераторы, как я в примере, то можно позвать ещё одну перегрузку и написать, так:

            list.emplace_back(str, pos1, pos2 - pos1);
            0

            В предупреждении 6, кстати, вероятно раньше вектор был статической переменной и проверкой на пустоту проверяли, нужно ли инициализировать палитру или она уже инициализирована

              0
              Можно, на будущее, попросить размещать General Analysis до блока с микрооптимизациями?
              Может я не прав, но читать основные предупреждения полезнее и хотелось бы их видеть в начале статьи, а не в конце.
                0
                Спасибо, учту
                0
                Эх, помню пришлось код править на паскале за одним… типапрограммистомсдипломом, где были два поиску данных в файле, один из которых возвращал код и десятка символов, второй (сразу же после первого) возвращал таким же поиском в цикле допустим первые 7 цифр, после чего для третьей переменной он всё таки просто взял из результата поиска первых 4 цифры, не прогоняя цикл.
                Плюс ко всему циклы, даже получив результат, не прекращали работу, а так и перебирали весь текстовый файл с жесткого диска до конца. И эта процедура запускалась десяток раз.

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

                Так что всё таки интересно, насколько микрооптимизации из статьи способны повлиять на что-либо)
                  +1

                  Захотелось сразу же поиграть.

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

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