Optimizing C++/Writing efficient code/Allocations and deallocations
Dynamic memory allocation and deallocation are very slow operations when compared to automatic memory allocation and deallocation. In other words, the heap is much slower than the stack.
In addition, dynamic allocation has a per-allocation overhead, causes virtual memory fragmentation, and causes bad data locality of reference, with the ensuing bad usage of both the processor data cache and virtual memory space.
Dynamic memory allocation/deallocation was performed in the C language using the malloc
and free
standard library functions.
In C++, although these functions are still available, the new
, new[]
, delete
, and delete[]
operators are normally used.
An obvious way to decrease the allocation count is to decrease the number of constructed objects and for that you should refer to the section "Constructions and destructions" in this chapter.
Here we concentrate on guidelines for decreasing the allocation count for a given number of new
operator calls.
Fixed length arrays
[edit | edit source]If a static or non-large array has compile-time constant length, instead of a vector
object, use a C-language array, std::array, or an array
object from the Boost library.
vector
s store data in a dynamically allocated buffer, whereas arrays allocate data inside the object itself.
This avoids repeated allocations/deallocations of dynamic memory and favors data locality.
If the array is large, such advantages are diminished and it becomes more important to avoid using too much stack space.
Allocating many small objects
[edit | edit source]If you have to allocate many objects of the same size, use a block allocator.
A block allocator (aka pool allocator) allocates medium to large memory blocks and provides a service to allocate/deallocate smaller, fixed-size blocks. It allows high allocation/deallocation speed, low memory fragmentation and efficient use of data caches and of virtual memory.
In particular, an allocator of this kind can greatly improve the performance of the std::list
, std::set
, std::multiset
, std::map
, and std::multimap
standard containers.
If your standard library implementation does not already use a block allocator for such containers, you should get one and specify it as a template parameter of instances of such container templates. Boost provides two customizable block allocators, pool_allocator
and fast_pool_allocator
. Other pool allocator libraries can be found on the World Wide Web. Always measure first to find the fastest allocator for the job at hand.
Appending elements to a collection
[edit | edit source]When you have to append elements to a collection, use push_back
to append a single element, use insert
to append a sequence of elements, and use back_inserter
to cause an STL algorithm to append elements to a sequence.
The push_back
functions guarantees an amortized linear time, as, in case of vector
s, it increases the capacity exponentially.
The back_inserter
class calls the push_back
function internally.
The insert
function allows a whole sequence to be inserted in an optimized way and therefore a single insert
call is faster than many calls to push_back
.