Chapter 17

However, the use of RTTI fails at run time, causing the program to generate a segmentation violation. Consult your compiler documentation for the proper flags to disable these features.

Disabling support for language features is risky. You never know when a third-party library will suddenly throw an exception or rely on RTTI for correct behavior. Thus, you should only disable support for exceptions and RTTI when you are sure that none of your code and none of the library code you use require those features, and when you are writing a performance-critical application.

Use Inline Methods and Functions

As described in Chapter 9, the code for an inline method or function is inserted directly into the code where it is called, avoiding the overhead of a function call. You should mark as inline all functions and methods that you think can qualify for this optimization. However, remember that inlining requests by the programmer are only a recommendation to the compiler. It can refuse to inline the function that you want it to inline.

On the other hand, some compilers inline appropriate functions and methods during their optimization steps, even if those functions aren’t marked with the inline keyword. Thus, you should read your compiler documentation before wasting a lot of effort deciding which functions to inline.

Design-Level Efficiency

The design choices in your program affect its performance far more than do language details such as pass-by-reference. For example, if you choose an algorithm for a fundamental task in your application that runs in O(n2) time instead of a simpler one that runs in O(n) time, you could potentially perform the square of the number of operations that you really need. To put numbers on that, a task that uses an O(n2) algorithm and performs one million operations would perform only one thousand with an O(n) algorithm Even if that operation is optimized beyond recognition at the language level, the simple fact that you perform one million operations when a better algorithm would only use one thousand will make your program very inefficient. Remember, though, that big-O notation ignores constant factors, so it’s not always the most valid guideline. Nonetheless, you should choose your algorithms carefully. Refer to Part I, specifically Chapter 4, of this book for a detailed discussion of algorithm design choices.

In addition to your choice of algorithms, design-level efficiency includes specific tips and tricks. The remainder of this section presents three design techniques for optimizing your program: caching, object pools, and thread pools.

Cache as Much as Possible

Caching means storing items for future use in order to avoid retrieving or recalculating them. You might be familiar with the principle from its use in computer hardware. Modern computer processors are built with memory caches that store recently and frequently accessed memory values in a location that is quicker to access than main memory. Most memory locations that are accessed at all are accessed more than once in a short time period, so caching at the hardware level can significantly speed up computations.

472

Writing Efficient C++

Caching in software follows the same approach. If a task or computation is particularly slow, you should make sure that you are not performing it more than necessary. Store the results in memory the first time you perform the task so that they are available for future needs. Here is a list of tasks that are usually slow:

Disk access. You should avoid opening and reading the same file more than once in your program. If memory is available, save the file contents in RAM if you need to access it frequently.

Network communication. Whenever you need to communicate over a network, your program is subject to the vagaries of the network load. Treat network accesses like file accesses, and cache as much static information as possible.

Mathematical computations. If you need the result of a computation in more than one place in your program, perform the calculation once and share the result.

Object allocation. If you need to create and use a large number of short-lived objects in your program, consider using an object pool, which is described in the next section.

Thread creation. This task can also be slow. You can “cache” threads in a thread-pool. See the section on Thread Pools below.

Cache Invalidation

One common problem with caching is that the data you store are often only copies of the underlying information. The original data might change during the lifetime of the cache. For example, you might want to cache the values in a configuration file so that you don’t need to read it repeatedly. However, the user might be allowed to change the configuration file while your program is running, which would make your cached version of the information obsolete. In cases like this, you need a mechanism for cache invalidation: when the underlying data change, you must either stop using your cached information, or repopulate your cache.

One technique for cache invalidation is to request that the entity managing the underlying data notify your program if the data change. It could do this through a callback that your program registers with the manager. Alternatively, your program could poll for certain events that would trigger it to repopulate the cache automatically. Regardless of your specific cache invalidation implementation, make sure that you think about these issues before relying on a cache in your program.

Use Object Pools

