Early out if statements

[albinopapa]

In an endeavor to find performance increasing code, one thing I wanted to look at was branching and to be more specific, using if statements to exit from a function early.

I've most often seen this technique in physics or ray-tracing algorithms ( both are basically the same really ), but I have seen this technique used outside of those domains.

To test my query, I am in fact using some collision detection code. I ran across an article that covers some collision algorithms, it's more of a tutorial really. Anyway, in the article, there is some example code for detecting align-axis bounding box collision or overlap.

Code: Select all

if( a.vmin.x > b.vmax.x or a.vmax.x < b.vmin.x ) return false;
if( a.vmin.y > b.vmax.y or a.vmax.y < b.vmin.y ) return false;
return true;

Now, I might brush this off as "tutorial code", but the article does bring up points throughout suggesting optimizations like instead of testing if the distance between two circles is less than the sum of their radii, test if the squared distance is less than the squared sum of their radii. Since no mention was made about this AABB overlap being efficient or not, I'm going to take it at face value that this is what the author actually uses. Anyway, I wanted to test this "early out" technique against the version chili shows for overlap between two rectangles, which is really an aligned-axis bounding box. In chili's version there is no if statements, just a return statement that returns the result of the overlap testing.

Code: Select all

	return
		( a.vmin.x < b.vmax.x ) && ( a.vmax.x < b.vmin.x ) &&
		( a.vmax.y < b.vmax.y ) && ( a.vmax.y < b.vmin.y );

No early out: 0.0036946
early out: 0.00467973
Test was run 3 times to get the average time using 1,000 rectangles.

Nice, chili's version seems to be 27% faster than the early out technique.

I haven't gotten to collision resolution or manifold creation for AABBxAABB so results may change when I get there.

Manifold usage is introduced when covering CirclexCircle collision, so the code is different. Just testing for overlap between two circles I couldn't think of a way to early out. You have two options, test the distance against the radius sum or squared distance against the squared radius sum. If you are just testing overlap, there is no reason to perform the square root operation, so I had to implement the rest of the manifold creation, giving me a reason to perform the square root. This way I can test which is more costly, the branching or the square root operation.

EARLY_OUT: Off
Total time taken: 0.00802269

EARLY_OUT: On
Total time taken: 0.00334720

Here we notice that using the squared version and exiting early, thus avoiding a call to sqrt, is about 139% faster. In this case, an early out is our best option. These tests were performed over 20 iterations as opposed to the 3 iterations from the RectF tests. While each test on types were different from each other, the two versions ( with and without early out ) were the same for each type ( circle x circle was the same for each version and rect x rect was the same for each version ).

So what's the point?
I don't really have one exactly. There are going to be different factors that you'll have to take into account when deciding on whether to use an early out.

In some cases, finishing the function if some condition is not met won't make sense. For instance, if the function relies on a connection to a server then definitely early out if the connection has been lost.

If the function is purely computational and there is not expensive math ops like sqrt, or trig ops like sin/cos/tan and their inverse variants, then you may want to try doing the entire function as if no errors occurred and just have it ( return result == exptected; ). Test it and see if it makes any difference.

One reason people do or prefer early out or multiple return statements is it leads to more readable code. If you have an if "tree", then it becomes more and more difficult to read and reason about the nature of the function:

Code: Select all

if( condition_1 )
{
    if( condition_2 )
    {
        if( condition_3 )
        {
            if( condition_4 )
            {
                // do something
                return 0;
            }
            else
            {
                return 1;
            }
        }
        else
        {
            return 1;
        }
    }
    else
    {
        return 1;
    }
}

When it could have been written as:

Code: Select all

    if( !condition_1 ) return 1;
    if( !condition_2 ) return 1;
    if( !condition_3 ) return 1;
    if( !condition_4 ) return 1;

    // do something
    return 0;

It all depends on the nature of the function.

To be fair, when I started creating this post, I wasn't thinking about all the different reasons for using early out or multiple return statements. I was solely focused on calculations or more specifically, collision detection. That being said, I've often read that you should reduce the amount of if statements in your code. Not only is it easier to read for you without all the branching, it's also easier on the CPU. So if you can get away with it and it is beneficial, do the entire calculation or entire function and have as few if statements as possible, but make sure you test it to see if you are getting the results you want both in terms of the resultant data and performance.

[albinopapa]

Okay, so I tested a fuller AABB collision test with 20 iterations like the Circle tests. There aren't any sqrt calls, but there are 4 branches, two for early out detection and two for determining values. The two branches used to exit the function early I can combine to make one return thus eliminating half of the branches, but keeping the branches that handle values.

Early out using all 4 branches: .0028
Removing early out branches: .016
Joining the two branches to 1: .0035

I need to probably do some more testing. I'm thinking that there aren't a lot of collisions in my random data. So in cases where nothing is colliding, early out is super quick, if everything is colliding, then the worst case is about 16 ms.

[chili]

yeah early out is going to be good if collisions are rare, the branch predictor will ensure that pipe flushes are rare as well

[albinopapa]

I'm finding that out. It's so difficult to think about when branching is appropriate and when it can be sidestepped.

In a recent CppCon video the speaker talked about using bit manipulation tricks to make the if statements less complicated and allowing the branch predictor to be more efficient at it's job. Branch mis-predictions can be costly, so I'm trying to figure out how and where I can reduce the number of 'if' statements and apparently early out is not one of those cases.