Pass-by-Reference

The pass-by-reference rule is discussed elsewhere in this book, but it’s worth repeating here.

When you pass an object of a derived class by value as argument for a function parameter with as type one of the base classes, then the derived object is sliced to fit into the base class type. This causes information to be lost, see Chapter 10 for details.

Pass-by-value also incurs copying costs that are avoided with pass-by-reference. One reason why this rule can be difficult to remember is that on the surface there doesn’t appear to be any problem when you pass-by-value. Consider a class to represent a person that looks like this:

class Person
{
    public:
        Person() = default;
        Person(std::string_view firstName, std::string_view lastName, int age);
        virtual ~Person() = default;

        std::string_view getFirstName() const { return mFirstName; }
        std::string_view getLastName() const { return mLastName; }
        int getAge() const { return mAge; }

     private:
        std::string mFirstName, mLastName;
        int mAge = 0;
};

You could write a function that takes a Person object as follows:

void processPerson(Person p)
{
    // Process the person.
}

You can call this function like this:

Person me("Marc", "Gregoire", 38); 
processPerson(me);

This doesn’t look like there’s any more code than if you write the function like this instead:

void processPerson(const Person& p)
{
    // Process the person.
}

The call to the function remains the same. However, consider what happens when you pass-by-value in the first version of the function. In order to initialize the p parameter of processPerson(), me must be copied with a call to its copy constructor. Even though you didn’t write a copy constructor for the Person class, the compiler generates one that copies each of the data members. That still doesn’t look so bad: there are only three data members. However, two of them are strings, which are themselves objects with copy constructors. So, each of their copy constructors will be called as well. The version of processPerson() that takes p by reference incurs no such copying costs. Thus, pass-by-reference in this example avoids three copy constructor calls when the code enters the function.

And you’re still not done. Remember that p in the first version of processPerson() is a local variable to the processPerson() function, and so must be destroyed when the function exits. This destruction requires a call to the Person destructor, which will call the destructor of all of the data members. strings have destructors, so exiting this function (if you passed by value) incurs calls to three destructors. None of those calls are needed if the Person object is passed by reference.

Return-by-Reference

Just as you should pass objects by reference to functions, you should also return them by reference from functions in order to avoid copying the objects unnecessarily. Unfortunately, it is sometimes impossible to return objects by reference, such as when you write overloaded operator+ and other similar operators. And, you should never return a reference or a pointer to a local object that will be destroyed when the function exits!

Since C++11, the language has support for move semantics, which allows you to efficiently return objects by value, instead of using reference semantics.

Catch Exceptions by Reference

As noted in Chapter 14, you should catch exceptions by reference in order to avoid slicing and unnecessary copying. Throwing exceptions is heavy in terms of performance, so any little thing you can do to improve their efficiency will help.

Use Move Semantics

You should make sure your classes have a move constructor and move assignment operator to allow the C++ compiler to use move semantics with objects of those classes. According to the rule of zero (see Chapter 9), you should try to design your classes such that the compiler generated copy and move constructors and copy and move assignment operators are sufficient. If the compiler cannot implicitly define these for a class, try to explicitly default them if that works for your class. If that is also not an option, you should implement them yourself. With move semantics for your objects, returning them by value from a function will be efficient without incurring large copying costs. Consult Chapter 9 for details on move semantics.

Avoid Creating Temporary Objects

The compiler creates temporary, unnamed objects in several circumstances. Chapter 9 explains that after writing a global operator+ for a class, you can add objects of that class to other types, as long as those types can be converted to objects of that class. For example, the SpreadsheetCell class definition looks in part like this:

class SpreadsheetCell
{
    public:
        // Other constructors omitted for brevity
         SpreadsheetCell(double initialValue);
        // Remainder omitted for brevity
};

SpreadsheetCell operator+(const SpreadsheetCell& lhs,
    const SpreadsheetCell& rhs);

The constructor that takes a double allows you to write code like this:

SpreadsheetCell myCell(4), aThirdCell;
aThirdCell = myCell + 5.6;
aThirdCell = myCell + 4;

