Optimizing Custom Memory Allocators

Sebastien Marc

It all started innocently. We had just finished the implementation of an XP ( eXtreme Programming) iteration of our Linux financial risk engine and were doing some load testing. We had to handle tens of thousands of financial positions in a matter of minutes, so scalability was important. The first big report got through, but the engine shot up in memory to 500 MB. The second run worried me as the engine shot up to 700 MB for the same report. The third run was a disaster. The server swapped, spending most of its time in an I/O wait state and taking forever to compute the profit and losses of each position.

Our application was suffering from unacceptable memory fragmentation.

Fortunately C++ provides the tools to fight memory fragmentation: custom memory allocators. We began to implement custom allocators to map (mmap system call) critical chunks of memory needed during the computation of the report, and we decided to implement custom containers using these allocators. The solutions worked well. Memory went down at the end of each report, and the fragmentation disappeared. But the code was very inefficient. The required time for a report nearly doubled. After quantifying the engine on Solaris (a pity quantify does not exist on Linux), we realized most of the time was spent calling the destructors for the objects in our containers.

Below is code using part of the implementation of a specific container:

template <class T>
void destroyit(T* tPtr)
{
  tPtr->~T();
}

template <class Contained,
  unsigned int size>
class Container
{
public:
  Container()
      :holderPtr_(NULL), bytes_
        (size*sizeof(Contained))
    {
      holderPtr_ =
        (Contained*) mmap(0, bytes_,
          PROT_READ|PROT_WRITE,
          MAP_PRIVATE, zerofd, 0);
      // Use placement new to
      // initialize our objects.
      for(int i=0; i<size; i++)
        new (holderPtr_ + i) Contained();
    }
  virtual ~Container()
    {
      long nelements =
        bytes_ / sizeof(Contained);
      for(int i=0; i<nelements; i++)
        destroyit(holderPtr_ + i);
      munmap(holderPtr_,bytes_);
    }
  
private:
  Contained* holderPtr_;
  unsigned long bytes_;
};

{
  // Uses the heap
  std::auto_ptr<MyClass> mPtr
    (new MyClass());
  // Time to allocate prices. Do
  // it using  our container
  // because we do not want  to
  //fragment the heap when prices
  //are deleted.
  // Container holding a 100 prices.
  Container<PriceClass, 100> c;
  // Do other things.
}

That was great, but what about:

{
  // Container holding a 100 prices.
  Container<double, 100> c;
}

So, when the container goes out of scope, its destructor enters a dreadful loop, trying to call 100 destructors on each double! That's not a model of efficiency and was definitely the main performance bottleneck of our risk engine. (Believe it or not, this appears to be how the standard STL vector container on the latest sparcWorks compiler is implemented).

Here is the design challenge: how to design the container to call the destructors of contained classes but avoid entering a loop when your container contains fundamental data types.

Modern C++ design and some of the template techniques described by Alexandrescu will help. Fasten your seat belts, here is the code to handle the case of double. I'll then generalize the solution to other types.

Start by defining two static types:

struct Yes_type {};
struct No_type {};

I can then have the following functions:

template <class T>
void destroyit(T* tPtr, long bytes, No_type)
{
}

template <class T>
void destroyme(T* tPtr)
{
  tPtr->~T();
}

template <class T>
void destroyit(T* tPtr, long bytes, Yes_type)
{
  long nelements = bytes / sizeof(T);
  for(int i=0; i<nelements; i++)
    destroyme(tPtr + i);
}

Now the tricky part is to call the appropriate destroyit function in the destructor of the container. You can call the appropriate destroyit function by introducing yet another static type:

template <class T> struct Container_type_traits
{
  typedef Yes_type has_destructor;
};

struct Container_type_traits<double>
{
   typedef No_type has_destructor;
};

The destructor for the container is:

virtual ~Container()
{
  destroyit(holderPtr_, bytes_,
Container_type_traits<Contained>::has_destructor());
  munmap(holderPtr_,bytes_);
}

I can now complete the implementation by specializing Container_type_traits structures for all the types I know do not need their destructor to be called (all the basic types qualify).

You can generalize this approach to many different applications. This technique allowed me to reduce memory fragmentation while maintaining a high level of performance.

About the Author