Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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...

share|improve this question
1  
How would this avoid fragmentation? alloc 16 byte @ 0; alloc 16 byte @ 32; free 16 byte @ 0; alloc 12 byte @ 0; and you got a hole in which only a 4-byte allocation can fill. –  delnan Oct 10 '11 at 20:56
    
doubles are often 4 and 8 byte aligned -- it varies by platform/arch. –  justin Oct 10 '11 at 21:15
    
Related reading: en.wikipedia.org/wiki/Memory_alignment –  justin Oct 10 '11 at 21:19
    
@delnan: still, isn't that hole better than automatically creating holes by making everything 8-byte aligned? What I mean is this: alloc 4 byte @ 0, alloc 4 byte @ 8, alloc 4 byte @ 16, etc... we already have way more fragmentation when everything is 8-byte aligned, than in the counter-example you gave... –  Dark Templar Oct 11 '11 at 2:05

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.