Finding the Closest Enemy

We have been looking at temporary objects and the effect they can have on the performance of an application. As an example I offered a function that can tell the AI of a game which enemy is located closest to the player from a list that was provided as a function argument.

Refer to the previous article for the initial definition of the following function:

Enemy FindClosest(list<Enemy> enemies, Player player);

The conclusion was that it is much better to return a reference to an object than it is to return that object by value. Likewise it is much better to pass a function parameter by reference than it is to pass it by value. We actually have to apply this rule to this function before we can return a reference to an enemy.

By default, function parameters are passed by value. This means that the compiler creates a copy of the original object that was passed to the function and introduces the copy to the function as its parameter. The easiest way to visualize this is to use the MyClass class from the previous article and try the following test code:

void ByValue(MyClass obj) {
 (void)printf(“ByValue called..\n”);
}

/* in main() */
MyClass obj(“myObject”);
(void)printf(“Calling ‘ByValue’\n”);
ByValue(obj);

Clearly we can see the copy constructor being called to copy ‘myObject’ into the function parameter ‘obj’ in order to expose it to the function ‘ByValue’.

myObject - Constructor called.
Calling 'ByValue'
unnamed object - Copy Constructor called.
ByValue called..
unnamed object - Destructor called.
myObject - Destructor called.

We know that constructors (whether they are copy constructors or not), assignment operators and destructors can be costly operations.

Let's see what happens when we pass ‘MyClass’ by reference to the function:

void ByReference(MyClass &obj) {
 (void)printf(“ByReference called..\n”);
}

/* in main() */
MyClass obj(“myObject”);
(void)printf(“Calling ‘ByReference’\n”);

No copy constructors were called… most excellent!

Calling 'ByReference'
ByReference called..

Just like returning an object by reference, passing one by reference to a function allows you to keep working with the object itself, instead of instanced copies. This is much more efficient, since no new objects have to be created nor destroyed.

The only time it is less efficient to pass a reference instead of a value is when you are working with primitive values like integers, floats, booleans, and so on. In these cases a reference causes unnecessary overhead. References are almost always implemented like pointers; so passing a primitive value directly is more efficient than passing the address to that value.

When we pass a function argument by reference, the function is allowed to manipulate and make changes to the object being referenced. Some would even argue that for this very reason it is safer to pass function arguments by value when you want to make sure the function doesn’t make any alterations to them. I prefer to use constant references instead.

By passing a const reference to a function, you forbid the function to make any changes to the object via that reference.  Now we can make our first alteration to the FindClosest function:

Enemy const& FindClosest(list<Enemy> const &enemies,
     Player const &player) {
   assert (!enemies.empty()); 

      list<Enemy>::const_iterator closest;
      float min_sqdistance = FLT_MAX;
     
      list<Enemy>::const_iterator nmeIt;
      for (nmeIt=enemies.begin(); nmeIt!=enemies.end(); nmeIt++)
      {
       Vector3 nme2ply=player.GetPos() – nmeIt->GetPos();
       float sqdist=nme2ply.squaredLength();
       if (sqdist < min_sqdistance)
       {
        closest=nmeIt;
        min_sqdistance=sqdist;
       }
      }
return *closest;
         }

This alteration saves the need to construct an Enemy object local to the function body, and also the need to construct a temporary object to carry the result over to the caller.

Now let’s take a better look at how we’d use this function:

Enemy activeEnemy = FindClosest(enemyList, player);

The first and simplest optimization that comes to mind is the application of a copy constructor. With the statement above, an object must be created by calling its constructor (first call), after which an object is assigned to it by calling its assignment operator (second call). If a copy constructor is used, only one call to that copy constructor has to be made:

Enemy activeEnemy( FindClosest(enemyList, player) );

Compilers can optimize this statement by replacing the call to the constructor and assignment operator with that of the copy constructor… but there are no guarantees.

Instead of copying the data of the returned enemy into another Enemy object, we could use the const reference the function is returning:

Enemy const &activeEnemy = FindClosest(enemyList, player);

The obvious downside of a const reference is that we cannot make changes to the referenced object, and cannot use any of its functions unless they are declared const.

If we need to change the state of an enemy, we will have to return a non-const reference. To be able to return a non-const reference, we’ll have to pass a non-const reference to the enemy list to the function as well. The reference to the player object can remain const since we don’t expect a function that works with enemies to make changes to the player object.

Finally, here is a function declaration that is usable:

Enemy& FindClosest(list<Enemy> &enemies, Player const &player);

The enemy list is no longer const, so we can replace the const_iterators in the function body with regular iterators again.

By now I’d expect you don’t want to pass function arguments by value anymore unless they are primitive values. In case you are still hesitating, let's look at how passing by value can create a problem named ‘object slicing’. Then if you are convinced that const references are your salvation, stay alert, because there are situations where they perform as poorly as objects that are passed by value.