The second line constructs a temporary SpreadsheetCell object from the 5.6 argument; it then calls the operator+ with myCell and this temporary object as arguments. The result is stored in aThirdCell. The third line does the same thing, except that 4 must be coerced to a double in order to call the double constructor of the SpreadsheetCell.

The important point in this example is that the compiler generates code to create an extra, unnamed SpreadsheetCell object for both addition operations in this example. That object must be constructed and destructed with calls to its constructor and destructor. If you’re still skeptical, try inserting cout statements in your constructor and destructor, and watch the printout.

In general, the compiler constructs a temporary object whenever your code converts a variable of one type to another type for use in a larger expression. This rule applies mostly to function calls. For example, suppose that you write a function with the following prototype:

void doSomething(const SpreadsheetCell& s);

You can call this function like this:

doSomething(5.56);

The compiler constructs a temporary SpreadsheetCell object from 5.56 using the double constructor. This temporary object is then passed to doSomething(). Note that if you remove the const from the s parameter, you can no longer call doSomething() with a constant; you must pass a variable.

You should generally attempt to avoid cases in which the compiler is forced to construct temporary objects. Although it is impossible to avoid in some situations, you should at least be aware of the existence of this “feature” so you aren’t surprised by performance and profiling results.

Move semantics is used by the compiler to make working with temporary objects more efficient. That’s another reason to make sure your classes support move semantics. See Chapter 9 for details.

The Return-Value Optimization

A function that returns an object by value can cause the creation of a temporary object. Continuing with the Person example from earlier, consider this function:

Person createPerson()
{
    Person newP("Marc", "Gregoire", 38);
    return newP;
}

Suppose that you call it like this (assuming that operator<< is implemented for the Person class):

cout << createPerson();

Even though this call does not store the result of createPerson() anywhere, the result must be stored somewhere in order to pass it to operator<<. In order to generate code for this behavior, the compiler is allowed to create a temporary variable in which to store the Person object returned from createPerson().

Even if the result of the function is not used anywhere, the compiler might still generate code to create the temporary object. For example, suppose that you have this code:

createPerson();

The compiler might generate code to create a temporary object for the return value, even though it is not used.

However, you usually don’t need to worry about this issue because in most cases, the compiler optimizes away the temporary variable to avoid all copying and moving. For the createPerson() example, this optimization is called named return value optimization (NRVO) because the return statement returns a named variable. In the case the return statement has as argument a nameless temporary value, then this optimization is called return value optimization (RVO). These kinds of optimizations are usually only enabled for release builds. For NRVO to work, the argument to the return statement must be a single local variable. For example, in the following case, the compiler cannot do NRVO:

Person createPerson()
{
    Person person1;
    Person person2;
    return getRandomBool() ? person1 : person2;
}

If NRVO and RVO are not applicable, then copying or moving will happen. If the object you want to return from a function supports move semantics, then it is moved out of the function instead of copied.

An Object Pool Implementation

This section provides an implementation of an object pool class template that you can use in your programs. The pool hands out objects via the acquireObject() method. If acquireObject() is called but there are no free objects, then the pool allocates another instance of the object. acquireObject() returns an Object that is an std::shared_ptr with a custom deleter. The custom deleter doesn’t actually delete the memory; it simply puts the object back on the list of free objects.

The most difficult aspect of an object pool implementation is keeping track of which objects are free and which are in use. This implementation takes the approach of storing free objects in a queue. Each time a client requests an object, the pool gives that client the top object from the queue. The code uses the std::queue class from the Standard Library, as discussed in Chapter 17. Because this standard data structure is used, this implementation is not thread safe. One way to make it thread safe is to use a lock-free concurrent queue. However, the Standard Library does not provide any concurrent data structures, so you’ll have to use third-party libraries.

Here is the class definition, with comments that explain the details. The class template is parameterized on the class type from which the objects in the pool are to be constructed.

#include <queue>
#include <memory>

