5
\$\begingroup\$

I need to improve the efficiency of my program and, using the profiler, have narrowed the problem down to 2 key areas, but I am having trouble coming up with ways to make the program run better.

Based on my profiler's report, it seems to be telling me that my if functions are inefficient. Whats a better way to achieve a better result?

Character* FindAttackTarget() const
        {
            float weakestHp = FLT_MAX;
            Character* weakestEnemy = nullptr;
            uint64_t weakestCharId = INT64_MAX;

            //Only attack characters that are within attack range
            auto& gameChars = m_pGame->m_gameCharacters;


            for (size_t i = 0; i < gameChars.size(); ++i)
            {
                auto& c = gameChars[i];
                if (Location.Dist(c.GetLocation()) <= AttackRange &&
                    c.HP > 0 &&
                    c.Team != Team)
                {
                    //We want the weakest with the lowest ID number - this keeps consistent results when re-playing the same part of the game (eg. after a load game)
                    if (c.HP < weakestHp || (c.HP == weakestHp && c.ID < weakestCharId))
                    {
                        weakestEnemy = &gameChars[i];
                        weakestHp = c.HP;
                        weakestCharId = c.ID;
                    }
                }
            }

            return weakestEnemy;
        }
\$\endgroup\$
  • \$\begingroup\$ Which lines are the ones being flagged by the profiler as slow? \$\endgroup\$ – 1201ProgramAlarm Apr 18 at 4:58
  • \$\begingroup\$ Are there many characters? And are few of them in range? \$\endgroup\$ – Deduplicator Apr 19 at 11:54
  • \$\begingroup\$ A Note on Naming FindAttackTarget implies it's finding a target to attack, which it does. But the name fails to deliver any of the relevant information that the function is retrieving the one with the lowest HP or the distance factor. One might improve this with something like FindLowestHealthTarget. \$\endgroup\$ – Shelby115 Apr 19 at 19:07
8
\$\begingroup\$

The tests c.HP > 0 and c.Team != Team are probably blazingly fast tests. Location.Dist(c.GetLocation()) <= AttackRange probably involves the square-root of the sum of the squares of the difference of coordinates in two or three dimensions. Plus, GetLocation() may involve memory allocation and/or copying constructors. It is by far the slowest test, yet you are testing it first! Take advantage of the short-circuit logical and operators by reordering the tests so the fastest tests are done first, so the slowest test may not even need to be executed, resulting in faster execution.

Since all conditions must pass before you update weakestEnemy, you could even test whether or not the target passes the “weakest with lowest ID” test before checking the attack range.

Bonus: the square-root can be avoided; simply compute the square distance, and compare against the \$AttackRange^2\$ (computed outside of the loop) for another speed gain.

\$\endgroup\$
  • \$\begingroup\$ I believe you're on the right track but could expand and systematize your answer: for instance, @Atazir could have gameChars partitioned between enemy and the rest, then have the enemy partition sorted by strength, and last find the first enemy in range: the costly operation is performed on the least number of elements. \$\endgroup\$ – papagaga Apr 18 at 6:08
  • \$\begingroup\$ @papagaga Partitioning is a great idea; not so sure about the sorting. Perhaps it would be better if you expanded and defended these ideas in your own answer. \$\endgroup\$ – AJNeufeld Apr 18 at 13:29
2
\$\begingroup\$

The most obvious target for improvement is the outer loop:

Currently, you loop over all characters. If there are few characters, that's fine. If there are many, it's unconscionable.

Consider dividing your play-area into a grid, and adding a std::unordered_multimap to find all characters in a cell. Depending on the range and your cell-size, you won't have to search too many cells, and they won't have that many characters each.

\$\endgroup\$
2
\$\begingroup\$

Since you tagged c++, we should make use of C++ features, and not pretend c++ being c with classes.

No raw loops (see Sean Parent's talk on C++ Seasoning)

auto& c = gameChars[i];
if (Location.Dist(c.GetLocation()) <= AttackRange &&
                  c.HP > 0 &&
                  c.Team != Team)
{
    //We want the weakest with the lowest ID number - this keeps consistent results when re-playing the same part of the game (eg. after a load game)
    if (c.HP < weakestHp || (c.HP == weakestHp && c.ID < weakestCharId))
    {
        weakestEnemy = &gameChars[i];
        weakestHp = c.HP;
        weakestCharId = c.ID;
    }
}

The body of the for loop is basically finding the minimum element in a range of Characters, where the range is represented by Characters, which satisfy a pre-condition. There is already a function for that in the STL called std::min_element.

In order to use std::min_element you only have to provide a comparison functor or a pre-define a comparison function for Character, e.g.

bool operator<(const Character& lhs, const Character& rhs)
{
    return lhs.HP < rhs.HP || (lhs.HP == rhs.HP && lhs.ID < rhs.ID);
}

Now considering std::min_element and including the pre-check, we can rewrite FindAttackTarget to:

Character* FindAttackTarget() const
{
    auto& gameChars = m_pGame->m_gameCharacters;
    auto min_it = std::min_element(gameChars.begin(), gameChars.end(), [&](auto& lhs, auto& rhs) {
        // also changed the order of evaluation since Location.Dist() is most likely the slowest to evaluate
        if(lhs.HP > 0 && lhs.Team != Team && Location.Dist(lhs.GetLocation()) <= AttackRange)
        {
            return lhs < rhs;
        }
        return false;
    }));
    if(min_it == gameChars.end()) // no target found
        return nullptr;
    return &(*min_it);
}

Et voila, no raw loops, only using STL algorithms. Now everyone can reason about your program without having to worry about any loop shenanigans you might have mixed up.

From here on, there can only be one bottleneck, and that is the Location.Dist() function as @AJNeufeld already mentioned.

Addon: range-v3

With the range-v3 library, which will be included in c++20, you can pre-filter your attackable targets like this:

bool isAttackable(const Character& c) {
  return c.HP > 0 && c.Team != Team && Location.Dist(c.GetLocation()) <= AttackRange;
}

auto attackableChars = gameChars | ranges::view::filter(isAttackable);

resulting in code for FindAttackTarget:

Character* FindAttackTarget() const {
    auto attackableChars = m_pGame->m_gameCharacters | ranges::view::filter(isAttackable);
    if(attackableChars.empty()) // no target found
        return nullptr;
    return &(*std::min_element(attackableChars.begin(), attackableChars.end()));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.