Importance of padding in Dynamic Memory Allocation

Question

I am trying to implement a heap (implicit free list with header/footer) and deciding on whether I should add padding to it. What are the tangible benefits of adding pads? I read that it somehow reduces fragmentation, but I don't really understand why this is the case. Moreover, I am interested in what kind of performance benefits I can get in terms of time.

Does this also help locality in my program and how does it help?

Should I pad the entire block to a format of say 4 or 8 byte multiple or should I pad my block excluding the header and footer.

Forgot to mention that this is a C implementation using unistd in linux.

Answer 1

I read that it somehow reduces fragmentation, but I don't really understand why this is the case.

This is correct. And it works because it sets a minimum size of the allocations. Let's say that you add padding so that each block is at least 1kB. This means that there will never be a situation where you free a piece of memory and that an allocation made after that will not fit into that newly freed memory, as long as the new allocation is at most 1kB.

You could easily see this effect for yourself with some simple experiments on a piece of paper. First have a block size equal to your total memory. Of course there will be no fragmentation, but you will waste a lot of memory. If the block size is half the size it's basically the same scenario, but less waste. When we have a block size that is one third of the total memory we first encounter fragmentation. And that will happen when the middle block is allocated.

In short, padding reduces fragmentation but requires more memory.

Should I pad the entire block to a format of say 4 or 8 byte multiple or should I pad my block excluding the header and footer.

If you implement it in a clever way, then you will be able so change the padding size by simply changing a variable. So find a way to measure problems and adjust the padding to your needs.

Does this also help locality in my program and how does it help?

This is trickier. It can go both ways and depends on the programs using the heap. But my gut feeling says that padding would probably decrease locality. If this is the case, this can impact performance because of cache misses.

Answer 2

klutt's answer gives the reason why you may want some (significant) padding. However, there is also a reason why you need a certain minimal amount of padding: Alignment.

The blocks of memory that your allocator dishes out are required to be usable with any data type, and many data types have some kind of alignment requirements. Usually, it's just that a misaligned data item makes accesses crawl along like a slug, but some data types may have a hard alignment requirement. For instance, a PPC CPU simply cannot load a vector (16 bytes) from an address that is not divisible by 16. These alignment requirements are highly platform specific.

As such, your allocator must align any memory address it returns to the largest alignment required by the CPU (16 bytes in the case of the PPC), and by consequence pad all memory blocks to this minimum quantum of memory.

It might even be a wise idea to pad memory allocations to full cache lines (64 bytes on X86-64, if I'm not much mistaken), but this is not a requirement.

From that minimal block size on, allocators typically pad allocations to the next power of two, or similar, to reduce the amount of different memory block sizes they need to handle.