An effective algorithm to manage fixed length memory blocks
download the sample code (6K)The sample code shows how to implement this algorithm in Delphi and Java.
In this article, I will introduce a simple but very effective and useful algorithm to dynamically allocate and free fixed length memory blocks.
What is this algorithm for?
You can consider it as a memory management algorithm. However, this memory management is not for general purpose usage, it only manages to allocate and free memory blocks with same and fixed length. Such memory blocks can be records in same type, or objects in same type.
What is the benefit of this algorithm?
1, Fast. The time complexity of allocation and freeing is O(1).
2, Almost no fragment. The heap is allocated beforehand. And when the heap needs to grow, a big chunk is allocated.
3, Very low overhead. The overhead for each memory block is up to 4 bytes. And if the maximum block count is no bigger than 65536 or 256, the overhead can be reduced to 2 or even 1 bytes.
4, Very simple. Only the basic push and pop operation on a stack is required.
As you can see, due to the above benefits, this algorithm is very suit for limited resource system such like embedded system, J2ME, etc. It's also useful for managing huge amount of fixed length records or same type objects even in a rich resource environment such like a J2EE server.
Details of the algorithm:
1, Allocate a piece of large buffer to hold the actual data. Because we assume each memory block to manage is fixed length, we can make a buffer in size of (block length) * (initial block count).
To be simpler, I will call current maximum block count as "capacity".
2, Use a stack to maintain the free blocks information. The stack element type depends on the maximum count of the blocks, byte for maximum 256 blocks, word for 65536, int32 for 4G.
Now let's initialize the stack by pushing integer 0 to capacity - 1 to stack. These numbers are the indexes of which blocks are free.
3, When allocating a block, an index will be popped from the stack and returned. If the stack is empty, means memory is full, we must grow the heap or raise an error. The popped index is just a free block. When freeing a block, the index of the block to free will be pushed back to the stack and it become a new free block.
Figure below shows the stack transition when allocating or freeing occurs.
Note: the top most element it the stack top.
| initial state | after one block allocated | after two block allocated | after first block freed | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
|
|
|