Free-lists

Repeatedly calling malloc()/free() can become expensive. I have seen programs where, prior to optimization, over 30% of the time was spent in the C libraries memory management routines (i.e. malloc(),free(), and the functions they called).

One of the simplest ways of avoiding this overhead is to use free-lists.

Assume we have some type T that we decide to use free lists for. Assume the initial definition of the type includes the following fragments:


	/* T-private.h */
	struct T {
	  int	t_fld1;
	  int	t_fld2;
	  /* ... */
	};

	/* .. */
	#define x_fld1_T(_t)	(deref_T(_t)->t_fld1)
	#define x_fld2_T(_t)	(deref_T(_t)->t_fld2)

	/* T.c */
	T *
	make_T(
		/* ... */
		)
	{
	  T *	newT = xalloc(struct T);
	  /* ... */
	  return newT;
	}

	void
	destroy_T(
		T * ptrT
		)
	{
	  free(ptrT);
	}

Then, to create the free list, we modify the initial structure definition and its associated accessor macros.


	struct T {
	  union {
	    T*	t_next;
	    struct {
	      int	t_fld1;
	      /* ... */
	    } t_body;
	  } t_free;
	};

	/* ... */
	#define x_next_free_T(_t)	(deref_T(_t)->t_free.t_next)
	#define x_fld1_T(_t)		(deref_T(_t)->t_free.t_body.t_fld1)
	#define x_fld2_T(_t)		(deref_T(_t)->t_free.t_body.t_fld2)

And the corresponding implementation would be:


	static T * lcl_free_list_T = 0;

	T *
	make_T(
		/* ... */
		)
	{
	  T *	newT;
	  if( lcl_free_list_T ) {
	    newT = lcl_free_list_T;
	    lcl_free_list_T = next_free_T(newT);
	  }
	  else {
	    newT = xalloc(struct T);
	    /* we should also deal with the no memory left case */
	  }

	  /* ... */
	  return newT;
	}

	void
	destroy_T(
		T *	ptrT
		)
        {
	  x_lcl_next_free_T(ptrT) = lcl_free_list_T;
	  lcl_free_list_T = ptrT;
	}

Note that, even though we have changed the shape of struct T considerably, we don't have change any of the other functions of T, since the changes are all buried in the accessor macros.

We will also need a function to reclaim the free list in case we run out of memory.


	void
	reclaim_T( void )
	{
	  T *	p;
	  T *	q;
	  
	  for( p = lcl_free_list_T; p; p = q ) {
	    q = lcl_next_free_T(p);
	    xfree(struct T, p);
	  }
	}

There, obviously, has to also be a central function which will be called when an out-of-memory condition is encountered, which will call all the reclaim_ functions, and then retry the allocation.


The technique of using a union is the only one that is both standards compliant (and, hence, portable) and does not (in general) increase the memory required by a structure. However, there is another technique that should work in most cases, involving pointer casts. It does not require any changes to the struct. This is like using the above code but with x_lcl_next_free_T() defined as


	#define x_lcl_next_free_T(_t)	(*((T**)(_t)))

This is equivalent to:


	void
	make_T(
		/* ... */
		)
	{
	  T *	newT;
	  if( lcl_free_list_T ) {
	    newT = lcl_free_list_T;
	    lcl_free_list_T = *(T**)newT;
	  }
	  else {
	    newT = xalloc(struct T);
	  }

	  /* ... */
	  return newT;
	}

	void
	destroy_T(
		T *	ptrT
		)
	{
	  *(T**)ptrT = lcl_free_list_T;
	  lcl_free_list_T = ptrT;
	}


Next Prev Main Top Feedback