// Provides an object pool that can be used with any class that provides a
// default constructor.
//
// acquireObject() returns an object from the list of free objects. If
// there are no more free objects, acquireObject() creates a new instance.
// The pool only grows: objects are never removed from the pool (freed),
// until the pool is destroyed.
// acquireObject() returns an Object which is an std::shared_ptr with a
// custom deleter that automatically puts the object back into the object
// pool when the shared_ptr is destroyed and its reference reaches 0.
//
// The constructor and destructor on each object in the pool will be called
// only once each for the lifetime of the object pool, not once per
// acquisition and release.
//
// The primary use of an object pool is to avoid creating and deleting
// objects repeatedly. This object pool is most suited to applications that
// use large numbers of objects with expensive constructors for short
// periods of time, and if a profiler tells you that allocating and
// deallocating these objects is a bottleneck.
template <typename T>
class ObjectPool
{
    public:
        ObjectPool() = default;
        virtual ~ObjectPool() = default;

        // Prevent assignment and pass-by-value
        ObjectPool(const ObjectPool<T>& src) = delete;
        ObjectPool<T>& operator=(const ObjectPool<T>& rhs) = delete;

        // The type of smart pointer returned by acquireObject().
        using Object = std::shared_ptr<T>;

        // Reserves and returns an object for use.
        Object acquireObject();
    private:
        // Stores the objects that are not currently in use by clients.
        std::queue<std::unique_ptr<T>> mFreeList;
};

When using this object pool, you have to make sure that the object pool itself outlives all the objects handed out by the pool. A user of the object pool specifies through the template parameter the name of the class from which objects can be created.

acquireObject() returns the top object from the free list, first allocating a new object if there are no free objects:

template <typename T>
typename ObjectPool<T>::Object ObjectPool<T>::acquireObject()
{
    if (mFreeList.empty()) {
        mFreeList.emplace(std::make_unique<T>());
    }

    // Move next free object from the queue to a local unique_ptr.
    std::unique_ptr<T> obj(std::move(mFreeList.front()));
    mFreeList.pop();

    // Convert the object pointer to an Object (a shared_ptr with
    // a custom deleter).
    Object smartObject(obj.release(), [this](T* t){
        // The custom deleter doesn't actually deallocate the
        // memory, but simply puts the object back on the free list.
        mFreeList.emplace(t);
    });

    // Return the Object.
    return smartObject;
}

Using the Object Pool

Consider an application that uses a lot of short-lived objects with an expensive constructor. Let’s assume the ExpensiveObject class definition looks as follows:

class ExpensiveObject
{
    public:
        ExpensiveObject() { /* Expensive construction … */ }
        virtual ~ExpensiveObject() = default;
         // Methods to populate the object with specific information.
         // Methods to retrieve the object data.
         // (not shown)
    private:
         // Data members (not shown)
};

Instead of creating and deleting large numbers of such objects throughout the lifetime of your program, you can use the object pool developed in the previous section. Your program structure could be something like this:

ObjectPool<ExpensiveObject>::Object
    getExpensiveObject(ObjectPool<ExpensiveObject>& pool)
{
    // Obtain an ExpensiveObject object from the pool.
    auto object = pool.acquireObject();

    // Populate the object. (not shown)

    return object;
}

void processExpensiveObject(ObjectPool<ExpensiveObject>::Object& object)
{
    // Process the object. (not shown)
}

int main()
{
    ObjectPool<ExpensiveObject> requestPool;

    {
        vector<ObjectPool<ExpensiveObject>::Object> objects;
        for (size_t i = 0; i < 10; ++i) {
            objects.push_back(getExpensiveObject(requestPool));
        }
    }

    for (size_t i = 0; i < 100; ++i) {
        auto req = getExpensiveObject(requestPool);
        processExpensiveObject(req);
    }
    return 0;
}

The first part of this main() function contains an inner code block which creates ten expensive objects and stores them in the objects container. Because all created Objects are stored in a vector and thus kept alive, the object pool is forced to create ten ExpensiveObject instances. At the closing brace of the inner code block, the vector goes out of scope, and all Objects contained in it are automatically released back to the object pool.

In the second for loop, the Objects (= shared_ptrs) returned by getExpensiveObject() go out of scope at the end of each iteration of the for loop, and so are automatically released back to the pool. If you add an output statement to the constructor of the ExpensiveObject class, you’ll see that the constructor is only called ten times during the entire program, even though the second for loop in main() loops a hundred times.

First Design Attempt

A logical design for this program consists of a NameDB class with the following public methods:

