When you create automatic objects on the stack, the size of the objects and their lifetime is built right into the generated code, because the compiler knows the exact type, quantity, and scope. Creating objects on the heap involves additional overhead, both in time and in space. Here’s a typical scenario. (You can replace malloc( ) with calloc( ) or realloc( ).)

You call malloc( ), which requests a block of memory from the pool. (This code may actually be part of malloc( ).)

The pool is searched for a block of memory large enough to satisfy the request. This is done by checking a map or directory of some sort that shows which blocks are currently in use and which are available. It’s a quick process, but it may take several tries so it might not be deterministic – that is, you can’t necessarily count on malloc( ) always taking exactly the same amount of time.

Before a pointer to that block is returned, the size and location of the block must be recorded so further calls to malloc( ) won’t use it, and so that when you call free( ), the system knows how much memory to release.

The way all this is implemented can vary widely. For example, there’s nothing to prevent primitives for memory allocation being implemented in the processor. If you’re curious, you can write test programs to try to guess the way your malloc( ) is implemented. You can also read the library source code, if you have it (the GNU C sources are always available).