CODEWITHSUNDEEP
c
nikhil chaubey
nikhil chaubey

Reputation: 401

Avoiding malloc/free Overhead in structure allocations in C

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.

Upvotes: 5

Views: 1068

Answers (3)

Bo Persson
Bo Persson

Reputation: 92301

I think the point of the example might be that a Person object holds pointers to additional memory. We can see from the deallocatePerson function that there are 3 pointers to strings inside the struct:

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

It means that to construct a complete Person you need several calls to malloc (1 for the struct itself and 3 for the strings).

So by saving a complete struct, including its strings, one getPerson call replaces four calls to malloc. That makes it likely to save some execution time.

Otherwise, I would not be surprised if malloc/free internally holds a similar array or linked list of recently used memory blocks ready to be recycled. If you have just free'd a memory block of the correct size, a new call to malloc will likely locate that block very fast.

Had Person been a simple struct without pointers to additional storage, the local caching is not that likely to improve performance (but perhaps instead add overhead by doing a linear search).

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

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.

Upvotes: 7

Abhijit Pritam Dutta
Abhijit Pritam Dutta

Reputation: 5591

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.

Upvotes: 2

Related Questions