#include <string_view>

class NameDB
{
    public:
        // Reads list of baby names in nameFile to populate the database.
        // Throws invalid_argument if nameFile cannot be opened or read.
        NameDB(std::string_view nameFile);

        // Returns the rank of the name (1st, 2nd, etc).
        // Returns –1 if the name is not found.
        int getNameRank(std::string_view name) const;

        // Returns the number of babies with this name.
        // Returns –1 if the name is not found.
        int getAbsoluteNumber(std::string_view name) const;

        // Protected and private members and methods not shown
};

The hard part is choosing a good data structure for the in-memory database. My first attempt is a vector of name/count pairs. Each entry in the vector stores one of the names, along with a count of the number of times that name shows up in the raw data file. Here is the complete class definition with this design:

#include <string_view>
#include <string>
#include <vector>
#include <utility>

class NameDB
{
    public:
        NameDB(std::string_view nameFile);
        int getNameRank(std::string_view name) const;
        int getAbsoluteNumber(std::string_view name) const;
    private:
        std::vector<std::pair<std::string, int>> mNames;

        // Helper methods
        bool nameExists(std::string_view name) const;
        void incrementNameCount(std::string_view name);
        void addNewName(std::string_view name);
};

Note the use of the Standard Library vector and pair classes, both of which are discussed in Chapter 17. A pair is a utility class that combines two values of possibly different types.

Here are the implementations of the constructor and the helper methods nameExists(), incrementNameCount(), and addNewName(). The loops in nameExists() and incrementNameCount() iterate over all the elements of the vector.

// Reads the names from the file and populates the database.
// The database is a vector of name/count pairs, storing the
// number of times each name shows up in the raw data.
NameDB::NameDB(string_view nameFile)
{
    // Open the file and check for errors.
    ifstream inputFile(nameFile.data());
    if (!inputFile) {
        throw invalid_argument("Unable to open file");
    }

    // Read the names one at a time.
    string name;
    while (inputFile >> name) {
        // Look up the name in the database so far.
        if (nameExists(name)) {
            // If the name exists in the database, just increment the count.
            incrementNameCount(name);
        } else {
            // If the name doesn't yet exist, add it with a count of 1.
            addNewName(name);
        }
    }
}

// Returns true if the name exists in the database, false otherwise.
bool NameDB::nameExists(string_view name) const
{
    // Iterate through the vector of names looking for the name.
    for (auto& entry : mNames) {
        if (entry.first == name) {
            return true;
        }
    }
    return false;
}

// Precondition: name exists in the vector of names.
// Postcondition: the count associated with name is incremented.
void NameDB::incrementNameCount(string_view name)
{
    for (auto& entry : mNames) {
        if (entry.first == name) {
            entry.second++;
            return;
        }
    }
}

// Adds a new name to the database.
void NameDB::addNewName(string_view name)
{
    mNames.push_back(make_pair(name.data(), 1));
}

Note that in the preceding example, you could use an algorithm like find_if() to accomplish the same thing as the loops in nameExists() and incrementNameCount(). The loops are shown explicitly in order to emphasize the performance problems.

You might have noticed some performance problems already. What if there are hundreds of thousands of names? The many linear searches involved in populating the database will become slow.

In order to complete the example, here are the implementations of the two public methods:

// Returns the rank of the name.
// First looks up the name to obtain the number of babies with that name.
// Then iterates through all the names, counting all the names with a higher
// count than the specified name. Returns that count as the rank.
int NameDB::getNameRank(string_view name) const
{
    // Make use of the getAbsoluteNumber() method.
    int num = getAbsoluteNumber(name);

    // Check if we found the name.
    if (num == -1) {
        return -1;
    }

    // Now count all the names in the vector that have a
    // count higher than this one. If no name has a higher count,
    // this name is rank number 1. Every name with a higher count
    // decreases the rank of this name by 1.
    int rank = 1;
    for (auto& entry : mNames) {
        if (entry.second > num) {
            rank++;
        }
    }
    return rank;
}

// Returns the count associated with this name.
int NameDB::getAbsoluteNumber(string_view name) const
{
    for (auto& entry : mNames) {
        if (entry.first == name) {
            return entry.second;
        }
    }
    return -1;
}