As you learned in Chapter 13, object pools are a technique for avoiding the creation and deletion of a large number of objects throughout the lifetime of your program. If you know that your program needs a large number of short-lived objects of the same type, you can create a pool, or cache, of those objects. Whenever you need an object in your code, you ask the pool for one. When you are done with the object, you return it to the pool. The object pool creates the objects only once, so their constructor is called only once, not each time they are used. Thus, object pools are appropriate when the constructor performs some setup actions that apply to many uses of the object, and when you can set instance-specific parameters on the object through nonconstructor method calls.

An Object Pool Implementation

This section provides an implementation of a pool class template that you can use in your programs. The pool allocates a chunk of objects of the specified class when it is constructed and hands them out via the acquireObject() method. When the client is done with the object, she returns it via the releaseObject() method. If aquireObject() is called but there are no free objects, the pool allocates another chunk of objects.

473

Chapter 17

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 on a queue. Each time a client requests an object, the pool gives that client the top object from the queue. The pool does not explicitly track objects that are in use. It trusts the clients to return them correctly to the pool when the clients are finished with them. Separately, the pool keeps track of all allocated objects in a vector. This vector is used only when the pool is destroyed in order to free the memory for all the objects, thereby preventing memory leaks.

The code uses the STL implementations of queue and vector, which were introduced in Chapter 4. The queue container allows clients to add elements with push(), remove them with pop(), and examine the top element with front(). The vector allows clients to add elements with push_back(). Consult Chapters 21 through 23 for more details of these two containers.

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

#include <queue> #include <vector> #include <stdexcept> #include <memory>

using std::queue; using std::vector;

//

//template class ObjectPool

//Provides an object pool that can be used with any class that provides a

//default constructor

//

//The object pool constructor creates a pool of objects, which it hands out

//to clients when requested via the acquireObject() method. When a client is

//finished with the object it calls releaseObject() to put the object back

//into the object pool.

//

//The constructor and destructor on each object in the pool will be called only

//once each for the lifetime of the program, not once per acquisition and release.

//The primary use of an object pool is to avoid creating and deleting objects

//repeatedly. The object pool is most suited to applications that use large

//numbers of objects for short periods of time.

//

//For efficiency, the object pool doesn’t perform sanity checks.

//It expects the user to release every acquired object exactly once.

//It expects the user to avoid using any objects that he or she has released.

//It expects the user not to delete the object pool until every object

//that was acquired has been released. Deleting the object pool invalidates

//any objects that the user has acquired, even if they have not yet been released.

template <typename T> class ObjectPool

{

474

Writing Efficient C++

public:

//

//Creates an object pool with chunkSize objects.

//Whenever the object pool runs out of objects, chunkSize

//more objects will be added to the pool. The pool only grows:

//objects are never removed from the pool (freed), until

//the pool is destroyed.

//

// Throws invalid_argument if chunkSize is <= 0

//

ObjectPool(int chunkSize = kDefaultChunkSize) throw(std::invalid_argument, std::bad_alloc);

//

//Frees all the allocated objects. Invalidates any objects that have

//been acquired for use

//

~ObjectPool();

//

//Reserve an object for use. The reference to the object is invalidated

//if the object pool itself is freed.

//

// Clients must not free the object!

//

T& acquireObject();

//

//Return the object to the pool. Clients must not use the object after

//it has been returned to the pool.

//

void releaseObject(T& obj);

protected:

//

//mFreeList stores the objects that are not currently in use

//by clients.

//

queue<T*> mFreeList;

//

//mAllObjects stores pointers to all the objects, in use

//or not. This vector is needed in order to ensure that all

//objects are freed properly in the destructor.

//

vector<T*> mAllObjects;

int mChunkSize;

static const int kDefaultChunkSize = 10;

//

//Allocates mChunkSize new objects and adds them

//to the mFreeList

//

void allocateChunk();

static void arrayDeleteObject(T* obj);

475

Chapter 17

private:

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

};

There are a few points to emphasize about this class definition. First, note that objects are acquired and released by reference, instead of by pointer, in order to discourage clients from manipulating them or freeing them through pointers. Next, note that the user of the object pool specifies through the template parameter the name of the class from which objects can be created, and through the constructor the allocation “chunk size.” This “chunk size” controls the number of objects created at one time. Here is the code that defines the kDefaultChunkSize:

