Optimizing C++/Code optimization/Allocations and deallocations

From Wikibooks, open books for an open world
< Optimizing C++‎ | Code optimization
Jump to: navigation, search

Even using a very efficient allocator, the allocation and deallocation operations take a significant time, and often the allocator is not very efficient.

In this section some techniques are described to decrease the total number of memory allocations, and their corresponding deallocations. They are to be applied only in bottlenecks, that is after having measured that the large number of allocations has a significant impact on performance.

The alloca function[edit]

In non-recursive functions, to allocate variable-size but not large memory space, use the alloca function.

It is very efficient, as it allocates space on the stack.

It is a non-standard function, but it is available with many compilers for several operating systems.

It may be used even to allocate an array of objects having constructors, as long as the placement-new operator is called on the allocated space, but it shouldn't be used for an array of objects having a destructor or which, directly or indirectly, contain member variables having a destructor, as such destructors would never be called.

Though, it is rather dangerous, as, if called too many times or with a too big value, it overflows the stack, and, if called for objects having a destructor, it causes resource leaks. Therefore this function is to be used sparingly.

Move allocations and deallocations[edit]

Move before bottlenecks memory allocations, and after bottlenecks the matching deallocations.

Variable length dynamic memory management is much slower than automatic memory management.

Analogous optimization is to be done for operations causing allocations indirectly, as the copy of objects which, directly or indirectly, own dynamic memory.

The reserve function[edit]

Before adding elements to a vector or to a string object, call its member function reserve with a size big enough for most cases.

If objects are repeatedly added to a vector or string object, several costly reallocations are performed. To avoid such reallocations, it is enough to initially allocate the required space.

Keep vectors capacity[edit]

To empty a vector<T> x object without deallocating its memory, use the statement x.resize(0);; to empty it and deallocate its memory, use the statement vector<T>().swap(x);.

To empty a vector object, there also exists the clear() member function, but, the C++ standard does not specify whether or not this function preserves the allocated capacity of the vector.

If you are repeatedly filling and emptying a vector object, and thus you want to to avoid frequent reallocations, perform the emptying by calling the resize member function, which, according to the standard, preserves the capacity of the object. If instead you have finished using a large vector object, and you may not use it again or you are going to use it with substantially fewer elements, you should free the object's memory by calling the swap function on a new empty temporary vector object.

swap function overload[edit]

For every copyable concrete class T which, directly or indirectly, owns some dynamic memory, redefine the appropriate swap functions.

In particular, add to the class public member function having the following signature:

void swap(T&) throw();

and add the following non-member function in the same namespace that contains the class T:

void swap(T& lhs, T& rhs) { lhs.swap(rhs); }

and, if the class is not a class template, add also the following non-member function in the same file that contains the class T definition:

namespace std { template<> swap(T& lhs, T& rhs) { lhs.swap(rhs); } }

In the standard library, the swap function is called frequently by many algorithms. Such function has a generic implementation and specialized implementations for various types of the standard library.

If objects of a non-standard class are used in a standard library algorithm that calls swap on them, and the swap function is not overloaded, the generic implementation is used.

The generic implementation of the swap function causes the creation and destruction of a temporary object and the execution of two object assignments. Such operation take much time if applied to objects that own dynamic memory, as such memory is reallocated three times.

The ownership of dynamic memory may be even only indirect. For example, if a member variable is a string or a vector, or is an object that contains a string or vector object, the memory owned by these objects is reallocated every time the object that contains them is copied. Therefore, even in these cases the swap function is to be overloaded.

If the object doesn't own dynamic memory, the copy of the object is much faster, and however it is not noticeably slower than using other techniques, and so no swap overload is needed.

If the class is not copyable or abstract, the swap function must never be called on object of such type, and therefore also in these cases no swap function is to be redefined.

To speed up the function swap, you have to specialize it for your class. There are two possible ways to do that: in the same namespace of the class (that may be the global one) as an overload, or in the namespace std as a specialization of the standard template. It is advisable to define it in both ways, as, first, if it is a class template only the first way is possible, an then some compilers do not accept or accept with a warning a definition only in the first way.

The implementations of such functions must access all the members of the object, and therefore they need to call a member function, that by convention is called again swap, that does the actual work.

Such work consists in swapping all the non-static members of the two objects, typically by calling the swap function on them, without qualifying its namespace.

To put the function std::swap into the current scope, the function must begin with the statement:

using std::swap;