Profiling the First Design Attempt

In order to test the program, you need a main() function:

#include "NameDB.h"
#include <iostream>
using namespace std;

int main()
{
    NameDB boys("boys_long.txt");
    cout << boys.getNameRank("Daniel") << endl;
    cout << boys.getNameRank("Jacob") << endl;
    cout << boys.getNameRank("William") << endl;
    return 0;
}

This main() function creates one NameDB database called boys, telling it to populate itself with the file boys_long.txt, which contains 500,500 names.

There are three steps to using gprof:

1. Compile your program with a special flag that causes it to log raw execution information when it is run. When using GCC as your compiler, the flag is –pg, as in this example:

   > gcc -lstdc++ -std=c++17 -pg -o namedb NameDB.cpp NameDBTest.cpp

2. Run your program. This should generate a file called gmon.out in the working directory. Be patient when you run the program because this first version is slow.
3. Run the gprof command. This final step enables you to analyze the gmon.out profiling information and produce a (somewhat) readable report. gprof outputs to standard out, so you should redirect the output to a file:

> gprof namedb gmon.out > gprof_analysis.out

Now you can analyze the data. Unfortunately, the output file is somewhat cryptic and intimidating, so it takes a little while to learn how to interpret it. gprof provides two separate sets of information. The first set summarizes the amount of time spent executing each function in the program. The second and more useful set summarizes the amount of time spent executing each function and its descendants; this set is also called a call graph. Here is some of the output from the gprof_analysis.out file, edited to make it more readable. Note that the numbers will be different on your machine.

index  %time    self  children    called     name 
[1]    100.0    0.00   14.06                 main [1]
                0.00   14.00       1/1           NameDB::NameDB [2]
                0.00    0.04       3/3           NameDB::getNameRank [25]
                0.00    0.01       1/1           NameDB::~NameDB [28] 

The following list explains the different columns.

• index: an index to be able to refer to this entry in the call graph.
• %time: the percentage of the total execution time of the program required by this function and its descendants.
• self: how many seconds the function itself was executing.
• children: how many seconds the descendants of this function were executing.
• called: how often this function was called.
• name: the name of the function. If the name of the function is followed by a number between square brackets, that number refers to another index in the call graph.

The preceding extract tells you that main() and its descendants took 100 percent of the total execution time of the program, for a total of 14.06 seconds. The second line shows that the NameDB constructor took 14.00 seconds of the total 14.06 seconds. So, it’s immediately clear where the performance issue is situated. To track down which part of the constructor is taking so long, you need to jump to the call graph entry with index 2, because that’s the index in square brackets behind the name in the last column. The call graph entry with index 2 is as follows on my test system:

[2] 99.6    0.00   14.00       1         NameDB::NameDB [2]
            1.20    6.14  500500/500500      NameDB::nameExists [3]
            1.24    5.24  499500/499500      NameDB::incrementNameCount [4]
            0.00    0.18    1000/1000        NameDB::addNewName [19]
            0.00    0.00       1/1           vector::vector [69]

The nested entries below NameDB::NameDB show which of its descendants took the most time. Here you can see that nameExists() took 6.14 seconds, and incrementNameCount()took 5.24 seconds. These times are the sums of all the calls to the functions. The fourth column in those lines shows the number of calls to the function (500,500 to nameExists() and 499,500 to incrementNameCount()). No other function took a significant amount of time.

Without going any further in this analysis, two things should jump out at you:

1. Taking 14 seconds to populate the database of approximately 500,000 names is slow. Perhaps you need a better data structure.
2. nameExists() and incrementNameCount() take an almost identical amount of time, and are called almost the same number of times. If you think about the application domain, that makes sense: most names in the input text file are duplicates, so the vast majority of the calls to nameExists() are followed by a call to incrementNameCount(). If you look back at the code, you can see that these functions are almost identical; they could probably be combined. In addition, most of what they are doing is searching the vector. It would probably be better to use a sorted data structure to reduce the searching time.

Second Design Attempt