template<typename T>

const int ObjectPool<T>::kDefaultChunkSize;

The default of 10, given in the class definition, is probably too small for most uses. If your program requires thousands of objects at once, you should use a larger, more appropriate, value.

The constructor validates the chunkSize parameter, and calls the allocateChunk() helper method to obtain a starting allocation of objects.

template <typename T>

ObjectPool<T>::ObjectPool(int chunkSize) throw(std::invalid_argument, std::bad_alloc) : mChunkSize(chunkSize)

{

if (mChunkSize <= 0) {

throw std::invalid_argument(“chunk size must be positive”);

}

// Create mChunkSize objects to start. allocateChunk();

}

The allocateChunk() method allocates mChunkSize elements in contiguous storage. It stores a pointer to the array of objects in the mAllObjects vector, and pushes each individual object onto the mFreeLlist queue.

//

//Allocates an array of mChunkSize objects because that’s

//more efficient than allocating each of them individually.

//Stores a pointer to the first element of the array in the mAllObjects

//vector. Adds a pointer to each new object to the mFreeList.

//

template <typename T>

void ObjectPool<T>::allocateChunk()

{

T* newObjects = new T[mChunkSize]; mAllObjects.push_back(newObjects); for (int i = 0; i < mChunkSize; i++) {

mFreeList.push(&newObjects[i]);

}

}

476

Writing Efficient C++

The destructor simply frees all of the arrays of objects that were allocated in allocateChunk(). However, it uses the for_each() STL algorithm to do so, passing it a pointer to the arrayDelete() static method, which in turn makes the actual delete call on each object array. Consult the STL chapters, Chapters 21 through 23, for details if this code confuses you.

//

//Freeing function for use in the for_each algorithm in the

//destructor

//

template<typename T>

void ObjectPool<T>::arrayDeleteObject(T* obj)

{

delete [] obj;

}

template <typename T> ObjectPool<T>::~ObjectPool()

{

// Free each of the allocation chunks. for_each(mAllObjects.begin(), mAllObjects.end(), arrayDeleteObject);

}

acquireObject() returns the top object from the free list, first calling allocateChunk() if there are no free objects.

template <typename T>

T& ObjectPool<T>::acquireObject()

{

if (mFreeList.empty()) { allocateChunk();

}

T* obj = mFreeList.front(); mFreeList.pop();

return (*obj);

}

Finally, releaseObject() returns the object to the tail of the free list.

template <typename T>

void ObjectPool<T>::releaseObject(T& obj)

{

mFreeList.push(&obj);

}

Using the Object Pool

Consider an application that is structured around obtaining requests for actions from users and processing those requests. This application would most likely be the middleware between a graphical front-end and a back-end database. For example, it could be part of an airline reservation system or an online banking application. You might want to encode each user request in an object, with a class that looks something like this:

477

Chapter 17

class UserRequest

{

public: UserRequest() {} ~UserRequest() {}

//Methods to populate the request with specific information

//Methods to retrieve the request data

//(not shown)

protected:

// Data members (not shown)

};

Instead of creating and deleting large numbers of requests throughout the lifetime of your program, you could use an object pool. Your program structure would then be something like the following:

UserRequest& obtainUserRequest(ObjectPool<UserRequest>& pool)

{

//Obtain a UserRequest object from the pool. UserRequest& request = pool.acquireObject();

//Populate the request with user input

//(not shown).

return (request);

}

void processUserRequest(ObjectPool<UserRequest>& pool, UserRequest& req)

{

//Process the request

//(not shown).

//Return the request to the pool. pool.releaseObject(req);

}

int main(int argc, char** argv)

{

ObjectPool<UserRequest> requestPool(1000);

//Set up program

//(not shown).

while (/* program is running */) {

UserRequest& req = obtainUserRequest(requestPool); processUserRequest(requestPool, req);

}

return (0);

}

478