Optimization 101: ordering conditions

One of the most basic truths about optimizing existing code is: there are no low hanging fruits. Your coworkers are not stupid, it’s not like you can just add some switch or line and code will magically run two times faster (at least not often). ‘Easiest’ way nowadays is probably some form of parallalization, but it’s not always possible. Usually, it’s more a series of mundane tweaks, day after day, shaving few cycles here, few there. I’ve been in situations where I was genuinely happy after gaining as little as 1.5ms (out of ~9ms, it was main object update loop, that’s been already after few optimization sessions in the course of 4-5 years, there really wasn’t much to get). Read also Pierre’s Novodex story for better idea of how it works. Condition order is one of those not-so-glamour aspects of optmization. It won’t give you much, but it can give you something, at least.

Basic idea is trivial: try to remember to order your conditions in increasing level of complexity. Exit as early as possible, exploit short circuiting (second one is usually less obvious). Consider the following example - we try to play a sound, which may not be present for all characters, it has a random chance of being played plus some other, more complicated conditions (like it may require a target in vicinity).

if (!HasVoice(voiceId)) // Easy test, the quickest one
    return;
if (Rand01() > ChanceToPlay(voiceId)) // A little bit more complicated
    return;
if (!EvaluateVoiceConditions(voiceId, additionalArgs))
    return;

If the voice has no chance to play this time, there’s no reason to evaluate more complex conditions, obviously. It’s the same with short circuiting. It doesn’t even have to be connected to amount of work done inside called functions, it’s about the cost of the call/test. Put inlined functions first, then normal ones, then virtual methods. Also, try to put conditions touching same regions of memory next to each other. Example:

if (!object->IsAlive() && object->IsPlayer())
{
    // do something for dead player object
}

Let’s assume IsAlive() is non-virtual function of Object class, IsPlayer() is a virtual method that’s overriden in Player class. If IsAlive() returns true (probably majority of cases), IsPlayer() will never be called (saving a virtual method call).

As mentioned - it’s not very flashy, it won’t make you a hero. It may give you 10 cycles per call. 10 cycles here, 10 cycles somewhere else, multiply by number of calls and suddenly it is a little bit more interesting.

Old comments

Jumpster 2010-05-18 23:04:48

@admin: “Reg: thatâ??s a good point, however my rule of thumb is that if condition is â??too likelyâ? (according to my arbitrary scale) to result in early exit (ie, body of the function does nothing in majority of cases), itâ??s better to refactor the code.”
Would you be so kind as to provide an example? I myself have always followed the same approach as Reg suggests; most likely to fail at the top for early exit (or an inverse if you will - the most likely to succeed at the top in switch() statements)…
JTK

admin 2010-05-19 03:47:20

The approach itself is OK, what I meant is that’s probably a bad sign if your function does nothing in 90% of cases (ie, exits early), unless it’s some kind of lazy evaluation case. You still need to be careful – consider first example, even assuming that EvaluateVoiceCondition results in early exit in majority of cases, it probably doesn’t make sense to put it as the first tested condition.

Justin Paver 2010-05-18 00:32:31

Pavel, I think that idea actually makes more sense if amount of players is not large. It saves one from having to traverse all non-player and living objects just to do some player logic. Also, if the majority of objects being traversed are not a player, you’d be paying the cost of calling the virtual IsPlayer() method on the majority of those objects.
W.r.t. to ordering conditions, another technique is to try to verify the statistics empirically by incrementing a unique counter every time a condition is hit. These tell one how often each paths would be taken under the data sets that one is using. One data set could be very different to another data set, and the performance of the code could vary dependening on which it is. One could also add counters to test for simultaneous rejection due to multiple conditions. eg.
If condition A is rejecting at 50% rate and B is rejecting at 40% rate. If counter for (A & B) is rejecting at rate close to either of those rates, one can likely eliminate one of the conditions and save the expense of evaluating it. Such simultaneous scenarios are infrequent though and less likely to benefit in savings.
Combined with the complexity metric, counters are quite valuable for figuring out which conditions will bring better performance gains when hoisted to the top.
Of course, once one has used such a heuristic to reorder conditions, one should verify it actually results in a performance gain too :)

admin 2010-05-18 01:04:42

@Pavel: that’s true, but at the end of the day it’s impossible to code without conditional instructions :). We should try to strive for the code flow to be as ‘linear’ as possible (no jumps), article is more about situations when there’s no choice. Examples given here are purely fictional, BTW.
@Justin: interesting idea, didn’t think of that.

Pavel Shevaev 2010-05-17 07:34:00

According to Mike Acton(insomniac games) the best optimization of conditions is not to have them at all :) I guess instead of “if (!object->IsAlive() && object->IsPlayer())” it’s much better to have an array of “dead player” objects(however, in this particular case it probably doesn’t make sense to do so since usually the amount of players is not large).

admin 2010-05-16 17:46:01

Reg: that’s a good point, however my rule of thumb is that if condition is “too likely” (according to my arbitrary scale) to result in early exit (ie, body of the function does nothing in majority of cases), it’s better to refactor the code. Plus, in many cases even evaluting the condition itself can be costly. In my first example, it probably never makes sense to move EvaluateVoiceCondition higher.
About the quality of code, maybe I’m just lucky, but it’s been a long time since I stumbled upon some really bad code that was culprit of low performance. Usually, it’s more of million of little inefficiences.

Reg 2010-05-16 13:05:59

Ordering conditions in increasing level of complexity is one possible criterion, but how about placing on the top the conditions that are most probable of evaluating to false and thus exiting early?
About low hanging fruits: It depends on who do you work with and the quality of code you optimize. You are very experienced so I’m sure you’ve seen many times the “WTF” kind of code where optimizations were obvious :)