One important thing to keep in mind when crafting your own memory allocators is alignment.
Every processor has a "natural" alignment for each data-type. For instance, on many 32-bit microprocessors, char are aligned on byte boundaries, int are aligned on 4 byte boundaries, and double are aligned on 8 byte boundaries. Generally:
malloc() returns memory aligned to the worst case alignment of the
machine.
struct fields are padded so that if the start of the structure is
aligned for the worst case, then each field will be aligned at the
natural alignment for its type.
struct is padded so that if an array of the type
is allocated, all fields of all elements end up at their natural
alignment.
For example, consider the following type:
struct T {
char c;
double d;
int i;
};
The layout for this type is as follows:
-------------------------
|cc .. .. ..|.. .. .. ..|
-------------------------
|dd dd dd dd|dd dd dd dd|
-------------------------
|ii ii ii ii|++ ++ ++ ++|
-------------------------
The .. represent 7 bytes of padding to ensure that d is aligned to an 8 byte boundary. The ++ represent 4 bytes of padding added at the end so that the all fields d of an array of struct T will be aligned on 8 byte boundaries.
Anytime we craft a memory allocator, we have to make sure that we keep alignment requirements in mind.
To minimize the amount of memory used by a structure, we should declare fields of the structure in increasing order of size. For, instance if we reordered the fields of struct T as:
struct T {
char c;
int i;
double d;
};
In this case, the layout will be:
-------------------------
|cc .. .. ..|ii ii ii ii|
-------------------------
|dd dd dd dd|dd dd dd dd|
-------------------------
The total size of each element will be reduced to 16 bytes from 24 bytes.