Clever memory management with constant time operations?

Let's consider a memory segment (whose size can grow or shrink, like a file, when needed) on which you can perform two basic memory allocation operations involving fixed size blocks:

• allocation of one block
• freeing a previously allocated block which is not used anymore.

Also, as a requirement, the memory management system is not allowed to move around currently allocated blocks: their index/address must remain unchanged.

The most naive memory management algorithm would increment a global counter (with initial value 0) and use its new value as an address for the next allocation. However this will never allow to shorten the segment when only a few allocated blocks remain.

Better approach: Keep the counter, but maintain a list of deallocated blocks (which can be done in constant time) and use it as a source for new allocations as long as it's not empty.

What next? Is there something clever that can be done, still with constraints of constant time allocation and deallocation, that would keep the memory segment as short as possible?

(A goal could be to track the currently non-allocated block with the smallest address, but it doesn't seem to be feasible in constant time…)

• wouldn't the checking of a list be not of constant-time anymore, as the list might grow or shrink due to some allocations/disallocations done previously?
– Sim
Mar 6, 2012 at 21:58
• @Sim, I was assuming it's a linked list and with it the operations would be $\mathcal{O}(N)$, because you always work only with the head. Mar 6, 2012 at 22:09
• I think your “better approach” will already use optimal amount of memory, i.e. it will never allocate additional memory if there is a free block. How do you imagine the “clever” approach would improve on that? Do you mean that it should allocate close to the beginning so that there is a better chance that you can shrink the segment after deallocations? Mar 6, 2012 at 22:11
• @Sim: Sorry, maybe I should have used the term stack (but I thought it could be confusing), 'deallocate' is push and 'allocate' is pop, or in the case it fails just fall back to the counter incrementation. Both are constant time. Mar 6, 2012 at 22:12
• Do you have real time constraints, or are you fine with amortized constant time? The answers are likely to be pretty different. Mar 6, 2012 at 22:15

3 Answers

With fixed-size blocks, what you have described is a free list. This is a very common technique, with the following twist: the list of free blocks is stored in the free blocks themselves. In C code, it would look like this:

static void *alloc_ptr = START_OF_BIG_SEGMENT;
static void *free_list_head = NULL;

static void *
allocate(void)
{
void *x;

if (free_list_head == NULL) {
x = alloc_ptr;
alloc_ptr = (char *)alloc_ptr + SIZE_OF_BLOCK;
} else {
x = free_list_head;
free_list_head = *(void **)free_list_head;
}
return x;
}

static void
release(void *x)
{
*(void **)x = free_list_head;
free_list_head = x;
}


This works well as long as all allocated blocks have the same size, and that size is a multiple of the size of a pointer, so that alignment is preserved. Allocation and deallocation are constant-time (that is, as constant-time as memory accesses and elementary additions -- in a modern computer, a memory access can involve cache misses and even virtual memory, hence disk accesses, so the "constant time" can be quite big). There is no memory overhead (no extra per-block pointers or things like that; the allocated blocks are contiguous). Also, the allocation pointer reaches a given point only if, at one time, that many blocks had to be allocated: since the allocation prefers using the free list, the allocation pointer is increased only if the space below the current pointer is clock full. In that sense, this is an optimal technique.

Decreasing the allocation pointer after a release can be more complex, since free blocks can be reliably identified only by following the free list, which goes through them in unpredictable order. If decreasing the big segment size when possible is important to you, you could want to use an alternate technique, with more overhead: between any two allocated blocks, you put a "hole". The holes are linked together with a doubly-linked list, in memory order. You need a data format for a hole such that you can locate the hole start address by knowing where it ends, and also the hole size if you know where the hole begins in memory. Then, when you release a block, you create a hole which you merge with the next and the previous holes, rebuilding (still in constant time) the ordered list of all holes. The overhead is then about two pointer-sized words per allocated block; but, at that price, you can reliably detect the occurrence of a "final hole", i.e. an occasion to decrease the big segment size.

There are many possible variations. A good introductory paper is Dynamic Storage Allocation: A Survey and Critical Review by Wilson et al.

• How do you find the holes nearest to a deallocation site in constant time?
– Raphael
Mar 7, 2012 at 6:49
• In the second method I describe, a hole is a header (a pair of pointers, for the list of holes) along with space for zero, one or more data blocks. Between any two allocated blocks, there is always a hole, even if it is a micro-hole consisting of only a hole header. So locating the nearest holes is easy: they are right before and right after the slot. Of course, micro-holes are not made part of the free list (the list of holes eligible for allocation). Another way to view it is that you add a header to every block and every (non-micro) hole (allocation under 16-bit Ms-Dos worked like that). Mar 7, 2012 at 12:05

This answer is about generic memory management techniques. I missed that the question asks about the case where all blocks have the same size (and are aligned).

The basic strategies you should know are first-fit, next-fit, best-fit, and the buddy system. I wrote a short summary once for a course I taught, I hope it's readable. I point there to a fairly exhaustive survey.

In practice you'll see various modifications of these basic strategies. But none of these is really constant time! I don't think that's possible in the worst case, while using a bounded amount of memory.

• Interesting, I have to read this in details. However, it seems that these systems deal specifically with non-constant size allocations, which is not a issue I'm confronted with. Mar 6, 2012 at 22:53
• Right. Sorry, I read way too fast your question. Mar 6, 2012 at 23:05
• OK, just one comment before I go to sleep: I think you must allocate the smallest free block if you want to keep the shortest possible segment for all possible sequences of operations. So, the only improvement that comes to mind is to use a heap instead of your list, but that's going to be $O(\lg n)$, not constant. Mar 6, 2012 at 23:21
• s/smallest free block/free block at smallest address/ Mar 6, 2012 at 23:28

You may want to have a look at amortized analysis and in particular dynamic arrays. Even if the operations are not really done in constant time at every step, in the long run it looks like it is the case.

• And how exactly will dynamic arrays help with allocating memory? Mar 6, 2012 at 22:14
• You would (de)allocate chunks of contiguous cells using the same kind of algorithm? Your whole file would be a linked list of bigger and bigger chunks. Mar 6, 2012 at 23:03