Optimizing C++/Writing efficient code/Allocations and deallocations
From Wikibooks, the open-content textbooks collection
Dynamic memory allocation and deallocation are very slow operations, compared with automatic memory allocation and deallocation. In other words, the heap is much slower than the stack.
In addition, such kind of allocation causes a per-allocation overhead, causes virtual memory fragmentation, and causes bad data locality of reference, with ensuing bad usage of both processor data cache and virtual memory space.
Dynamic memory allocation/deallocation was performed in C language using the malloc and free standard library functions. In C++, although such functions are still available, usually for such purpose the new, new[], delete, and delete[] operators are used.
Obviously, a way to decrease the allocation count is to decrease the number of constructed objects, and therefore the section "Constructions and destructions" in this chapter is indirectly useful also for the purpose of this section.
Yet, here guidelines are presented to decrease the allocations count for a given number of new operator calls.
[edit] Fixed length arrays
If a static or non-large array has compile-time constant length, instead of a vector object, use a C-language array or an array object from the Boost library.
vectors store the data in a dynamically allocated buffer, while the other solutions allocate data inside the object itself. This allows to avoid allocations/deallocations of dynamic memory and favor data locality.
If the array is large, such advantages are diminished, and instead it becomes more important to avoid to use too much stack space.
[edit] Allocating many small objects
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 the service to allocate/deallocate fixed size smaller blocks. It allows high allocation/deallocation speed, low memory fragmentation, an efficient usage of data caches and of the virtual memory.
In particular, an allocator of this kind can greatly improve the performance of the std::list, std::set, std::multi_set, std::map, and std::multi_map standard containers.
If your standard library implementation do not already use a block allocator for such containers, you should get one and specify it as template parameter of the instances of such containers 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.
[edit] Appending elements to a collection
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 append elements to a sequence.
The push_back functions guarantees an amortized linear time, as, in case of vectors, it increases exponentially the capacity.
The back_inserter class calls internally the push_back function.
The insert function allows to insert a whole sequence in an optimized way, and therefore a single call to it is faster than many calls to push_back.