With these two observations from the gprof output, it’s time to redesign the program. The new design uses a map instead of a vector. Chapter 17 explains that the Standard Library map keeps the entries sorted, and provides O(log n) lookup instead of the O(n) searches in a vector. A good exercise for you to try would be to use an std::unordered_map, which has an expected O(1) for lookups, and to use a profiler to see if that is faster than std::map for this application.

The new version of the program also combines nameExists() and incrementNameCount() into one nameExistsAndIncrement() method.

Here is the new class definition:

#include <string_view>
#include <string>
#include <map>

class NameDB
{
    public:
        NameDB(std::string_view nameFile);
        int getNameRank(std::string_view name) const;
        int getAbsoluteNumber(std::string_view name) const;
    private:
        std::map<std::string, int> mNames;
        bool nameExistsAndIncrement(std::string_view name);
        void addNewName(std::string_view name);
};

Here are the new method implementations:

// Reads the names from the file and populates the database.
// The database is a map associating names with their frequency.
NameDB::NameDB(string_view nameFile)
{
    // Open the file and check for errors.
    ifstream inputFile(nameFile.data());
    if (!inputFile) {
        throw invalid_argument("Unable to open file");
    }

    // Read the names one at a time.
    string name;
    while (inputFile >> name) {
        // Look up the name in the database so far.
        if (!nameExistsAndIncrement(name)) {
            // If the name exists in the database, the
            // method incremented it, so we just continue.
            // We get here if it didn't exist, in which case
            // we add it with a count of 1.
            addNewName(name);
        }
    }
}

// Returns true if the name exists in the database, false
// otherwise. If it finds it, it increments it.
bool NameDB::nameExistsAndIncrement(string_view name)
{
    // Find the name in the map.
    auto res = mNames.find(name.data());
    if (res != end(mNames)) {
        res->second++;
        return true;
    }
    return false;
}

// Adds a new name to the database.
void NameDB::addNewName(string_view name)
{
    mNames[name.data()] = 1;
}

int NameDB::getNameRank(string_view name) const
{
    // Implementation omitted, same as before.
}

// Returns the count associated with this name.
int NameDB::getAbsoluteNumber(string_view name) const
{
    auto res = mNames.find(name.data());
    if (res != end(mNames)) {
        return res->second;
    }
    return -1;
}

Profiling the Second Design Attempt

By following the same steps shown earlier, you can obtain the gprof performance data on the new version of the program. The data is quite encouraging:

index %time  self  children    called        name 
[1]   100.0  0.00    0.21                    main [1]
             0.02    0.18      1/1           NameDB::NameDB [2]
             0.00    0.01      1/1           NameDB::~NameDB [13]
             0.00    0.00      3/3           NameDB::getNameRank [28] 
[2]    95.2  0.02    0.18      1             NameDB::NameDB [2]
             0.02    0.16 500500/500500      NameDB::nameExistsAndIncrement 
[3]          0.00    0.00   1000/1000        NameDB::addNewName [24]
             0.00    0.00      1/1           map::map [87]

If you run this on your machine, the output will be different. It’s even possible that you will not see the data for NameDB methods in your output. Because of the efficiency of this second attempt, the timings are getting so small that you might see more map methods in the output than NameDB methods.

On my test system, main() now takes only 0.21 seconds—a 67-fold improvement! There are certainly further improvements that you could make on this program. For example, the current constructor performs a lookup to see if the name is already in the map, and if not, adds it to the map. You could combine these two operations simply with the following single line:

++mNames[name];

If the name is already in the map, this statement just increments its counter. If the name is not yet in the map, this statement first adds an entry to the map with the given name as key and a zero-initialized value, and then increments the value, resulting in a counter of 1.

With this improvement, you can remove the nameExistsAndIncrement() and addNewName() methods, and change the constructor as follows:

NameDB::NameDB(string_view nameFile)
{
    // Open the file and check for errors
    ifstream inputFile(nameFile.data());
    if (!inputFile) {
        throw invalid_argument("Unable to open file");
    }

    // Read the names one at a time.
    string name;
    while (inputFile >> name) {
        ++mNames[name];
    }
}

getNameRank() still uses a loop that iterates over all elements in the map. A good exercise for you to try is to come up with another data structure so that the linear iteration in getNameRank() can be avoided.