Writing Efficient C++

Use Thread Pools

Thread pools are very similar to object pools. Instead of creating and deleting threads dynamically throughout your program lifetime, you can create a pool of threads that can be used as needed. This technique is often used in programs that process incoming network requests. Your Web server might keep a pool of threads ready to lookup pages in response to each client request that arrives.

As discussed further in Chapter 18, threading support is platform-specific, so we do not show an example of a thread pool here. However, you can write one in a similar way to an object pool.

Profiling

Although we urge you to think about efficiency as you design and code, you should accept that not every finished application will perform as well as it could. It is easy for efficiency to fall by the wayside in an attempt to generate a functional program; in our experience, most efficiency optimization is performed on already working programs. Even if you did consider efficiency in your development, you might not have optimized the right parts of the program! Recall from Chapter 4 that 90 percent of the running time of most programs is spent in only 10 percent of the code. This means that you could optimize 90 percent of your code out of existence, but still only improve the running time of the program by 10 percent. Obviously, you want to optimize the parts of the code that are exercised the most for the specific workload that you expect the program to run.

Consequently, it is often helpful to profile your program to determine which parts of the code require optimization. There are many profiling tools available that analyze programs as they run in order to generate data about their performance. Most profiling tools provide analysis at the function level by specifying the amount of time (or percent of total execution time) spent in each function in the program. After running a profiler on your program, you can usually tell immediately which parts of the program need optimization. Profiling before and after optimizing is also useful to prove that your optimizations had an effect.

In our experience, the best profiling tool is Rational Quantify from IBM. It requires significant license fees, but you should check if your company or academic institution has a license for its use. If the license restriction is prohibitive, there are several free profiling tools. One of the most well-known is gprof, which can be found on most Unix systems, including Solaris and Linux.

Profiling Example with gprof

The power of profiling can best be seen with a real coding example. As a disclaimer, the performance bugs in the first attempt shown are not subtle. Real efficiency issues would probably be more complex, but a program long enough to demonstrate them would be too lengthy for this book.

Suppose that you work for the United States Social Security Administration. Every year the administration puts up a Web site that allows users to look up the popularity of new baby names from the previous year. Your job is to write the back-end program that looks up names for users. Your input is a file containing the name of every new baby. This file will obviously contain redundant names. For example, in the file for boys for 2003, the name Jacob was the most popular, showing up 29,195 times. Your program must read the file to construct an in-memory database. A user may then request the absolute number of babies with a given name, or the rank of that name among all the babies.

479

Chapter 17

First Design Attempt

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

#include <string> #include <stdexcept>

using std::string;

class NameDB

{

public:

//Reads the list of baby names in nameFile to populate the database.

//Throws invalid_argument if nameFile cannot be opened or read. NameDB(const string& nameFile) throw (std::invalid_argument);

//Returns the rank of the name (1st, 2nd, etc).

//Returns –1 if the name is not found.

int getNameRank(const string& name) const;

//Returns the number of babies with this name.

//Returns –1 if the name is not found.

int getAbsoluteNumber(const string &name) const;

// Protected and private members and methods not shown

};

The hard part is choosing a good data structure for the in-memory database. A first attempt might be an array, or a vector from the STL, of name/count pairs. Each entry in the vector would store 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 such a design:

#include <string> #include <stdexcept> #include <vector>

using std::string;

class NameDB

{

public:

NameDB(const string& nameFile) throw (std::invalid_argument);

int getNameRank(const string&	name)	const;
int getAbsoluteNumber(const string&		name) const;
protected:
std::vector<std::pair<string,	int> > mNames;
// Helper methods
bool nameExists(const string&	name)	const;
void incrementNameCount(const	string& name);
void addNewName(const string&	name);

private:

480

Writing Efficient C++

// Prevent assignment and pass-by-value. NameDB(const NameDB& src);

NameDB& operator=(const NameDB& rhs);

};

Note the use of the STL vector and pair. A pair is simply a utility class that combines two variables of different types. Consult Chapters 21 to 23 for details on the STL.