Things are never easy, you just have to make sure you know what you are doing… all the time.

 [slīs]

A thin broad piece cut from a larger object.

One of the dangers of passing an object by value is that the object might be sliced when the function accepts the object's baseclass by value. The compiler will create an instance of that baseclass instead of a copy of the derived class, and now you could be in a lot of trouble, because any virtual behavior that was implemented in the derived class is lost.

Here is a quick example:

class Base {
public:
    virtual ~Base() {}
    virtual void foo() const {
        (void)printf(“Base::foo() called.\n”);
    }
};

class Derived {
public:
    void foo() const {
        (void)printf(“Derived::foo() called.\n”);
    }
};

It is easy to see which foo() is being called, and we can now add the following functions and code to see how this slicing works:

void CallByValue(Base obj) { obj.foo(); }
void CallByReference(Base const &obj) { obj.foo(); }

/* test code */
(void)printf(“Slicing test.\n”);
Derived derived_obj;
(void)printf(“Calling CallByValue: “);
CallByValue(derived_obj);
(void)printf(“Calling CallByReference: “);
CallByReference(derived_obj);

The result confirms the description: “passing a derived object to a function that takes it baseclass as its parameter, causes this object to be sliced”… The first function call used Base::foo() and the second Derived::foo().

Slicing test.
Calling CallByValue: Base::foo() called.
Calling CallByReference: Derived::foo() called.

When passed by reference, the object remains intact. The function CallByReference doesn’t need a temporary object; it works with a reference to the baseclass instead of the object passed in.

Unfortunately we cannot blindly construct a coding rule that passing a function argument by const reference is always better than passing it by value. The reason for this is the fact that const references allow the compiler to perform an implicit conversion. We have actually come full circle.

C++ functions are "friendly" enough to take any object that can implicitly be converted to the parameter it accepts according to its declaration. These conversions can only be made on parameters passed by value or by const reference because these are the only ones that are under full control of the compiler.

Let’s extend the code we have been using to test object slicing. First, here is a simple class we will call Empty:

class Empty {
public:
 Empty() { (void)printf(“Empty object created.\n”); }
        void foo() const { (void)printf(“Empty::foo() called.\n”); }
};

Next we add a conversion constructor to our Base class. This is a constructor that can be called with an argument that is used to convert to the object that is about to be constructed.

class Base {
public:
 Base() {
      (void)printf(“Base created.\n”);
        }
      Base(Empty const &other) {
      (void)printf(“Base created from Emtpy object.\n”);
 }
 ~Base() {
(void)printf(“Base destroyed.\n”);
        }
 ...
};

Now we can visualize the application of the conversion constructor:

(void)printf(“Implicit Conversion test.\n”);
Empty empty_obj;
(void)printf(“calling CallByValue()\n”);
CallByValue(empty_obj);
(void)printf(“calling CallByReference()\n”);
CallByReference(empty_obj);

Running this code yields the following result:

Implicit Conversion test.
Empty object created.
calling CallByValue()
Base created from Empty object.
Base::foo() called.
Base destroyed.
calling CallByReference()
Base created from Empty object.
Base::foo() called.
Base destroyed.

The conversion constructor has made it possible to use the two functions that accept a Base class by passing an Empty object, either by value or by const reference. This was possible because the compiler constructs a temporary object that is a conversion of the object passed in. If you remove the const modifier in the CallByReference function declaration, the compiler will complain that it cannot convert an Empty object to a Base reference simply because it is not possible to map Empty onto Base directly… only through implicit conversion.

The Microsoft compiler in this case will complain:

Error C2664: ‘CallByReference’ : cannot convert parameter 1 from
‘Empty’ to ‘Base &’ - A reference that is not to ‘const’ cannot be bound to a non-lvalue.

We can conclude that when a function parameter utilizes a const reference, there is the possibility that an object passed into this function will be implicitly converted. So passing by value might facilitate slicing, which has unpleasant side-effects… but when using const references, we might facilitate the creation and destruction of a temporary variable.

Of course this example using a Base and Empty class is very hypothetical, but if you use the STL you have probably used conversion constructors already.

 It is why you can use foo(“some text”) with a function declaration like:

void foo (std::string const &label);

The std::string has a conversion constructor that accepts a char const*… which is very useful; just not free.

It wouldn’t be me writing these articles if I could not find a way to add insult to injury.  So how about returning a const reference from a function that was passed to that const reference?

Here is a nasty change to the CallByReference function:

Base const& AnotherCallByReference(Base const &obj);

You should realize now that this function might return a const reference to a temporary object (!). This temporary object is bound to be destroyed (rather) sooner or later… invalidating the reference to it.

As always… not everything is at it may seem to be.