|
|
Some C++ programs allocate a lot of small objects. If the objects were large, it would take a lot of time to affect all their memory. But because they are small, the time spent to allocate and free them is much greater than the time actually spent using them.
This problem is compounded by the fact that many memory allocators take longer to run when there are a lot of blocks of memory already in use. Thus the fraction of the total execution time taken by the allocator may well increase as the program is asked to handle larger inputs.
One way to reduce this overhead is to use a specialized allocation strategy for objects of a particular class: allocate a large chunk of memory from the system and parcel it out in little pieces. Because these pieces are all the same size, fragmentation within a big chunk becomes impossible and the pieces can be stored in a simple linked list. Allocation thus becomes simple and fast.