Here is the implementation of the constructor and the helper functions nameExists(), incrementNameCount(), and addNewName(). If you’re unfamiliar with the STL, you might be confused by the loops in nameExists() and incrementNameCount(). They simply iterate over all the elements of the mNames vector.

//

//Reads the names from the file and populates the database.

//The database is vector of name/count pairs, storing the

//number of times each name shows up in the raw data.

//

NameDB::NameDB(const string& nameFile) throw (invalid_argument)

{

//Open the file and check for errors. ifstream inFile(nameFile.c_str());

if (!inFile) {

throw invalid_argument(“Unable to open file\n”);

}

//Read the names one at a time.

string name;

while (inFile >> 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);

}

}

inFile.close();

}

//

//nameExists

//Returns true if the name exists in the database. Returns false otherwise.

bool NameDB::nameExists(const string& name) const

{

//Iterate through the vector of names looking for the name.

for (vector<pair<string, int> >::const_iterator it = mNames.begin(); it != mNames.end(); ++it) {

if (it->first == name) {

481

Chapter 17

return (true);

}

}

return (false);

}

//

//incrementNameCount

//Precondition: name exists in the vector of names.

//Postcondition: the count associated with name is incremented.

void NameDB::incrementNameCount(const string& name)

{

for (vector<pair<string, int> >::iterator it = mNames.begin(); it != mNames.end(); ++it) {

if (it->first == name) {

it->second++; return;

}

}

}

//

//addNewName

//Adds a new name to the database

void NameDB::addNewName(const string& name)

