Dynamic allocation of fixed-sized type

2
votes

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?

4
clinuxmemorymemory-managementmalloc
Sounds like you're on the verge of thinking up a free list. You use the space of an empty memory block to hold a pointer to the next free memory block. In this way, you create an in-place linked-list of free memory blocks. There are more advanced schemes from here. - GManNickG
On Windows yes (excepting the new concurrency CRT), on everything else probably not. - Steve-o

4 Answers

3
votes

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?, 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.

2
votes

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.

2
votes

First, you can have several implementations of malloc. For instance, Glibc malloc (explained here) is here, but musl libc malloc is here. And the variety of C dynamic memory implementation is well known.

Notice also that an implementation as simple as 

void *malloc (size_t sz)
{
   errno = ENNOMEM;
   return 0;
}

is probably conformant to the letter, but not the spirit, of the standard specification of malloc (e.g. in Posix, and in C99).

In reality, malloc is implemented by asking the Linux kernel some memory chunks thru syscalls like mmap(2) and munmap(2) and sometimes sbrk(2) which are all related to virtual memory and address space. Because of ASLR the result of malloc might be different from one run of your program to the next. malloc is able to deal with many allocations of the same size, but you could end up with memory fragmentation on very long running programs.

you could also use e.g. a slice allocator like in glib memory slices, but it might be rarely useful. You could also use Boehm's conservative garbage collector (e.g. use GC_malloc instead of malloc and not bother free-ing explicitly your data).

In practice, on Linux, malloc works quite well. I don't think you should bother with it. Of couse it is designed to minimize the memory allocation low-level operations like mmap (which are expensive; a good malloc implementation manages well a pool of memory and try re-using free-d memory before asking it from the kernel). There are also issues related to multi-threading, etc.

Before bothering about the decreasing the cost of malloc in your application you should measure it (and valgrind is useful, also to debug malloc related bug). Very often, the cost of malloc is not that important in an application. If you really want, you could manage your own memory arena, but I am not sure you should bother. (Measure first before optimizing). On today's machines, cache considerations are also dominant on the actual performance of your code.

0
votes

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:

'Hope that helps!