Heaps: Why is there a tradeoff between amount of space occupied (fragmentation), and speed at which operations are carried out?

Question

Apparently, the two major judging criteria of the effectiveness of heaps are (1) how much we can minimize the amount of space it takes up and (2) how fast operations on the heap can be carried out, eg, malloc and free

But I was wondering how these two criteria were related, namely, why there is a 'tradeoff' and why a faster heap makes it difficult for a smaller heap in size.

Also, why does a particular allocation alignment need to exist (for instance 8- or 16- byte) when then word size is clearly 4 bytes? If you allocate an int and a double, can't it just be:

allocate int at location 0

then

allocate double at location 4

(and then somehow keep track of the fact that a double-word is located at this location)? Then we would eliminate a LOT of fragmentation within the heap...

Answer 1

Fragmentation comes from memory that is unusable. Dynamic allocation is similar to playing Tetris - if you play fast you end up with holes (fragmentation), and you can't predict what type block is going to fall down next. With dynamic allocation, you can't predict when and what memory is going to be freed - imagine playing Tetris where blocks disappear randomly! Also keep in mind that dynamic allocation may require allocating variable-sized blocks - Tetris would involve polynominos instead of tetrominos!

A bit on dynamic allocation techniques:

The way you described is fixed-size block allocation. It is usually implemented as a free list. The problem with this method is that it can't allocate different size blocks and it can lead to bad caching behavior.

One of the simplest ways to implement dynamic allocation is buddy memory allocation - implemented as a binary tree that satisfies the heap property. The problem with this method is that it has internal fragmentation. Internal fragmentation comes from using techniques that use predetermined blocks, usually powers of 2. This means that allocating 150 bytes would actually allocate a block of 256, wasting 106 bytes due to internal fragmentation.

Other methods try to minimize fragmentation, such as slab allocation. Slab allocation is primarily used for kernels, as it was designed to allocate small objects - it's not ideal for general purpose malloc.

Anyways, the point I'm getting to is that it all depends on the type of allocations you're doing. Operating systems don't know which allocation method would be best for a program, and that is why they choose one that balances speed with fragmentation. It's nearly impossible to have 0 fragmentation without constantly pushing data around, that's just the nature of dynamic allocation.

Answer 2

But I was wondering how these two criteria were related, namely, why there is a 'tradeoff' and why a faster heap makes it difficult for a smaller heap in size.

When a request comes in you have to decide where to allocate it. The fastest thing to do would just be to allocate it on the top of the heap but that would lead to insane memory wastage. Basically each memory location would only be used once over the course of the programs run.

So memory managers keep one or more lists of free blocks. Maintaining and searching these lists to find the best possible block takes time and leads to tradeoffs. Do you just use the first block that fits or do you keep looking in the hope you find an exact fit? Do you detect the case where two adjacent blocks are free and merge them into one larger free block?.

Also, why does a particular allocation alignment need to exist (for instance 8- or 16- byte) when then word size is clearly 4 bytes?

There are a few reasons.

1. The C standard requires that allocated memory blocks are aligned such that they meet the alignment requirements of all the standard types. So if your platform requires 8-byte alignemt for doubles and long longs then malloc must align it's blocks on an 8 byte boundary.
2. The memory manager must store metadata for both allocated (remember in C you can free a block without specifying it's size) and free blocks. Normal practice is to store this metadata alongside the block itself rather than having a seperate data structure. To ease merging of adjacent blocks it is desirable to allow an allocated block and a free block to be distinguished by inspecting the header at the start of the block.

Put these requirements together and it makes sense to have a data structure with two fields, each of pointer-size at the start of each block. One field specifies if the block is free and if-so what the next block in the free list is. The other field specifies the size of the block.