Miscellaneous Topics

Suballocators

Memory managers have to suffer through the slings and arrows of not knowing when or how much memory will be requested by an application. There are, however, some circumstances where you will know in advance how large an application's memory requests will be or how many there will be. If this is the case, you can construct a dedicated memory manager known as a suballocator to handle memory requests and reap tremendous performance gains.

A suballocator is an allocator that is built on top of another allocator. An example of where suballocators could be utilized is in a compiler. Specifically, one of the primary duties of a compiler is to build a symbol table. Symbol tables are memory-resident databases that serve as a repository for application data. They are typically built using a set of fixed-size structures. The fact that a symbol table's components are all fixed in size makes a compiler fertile ground for the inclusion of a suballocator. Instead of calling malloc() to allocate symbol table objects, you can allocate a large pool of memory and use a suballocator to allocate symbol table objects from that pool.

The following source code implements the SubAllocator class and a small test driver:

#include
#include
#include

#define U4 unsigned long
#define U1 unsigned char

struct Indices
{
  U1 free;
  U4 index1;
  U4 index2;
  U4 index3;
};

class SubAllocator
{
  private:
  struct Indices *indices;
  U4 size;
  U4 lastAlloc;

  public:
  SubAllocator(U4 nElms);
  ~SubAllocator();
  struct Indices *alloc();
  void release(struct Indices *addr);
  void printList();
};

SubAllocator::SubAllocator(U4 nElms)
{
  U4 i;

  size = nElms;
  indices = (struct Indices*)malloc(size*(sizeof(struct
             Indices)));
  if(indices==NULL)
  {
      printf("SubAllocator::SubAllocator(%lu) :",size);
      printf("could not allocate list\n");
      exit(1);
  }

  for(i=0;i
  {
      indices[i].free =TRUE;
  }

  lastAlloc = 0;
  return;

} /*end constructor-----------------------------------------------*/

SubAllocator::~SubAllocator()
{
  free(indices);
  return;

} /*end destructor-----------------------------------------------*/

struct Indices* SubAllocator::alloc()
{
  U4 i;
  if(lastAlloc==size-1){ lastAlloc=0; }

  for(i=lastAlloc;i
  {
      if(indices[i].free==TRUE)
      {
          indices[i].free=FALSE;
          lastAlloc = i;
          return(&indices[i]);
      }
  }

  for(i=0;i
  {
      if(indices[i].free==TRUE)
      {
          indices[i].free=FALSE;
          lastAlloc = i;
          return(&indices[i]);
      }
  }
  return(NULL);

}/*end alloc-----------------------------------------------*/

void SubAllocator::release(struct Indices *addr)
{
  //sanity check
  if((addr>=&indices[0])&&(addr<=&indices[size-1]))
  {
      (*addr).free=TRUE;
  }
  else
  {
      printf("SubAllocator::release():");
      printf("release failed, address out of bounds\n");
  }
  return;

}/*end release-----------------------------------------------*/

void SubAllocator::printList()
{
  U4 i;
  for(i=0;i
  {
      if(indices[i].free==FALSE)
      {
          printf("indices[%lu] ",i);
          printf("[%lu, ",indices[i].index1);
          printf("%lu,",indices[i].index2);
          printf("%lu]\n",indices[i].index3);
      }
      else
      {
          printf("indices[%lu]=FREE\n",i);
      }
  }
  return;

}/*end printList-----------------------------------------------*/

void main()
{
  U4 ticks1,ticks2;
  U4 nAllocations=1024;
  U4 i;
  SubAllocator *ptr;
  struct Indices **addr;

  ptr = new SubAllocator(nAllocations);
  addr = (struct Indices**)malloc(nAllocations*sizeof(struct
          Indices*));

  ticks1 = GetTickCount();

  for(i=0;i
  {
      addr[i] = (*ptr).alloc();
      if(addr[i]==NULL)
      {
          printf("addr[%lu]==NULL\n",i);
          exit(1);
      }
  }

  for(i=0;i
  {
      (*ptr).release(addr[i]);
  }

  ticks2 = GetTickCount();

  delete(ptr);
  free(addr);

  printf("msecs=%lu\n",ticks2-ticks1);

  return;

}/*end main-----------------------------------------------*/

When this application is executed, the following output is produced:

   msecs=0