In many real systems, size of memory and objects are not known and can not be determined statically and is mainly dependent on data set during run time. For example, a compiler for a programming language will maintain symbol tables and type information which is dynamically constructed by reading the source program where source program can be of any size. In fact, there are very few large programs (or none), not having dynamic memory allocation. Dynamically created data structures like trees, linked lists and hash tables (which can be implemented as arrays of linked lists) are key to the construction of many large software systems.

(Please note: HW implementation may have dynamic memory allocation as well but memory usage has to be calculated before hand because in HW, supporting true dynamic memory allocation is not possible. HW based Dynamic Memory Allocation will be explained in another article. Please visit Linked List Implementation in ASIC series for detailed implementation details.)

This article is performance comparison between various allocation schemes. Aim is not to provide comrehensive review/information on Dynamic Memory Allocation but to make reader aware of performance loss, resulting because of Dynamic Memory Allocation. Performance of following schemes are evaluated

• ANSI C Dynamic Allocation Scheme - malloc/free
• C++ Dynamic Allocation Scheme - new/delete
• ANSI C Records Collapsing - Combining multiple records in single entity
  
• ANSI C based Pool based Dynamic Memory Allocation Scheme

Memory allocation provides a way to dynamically create buffers and arrays. Dynamic means that the space is allocated in memory as the program is executing. On many occasions the sizes of objects will not be known until run time. For instance, the length of a string a user inputs will not be known prior to execution. The size of an array may depend on parameters unknown until program execution. Certain data structures such as linked lists utilize dynamic memory allocation.

In many cases large amounts of dynamically allocated memory is consumed by interconnected objects which are not themselves very large. The time consumed allocating objects can be minimized, but is unavoidable. A significant amount of processing time can also be consumed traversing the dynamic data structures and returning them to the system.

Each memory allocation/de-allocation request in software is very costly and significantly impacts performance. Many methods are proposed to reduce this performance loss. One technique is to use a pool based memory allocator. This pool based memory allocator can be made part of library itself to maintain the transparency. Compiler can also play tricks by rescheduling and lumping allocation and de-allocation requests together to improve performance. There are few high performance compilers available out there performing these tricks.

A pool based memory allocator allocates large blocks of memory and then allocates smaller objects from these blocks. When it is time to recover memory, the entire pool is deallocated at once. This usually involves returning only a few large memory blocks to the system. This greatly reduces the time consumed by memory recovery.