Heap – Why Does a Heap Need to Allocate in 8-Byte Alignments?

The problem with stacks is that you can't "free" memory unless it is on top of the stack. For instance, say you allocated 3 things of varying sizes:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

The stack would have a on the bottom, b in the middle, and c on top. This becomes problematic if we want to free b:

free(b); // b is not on top! We have to wait until c is freed!

The workaround is to move all the data after b and shift if so that it comes after a. This works, but will require 5000000 copies in this case - something that will be much slower than a heap.

This is why we have a heap. While allocation may be slower than a stack (O(log n) vs O(1)), heaps allow freeing memory at an arbitrary location to be fast - O(log n), compared to a stack's O(n)

The idea is that one word of memory can be used as an address in the address space (i.e., a word is wide enough to hold a pointer). If an address were larger than a word, addressing would require multiple sequential words. That's not impossible, but is unreasonably complicated (and likely slow).

So, given an w-bit word, how many values can that word represent? How may addresses can it denote? Since any bit can take on two values, we end up with 2·2·2·…·2 = 2^w addresses. Addresses are counted starting by zero, so the highest address is 2^w - 1.

Example using a three-bit word: There are 2³=8 possible addresses:

bin: 000 001 010 011 100 101 110 111
dec:   0   1   2   3   4   5   6   7

The highest address is 2³-1 = 8 - 1 = 7. If the memory is an array of bytes and the address is an index to this array, then using a three-bit word we can only address eight bytes. Even if the array physically holds more bytes, we cannot reach them with a restricted index. Therefore, the amount of virtual memory is restricted by the word size.