Reducing allocation overhead

Another large source of memory usage comes from the following types of allocation overhead:
User overhead
The actual data occupies less memory that what was requested by the user
Padding overhead
The fields in a structure are arranged in a way that the sizeof of a structure is larger than the sum of the sizeof of all of its fields
Heap fragmentation
The application takes more memory than it needs, because it requires contiguous memory blocks, which are bigger than chunks that the allocator has
Block overhead
The allocator actually takes a larger portion of memory than required for each block
Free blocks
All free blocks continue to be mapped to physical memory

User overhead usually comes from predictive allocations (often by realloc), which allocate more memory than required. You can either tune it by estimating the average data size, or if your data model allows it, after the growth of data stops, you can truncate the memory to fit into the actual size of the object.

The sections that follow provide techniques for reducing the four other types of overhead.