game mechanics code optimization

Everything about development and the OpenMW source code.
Post Reply
crassell
Posts: 49
Joined: 26 Aug 2017, 21:10
Github profile: https://github.com/crussell187

game mechanics code optimization

Post by crassell » 07 Sep 2017, 03:12

I'm a new developer and I know one of the main tenants of optimization is stay away from premature optimization, but I do notice some basic design patterns that are causing me to think even implementation code i'm adding is potentially slowing down mainline code. I hope what you find here is constructive criticism only.

For instance, I've been working on third person over the shoulder archery which requires me to stop head tracking updates for the player only when i'm in third person ranged aiming.

The code before I touched it:
for (PtrActorMap::iterator it(mActors.begin()); it != mActors.end(); ++it)
{
if (it->first == iter->first)
continue;
updateHeadTracking(iter->first, it->first, headTrackTarget, sqrHeadTrackDistance);
}
iter->second->getCharacterController()->setHeadTrackTarget(headTrackTarget);
The code after I touched it:
if (!((iter->first == player) && MWBase::Environment::get().getWorld()->getPlayer().getThirdPersonOverShoulderRanged()))
{
for (PtrActorMap::iterator it(mActors.begin()); it != mActors.end(); ++it)
{
if (it->first == iter->first)
continue;
updateHeadTracking(iter->first, it->first, headTrackTarget, sqrHeadTrackDistance);
}
}
iter->second->getCharacterController()->setHeadTrackTarget(headTrackTarget);
Essentially for every actor on screen, I will constantly check the third person ranged flag and if my current iteration of actors is the player. This one check may not cost much depending on the frequency of update of head tracking, actor count, etc., but I see if(ptr == player) checks sprinkled across both actors.cpp and character.cpp many of which are loops where under various conditions, the player is ignored or perhaps does something extra.

For the example above, adding general accessors to the map from outside and removing the player from the map would save the check altogether. For if checks where the player does something extra we may need to see if we can gather the work and amortize the check once.

Also, i'm not sure if vectors were looked into for all of these loop lists. Might improve on cache locality as well but again, need to profile first :)

User avatar
psi29a
Posts: 3432
Joined: 29 Sep 2011, 10:13
Github profile: https://github.com/psi29a/
Contact:

Re: game mechanics code optimization

Post by psi29a » 07 Sep 2017, 08:33

Usually premature optimizations usually are more specific 'hacks' that are harder to read and are avoided at the expense of maintainability.

However, if you believe that your optimization is worthwhile, is easily understood and you can demonstrate the performance gain (something tangable, even if it is printing and counting cout statements over a timestamp), then I say create the PR so that we can see if travis (gcc/clang) and appveyor (msvc) agrees. You'll also have a more technical discussion on github which is easier to reference code there.

The fact that you are putting an if before a loop saves us a needless loop iteration with many possible ifs is a good thing in my book.

User avatar
Thunderforge
Posts: 154
Joined: 06 Jun 2017, 05:57
Github profile: https://github.com/Thunderforge

Re: game mechanics code optimization

Post by Thunderforge » 07 Sep 2017, 19:52

Agreed, if you have an improvent, and especially if you can prove that it provides tangible optimizations, then go ahead and make a PR.

Chris
Posts: 1286
Joined: 04 Sep 2011, 08:33

Re: game mechanics code optimization

Post by Chris » 07 Sep 2017, 20:42

psi29a wrote:
07 Sep 2017, 08:33
The fact that you are putting an if before a loop saves us a needless loop iteration with many possible ifs is a good thing in my book.
That's actually indicative of a design flaw. If you find yourself doing something like

Code: Select all

for(auto &i : my_list)
{
    if(i != something || i.someflag)
        continue;
    do_stuff(i);
}
// or
for(auto &i : my_list)
{
    if(i.somevar == something)
        do_something(i);
    else if(i.somevar == something_else)
        do_something_else(i);
    ...
}
that means the list isn't sorted correctly for what you want to do to it. If a list is multi-purpose, with different purposes using different entries, it may even be better to have separate lists (and don't be fooled by virtual functions; they're basically just switch statements in disguise). These days, CPUs are orders of magnitude faster than memory, so the less memory you need when doing the work you need to do, the better (the more compact your data is, the fewer entries you need to skip over, the better). There can be more bookkeeping, but your CPU can spare the cycles if they'd otherwise be burned while waiting for memory.

crassell
Posts: 49
Joined: 26 Aug 2017, 21:10
Github profile: https://github.com/crussell187

Re: game mechanics code optimization

Post by crassell » 07 Sep 2017, 23:23

that means the list isn't sorted correctly for what you want to do to it. If a list is multi-purpose, with different purposes using different entries, it may even be better to have separate lists (and don't be fooled by virtual functions; they're basically just switch statements in disguise).
I didn't even want to mention virtual functions for this :) . They are essentially trading explicit branch prediction through an if or switch for implicit branch/branch target prediction with vtable lookups. After looking at the loop in question it is as you said a multi-purpose list (processes the same loop for head tracking, ai updates, etc.) so my initial recommendation wouldn't work. Like you said, multiple lists might help rather than one monolithic all actors list. Cheaper branching might also help as although you may predict well, you still have to execute and retire all of these useless instructions getting to the result of a condition verifying you took the right path.

Anyways, maybe the forum is not a place to discuss. Is there a useful online code review and comment tool? I might just profile code and then do some code audits on the side as I see problems. If there was a place where I could comment on various lines throughout the source, it may be helpful to communicate problem areas that we can collaborate on.

User avatar
psi29a
Posts: 3432
Joined: 29 Sep 2011, 10:13
Github profile: https://github.com/psi29a/
Contact:

Re: game mechanics code optimization

Post by psi29a » 08 Sep 2017, 06:56

crassell wrote:
07 Sep 2017, 23:23
Anyways, maybe the forum is not a place to discuss. Is there a useful online code review and comment tool? I might just profile code and then do some code audits on the side as I see problems. If there was a place where I could comment on various lines throughout the source, it may be helpful to communicate problem areas that we can collaborate on.
The forums is great for a group discussion, but if you want code review, comments on the code itself, code highlighting and the whole thing... github's PR is best for that. :)

crassell
Posts: 49
Joined: 26 Aug 2017, 21:10
Github profile: https://github.com/crussell187

Re: game mechanics code optimization

Post by crassell » 08 Sep 2017, 14:51

I looked into that but unfortunately the PR is for a proposed changeset. What would be nice is to review an entire file / set of files from top to bottom. A large code audit would be very useful in case massive code re-factoring is warranted. I think I saw some hints at how you could fake this on github through a pull request but this isn't natively supported. This might also allow some of the more experienced coders who don't have the time to fix but do have the time to review to re-architect the design of a portion of the engine and describe it for other developers to do the work.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest