Avoiding malloc/free Overhead in structure allocations in C

Question

I am reading and experimenting pointers from this book,

http://shop.oreilly.com/product/0636920028000.do

In chapter 6 of this book under Avoiding malloc/free Overhead heading author is suggesting how to avoid malloc/free overhead when doing lots of structure memory allocations/deallocations.

Below is the way he wrote the functions,

#define LIST_SIZE 10
Person *list[LIST_SIZE];

void initializeList() 
{
    int i=0;
    for(i=0; i<LIST_SIZE; i++) 
    {
        list[i] = NULL;
    }

}

Person *getPerson() 
{
    int i=0;
    for(i=0; i<LIST_SIZE; i++) 
    {

        if(list[i] != NULL) 
        {
            Person *ptr = list[i];
            list[i] = NULL;
            return ptr;
        }
    }
    Person *person = (Person*)malloc(sizeof(Person));
    return person;
}

void deallocatePerson(Person *person) 
{
    free(person->firstName);
    free(person->lastName);
    free(person->title);
}

Person *returnPerson(Person *person)
{
    int i=0;
    for(i=0; i<LIST_SIZE; i++) 
    {
    if(list[i] == NULL) 
        {
            list[i] = person;
            return person;
        }
    }
    deallocatePerson(person);
    free(person);
    return NULL;
}

What I understood from his code, that he creates a memory pool array, pointing to struct person type and then initialize each array element with NULL.

Next we will get a memory from pool using getPerson function. This function, checks against !=NULL which I think will fail every time. So again it will be same, as doing malloc and memory is not getting assigned from the pool anytime.

1. Is my understanding correct?
2. Is this the way to handle overhead ?
3. What should be the correct way to do it? Any source/link would be appreciated.

Answer 1

Next we will get a memory from pool using getPerson function. This function, checks against !=NULL which I think will fail every time.

The check will fail every time as long as you continue calling getPerson repeatedly. However, if you do a mixture of getPerson and returnPerson, some NULL checks will succeed, because returnPerson puts non-NULL values into the array.

This observation is key to understanding the approach: the array serves as a small temporary storage for struct Person blocks that have been allocated with malloc, but are no longer in use. Rather than calling malloc again, your code grabs an available block from this special list, if there is one available.

In situations when you make thousands of allocations, but never keep more than LIST_SIZE objects active at any given time, the number of malloc calls is limited to LIST_SIZE.

Is this the way to handle overhead?

This is a variation on using lookaside lists, an optimization technique so important that Microsoft created an API for its use in driver code. A simpler approach would use Person *list[LIST_SIZE] as a stack of released blocks, i.e. with the index of the last released block and no loop.

Another approach would be to set up a linked list of such blocks, reusing the memory of the block itself to store the next pointer. This technique may be too complex for an introductory boo, though.

Answer 2

First of all what your writer referring to overhead here? For dynamic memory allocation we call malloc to allocate memory and free to release the memory. Also during this process Operating System need to search for available memory from heap and allocate the same as well. To avoid this overhead, he is just suggesting that at the very beginning when your application load and if you know the frequency of probable dynamic memory allocation to a struct, you can in advance reserved a pool of memory which will reduce allocation and deallocation of memory overhead significantly. That is true to a certain extent, if your server is already running a lots of application and processors are very busy you can go for this kind of approach. But there are drawbacks as well. In this case you already reserved a pool of memory from your heap in advance. If not utilized properly it will leads to poor memory management.