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 for #1 — others have handled that, in short, glibc does a fairly good job, and other mallocs may do better under various circumstances.

However, as for your second question: How will a custom one perform?

• In general, a hand-coded, low-level implementation of a free-list-allocator that is aware of the application's own usage patterns and needs will probably outperform a general-case algorithm like GNU libc provides;

• but you'll have to prove it by writing the thing.

There are some related answers at [Custom malloc for lots of small, fixed size blocks?](https://stackoverflow.com/questions/3622637/custom-malloc-for-lots-of-small-fixed-size-blocks), by the way.

You might also look at the representation of disc sector usage in various filesystem drivers, as they solve effectively the same thing — fixed-size blocks/sectors being allocated in pseudorandom intervals under various loads — whereas most malloc's are going to concentrate on being general-purpose.
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!