{

mNames.push_back(make_pair<string, int>(name, 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(). We show the loops explicitly in order to emphasize the performance problems.

The savvy reader might notice some performance problems already. What if there are hundreds of thousands of names? The many linear searches involved in populating the database might become slow.

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

//

//getNameRank

//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(const string& name) const

{

// Make use of the getAbsoluteNumber() method. int num = getAbsoluteNumber(name);

482

Writing Efficient C++

// 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 (vector<pair<string, int> >::const_iterator it = mNames.begin(); it != mNames.end(); ++it) {

if (it->second > num) { rank++;

}

}

return (rank);

}

//

//getAbsoluteNumber

//Returns the count associated with this name

int NameDB::getAbsoluteNumber(const string& name) const

{

for (vector<pair<string, int> >::const_iterator it = mNames.begin(); it != mNames.end(); ++it) {

if (it->first == name) {

return(it->second);

}

}

return (-1);

}

Profile of the First Attempt

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

#include “NameDB.h”

int main(int argc, char** argv)

{

NameDB boys(“boys_long.txt”);

cout << boys.getNameRank(“Daniel”) << endl; cout << boys.getNameRank(“Jacob”) << endl; cout << boys.getNameRank(“William”) << endl;

return (0);

}

483

Chapter 17

This main creates one NameDB database called boys, telling it to populate itself with the file boys_long

.txt This file 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 next time it is run. On Solaris 9, using the SunOne Studio 8 C++ Compiler, the flag is –xpg:

>CC -o namedb -xpg main.cpp NameDB.cpp

2.Next, run your pogram. This run should generate a file gmon.out in the working directory.

3.The final step is to run the gprof command in order to analyze the gmon.out profiling information and produce a (somewhat) readable report. The –C option tells gprof to demangle C++ function names so they are more readable. gprof outputs to standard out, so you should redirect the output to a file:

>gprof -C namedb gmon.out > gprof_analysis.out

Now you can analyze the data. Unfortunately, the output file is somewhat cryptic and intimidating. It takes a little while to learn how to interpret it. gprof provides two separate sets of information. The second set summarizes the amount of time spent executing each function in the program. The first, and more useful, set summarizes the amount of time spent executing each function and its descendents. Here is some of the output from the gprof_analysis.out file, edited to make it more readable:

[2]

85.1

0.00

48.21

1

main [2]

The preceding line means that main() and its descendents took 85.1 percent of the total execution time of the program, for a total of 48.21 seconds. The remaining 14.9 percent of the time was spent performing other tasks like looking for dynamically linked libraries and initializing global variables. The next entry shows that the NameDB constructor and its descendents took 48.18 seconds, which is almost the entire time of main(). The nested entries below NameDB::NameDB show which of its descendents took the most time. Here you can see that nameExists() and incrementNameCount() both took approximately 14 seconds. Remember that these times are the sums of all the calls to the functions. The third column

in those lines shows the number of calls to the function (500,500 to nameExists() and 499,500 to incrementNameCont()). No other function took a significant amount of the NameDB time.

[3]	85.1	0.03	48.18	1	NameDB::NameDB
		9.60	14.04	500500/500500	bool NameDB::nameExists
		8.36	14.00	499500/499500	void NameDB::incrementNameC
ount

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

1.48 seconds to populate the database of approximately 500,000 names is slow. Perhaps you need a better data structure.

2.nameExists() and incrementNameCount() take almost identical time, and are called almost the same number of times. If you think about the application domain, that makes sense: most names in the text file input 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.

484

Writing Efficient C++

Second 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. Recall from Chapter 4 that the STL map employs an underlying tree structure that keeps the entries sorted, and provides O(log n) lookup instead of the O(n) searches in the vector.

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

Here is the new class definition:

#include <string> #include <stdexcept> #include <map>

using std::string;

class NameDB

{

public:

NameDB(const string& nameFile) throw (std::invalid_argument);

int getNameRank(const string& name) const;

int getAbsoluteNumber(const string& name) const;

protected:

std::map<string, int> mNames;

bool nameExistsAndIncrement(const string& name); void addNewName(const string& name);

private:

// Prevent assignment and pass-by-value NameDB(const NameDB& src);

NameDB& operator=(const NameDB& rhs);

};

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(const string& nameFile) throw (invalid_argument)

{

//

// Open the file and check for errors.

//

ifstream inFile(nameFile.c_str()); if (!inFile) {

throw invalid_argument(“Unable to open file\n”);

}

485

Chapter 17

//

// Read the names one at a time.

//

string name;

while (inFile >> name) {

//

// Look up the name in the database so far.

//

if (!nameExistsAndIncrement(name)) {

//

//If the name exists in the database, the

//function incremented it, so we just continue.

//We get here if it didn’t exist, in case which

//we add it with a count of 1.

//

addNewName(name);

}

}

inFile.close();

}

//

//nameExistsAndIncrement

//Returns true if the name exists in the database. false

//otherwise. If it finds it, it increments it.

//

bool NameDB::nameExistsAndIncrement(const string& name)

{

//

//Find the name in the map.

//

map<string, int>::iterator res = mNames.find(name); if (res != mNames.end()) {

res->second++; return (true);

}

return (false);

}

//

//addNewName

//Adds a new name to the database

void NameDB::addNewName(const string& name)

{

mNames.insert(make_pair<string, int>(name, 1));

}

//

//getNameRank

//Returns the

486

Writing Efficient C++

int NameDB::getNameRank(const string& name) const

{

int num = getAbsoluteNumber(name);

//

// Check if we found the name.

//

if (num == -1) { return (-1);

}

//

//Now count all the names in the map that have

//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 (map<string, int>::const_iterator it = mNames.begin(); it != mNames.end(); ++it) {

if (it->second > num) {

rank++;

}

}

return (rank);

}

//

//getAbsoluteNumber

//Returns the count associated with this name

int NameDB::getAbsoluteNumber(const string& name) const

{

map<string, int>::const_iterator res = mNames.find(name); if (res != mNames.end()) {

return (res->second);

}

return (-1);

}

Profile of the Second Attempt

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

[2]

85.3

0.00

3.19

1

main [2]

main() now takes only 3.19 seconds: a 15-fold improvement! There are certainly further improvements that you could make on this program, but we leave those as an exercise for the reader. One hint is that caching could come in handy for ranking the names.

487

Chapter 17

Summar y

This chapter discussed the key aspects of efficiency and performance in C++ programs, and provided several specific tips and techniques for designing and writing more efficient applications. We hope you gained an appreciation for the importance of performance and for the power of profiling tools. Remember to think about performance and efficiency from the beginning of your program life cycle: design-level efficiency is far more important than is language-level efficiency.

488