C allocation and memory overhead

Question

Apologies if this is a stupid question, but it's been kinda bothering me for a long time.

I'd like to know some details on how the memory manager knows what memory is in use.

Imagine a one-chip microcomputer with 1024B of RAM - not much to spare.

Now you allocate 100 ints - each int is 4 bytes, each pointer 4 bytes too (yea, 8bit one-chip will most likely have smaller pointers, but w/e).

So you've just used 800B of ram for 100 ints? But it's worse - the allocation system must somehow take note on where the memory is malloc'd and where it's free - 200 extra bytes or something? Or some bit marks?

---

• If this is true, why is C favoured over assembler so often?

• Is this really how it works? So super inefficient?

• (Or am I having a totally incorrect idea about it?)

Answer 1

It may surprise younger developers to learn that greying old ones like myself used to write in C on systems with 1 or 2k of RAM.

In systems this size, dynamic memory allocation would have been a luxury that we could not afford. It's not just the pointer overhead of managing the free store, but also the effects of free store fragmentation making memory allocation inefficient and very probably leading to a fatal out-of-memory condition (virtual memory was not an option).

So we used to use static memory allocation (i.e. global variables), kept a very tight control on the depth of function all nesting, and an even tighter control over nested interrupt handling.

When writing on these systems, I didn't even link the standard library. I wrote my own C startup routines and provided custom minimal I/O routines.

One program I wrote in a 2k ram system used the lower part of RAM as the data area and the upper part as the stack. In the final cut, I proved that the maximal use of stack reached so far down in memory that it was 1 byte away from the last variable in the data area.

Ah, the good old days...

EDIT:

To answer your question specifically, the original K&R free store manager used to add a header block to the beginning of each block of memory allocated via malloc.

The header block looked something like this:

union header {
    struct {
    union header   *ptr;
    unsigned        size;
    } s;
};

Where ptr is the address of the next header block and size is the size of the memory allocated (in blocks). The malloc function would actually return the address computed by &header + sizeof(header). The free function would subtract the size of the header from the pointer you provided in order to re-link the block back into the free list.