Question: Suppose we have some fixed-length data type such as a C struct:

```
struct T
{
    ...;
}

```

One way to allocate T would be:

```
T* create_t() { return (T*) malloc(sizeof(T)); }

```

and deallocate:

```
void destroy_t(T* t) { free(t); }

```

Under the hood malloc uses a memory allocation algorithm that deals with different size blocks in different ways.

Suppose we were writing a program that called create\_t and destroy\_t frequently and had very many T items allocated at once, (and in pseudo-random order).

Given that the memory required is of fixed size elements, is it possible to write a custom memory allocation scheme that is superior to the generic implementation of malloc.

For example we could preallocate a huge array with elements of size T and then use those, but what is the best method to keep track of which elements have been allocated and which haven't?

What algorithm does malloc on Linux end up using when called with a huge number of allocations of the same size?

Roughly how will the performance of this custom method compare to the generic malloc?

Answer: 
AS far as I know the memory management used is a kind of 'bucket' management.

`malloc` keeps the free memory segments in buckets and when called, tries to pass out one of the best fit blocks to the caller.

But just download the source of the libc and have alook yourself.

And writing memory management is quite tricky and a lot of effort has been put into the currently used algorithms. I do believe that it is very hard (especially as a single person) to come up with something better than all those guys did.
Q: Given that the memory required is of fixed size elements, is it possible to write a custom memory allocation scheme that is superior to the generic implementation of malloc.?

A: Maybe. It would probably be a nontrivial undertaking.

Any given OS is likely to have a different implementation of "malloc()". The standard for Linux (for example), is Gnu Libc. You can find the source here:

* <http://www.gnu.org/software/libc/>

'Hope that helps!