A Pooling Memory Manager for C++

Kirit works for Motion Graphics Limited in London. He can be contacted at [email protected].

Raytracers make huge demands on memory. In the process of rendering a 96x128-pixel image, for instance, a ray-tracing program was allocating and deallocating small blocks of memory (between 20 and 100 bytes) millions of times, although the maximum memory needed at any one time was typically less than 11 KB; see Figure 1. Most implementations of new and malloc are not designed to cope with this many memory allocations and deallocations.

Applications such as raytracers can also have trouble detecting memory leaks. If a leak is introduced, the program can munch its way through 10 MB of memory, causing severe thrashing when the program starts to use virtual memory. Although the MFC debugging memory allocator I was using checked for memory leaks, it didn't work with the memory pooling that I had added. Consequently, I had to implement my own memory-allocation facility. In this article, I'll focus on the strategy and tools that I developed to handle dynamic-memory allocation in the process of writing an object-oriented raytracer.

A Memory Strategy

When first designing classes, a declaration of the Company and Address classes (see Example 1) makes it possible to store and retrieve addresses, as well as reuse the Address class in other places. Clearly, Company will contain an instance of each of the classes String and Address. This causes no problem until you want to add international addresses, where each address may have a slightly different format. In the U.S., you would store a zip code, while the U.K. requires a post code. Each address has a different format and should appear differently in dialog boxes and when printed. To do this, you could subclass Address for both U.S. and U.K. addresses, as in Example 2.

Because of the way C++ handles polymorphism, you would also need to change Company so that it uses a pointer to (rather than an instance of) the Address class (Example 3). This is not a trivial change. There is no longer an instance of Address in Company, but a reference--and this means you must now change every single line of code that uses the Company or Address classes so they will work properly!

You may argue that changing part of the object hierarchy is bound to create a need to change other parts of the code. This need not be the case, however. It is possible to design the class from the outset so that this sort of change does not mean reworking thousands of lines of code. Example 4 gives an alternative to the implementation in Example 1. In Example 4 you use object pointers at all times. When you find that more flexibility is needed in the address storage, then all you do is change the internal implementation of address to accommodate it. All the client objects are already using pointers.

This does lead to another problem: When designing the classes, you must consider what is going to happen to all these new instances you are creating. The strategy I use comes from considering the differences in Example 3 and Example 4 and remembering that the changes should remain transparent to all client objects.

To achieve this transparency, constructors and member functions that set values or command changes from a receiving object must pass pointers to new object instances, for which the receiver then becomes responsible. The only exception is when a pointer is declared as const. In this case, I assume that the function that constructs the object should keep hold of it.

The other element of the memory-management strategy involves querying messages. Whenever an object's state is questioned, a pointer to a new object containing the answer is returned, which the querying function is then responsible for deleting.

This approach strengthens the data hiding that you achieve through the use of objects, because you make no assumptions about any subclassing of the Address class. Neither do you assume anything about the storage of the address within instances of the Company class. Overall, this weakens the coupling between object classes, which allows reuse of objects in the long term.

Unfortunately, there is a caveat to this strategy involving the number of memory allocations: Every time an object wants to find or change the address of a customer instance, a new instance of Address must be created on the heap.

The Memory Manager

The memory-pooling strategy itself is straightforward. MemoryPool, an array of MemHeader pointers, is created by the PoolOn function. Due to the MemLink member's constant presence in the MemHeader, you can chain MemHeaders together into a simple list. Figure 2 shows the different forms of the structure. MemoryPool is just an array of these lists.

When a request for memory is generated, it is passed to ARAlloc (see the version implemented in mempool.cpp), which checks that the memory pool is turned on and that there is a memory block of the correct size in the memory pool. If both these conditions are met, the head of the list is removed and that memory block will be used to satisfy the request. If the pool is not on or there are no spare blocks of the correct size, one is taken from the operating system. Either way, the size of the memory block is written to the size part of the MemLink union just before the memory block is handed out.

When a block is freed, it is passed to ARFree. It finds the MemHeader associated with the memory block, through which it finds the size of the memory block. If the memory pool has been turned off, then the block is simply freed back to the operating system; if the pool is on, it is placed at the head of the correct list in the MemoryPool array.

Memory-Pooling Diagnostics

All of the diagnostics for the memory pool are controlled through the MEMDIAG symbol, which should be defined project wide whenever you do a debug compile. Table 1 describes the #defines at the beginning of mempool.cpp that control aspects of the manager that are important for both debug and release compiles. Table 2 gives descriptions of the symbols used only for debug compiles. Switching between options is usually just a matter of commenting out lines in mempool.cpp.

The header file is arranged so that all the debugging constructs automatically turn themselves off when MEMDIAG is not defined. This means that you can use the OUTP and ASSERT macros in your code and only have them produce compiled code when debugging. You can include support for the memory system by just including the header file in your implementation files.

Figure 2 shows the difference in the structures created by this conditional compilation. When the diagnostics are disabled, you only get a small overhead (usually four bytes on a 32-bit system) for each memory allocation.

To see how the conditional compilation works, look at one of the most useful diagnostics that the memory manager produces--file and line numbers for all leaked memory blocks.

To output this information, you need to first pass it on to the memory manager. Second, you must keep a separate record of all the blocks passed out and tick them off when they are returned. This will slow down each free because you must find the freed block among all the outstanding blocks of memory. Because of this performance hit, you usually use this diagnostic as a last resort.

In turning on this diagnostic, you don't want to have to recompile all the code after encountering a memory leak. Consequently, special macros in the header file map to two versions of the ARAlloc function. One ARAlloc is passed a pointer to the name of the file and line number of the allocation, as well as the size of the requested block. The other ARAlloc is only given the size. When you are not using the full memory tracking (controlled by the MEMTRACKING symbol), the three-argument version of ARAlloc calls the single-argument version. When MEMTRACKING is defined, it retrieves the start of the MemHeader block from in front of the returned memory block so that the filename and the line number will be stored in the header.

The single-argument version of ARAlloc and ARFree handle the other part of the work. When full-memory tracking is turned on, a second MemHeader list store (MemoryAlloced) is set up. Before the address of the requested memory block is returned, the MemHeader is placed on the head of the correct MemoryAlloced list and default values are given to the filename and line number; this is why you need two next pointers in Figure 2(a).

At this point, ARFree walks down this list until it finds the correct memory block, which is removed from the list and the hole plugged. Also check for blocks of memory allocated before the memory pooling was turned on, because they may not be in the list.

The final part of the story is in PoolOff, which must check through MemAlloced when the memory pool is finally turned off. It can now report the size, line number, and filename where the memory allocation took place.

Conclusion

Figure 1: The memory report from a 96x128-pixel render in the raytracer. Note the number of allocations handled (more than 2 million) and the amount of memory taken from the system (less than 11 KB) compared with the reuse of that memory (92.3 MB).

Pooling off 1. Alloced:      11222 (0.0Mb) Freed:   0 (0.0Mb)
Mem ARAllocs: 2283781 ARFrees: 2283781
bytes     allocs       hits      frees  left over
   14          4      47205      47209          0
   18          3          0          3          0
   22         75      71905      71980          0
   26          1          1          2          0
   30         51      73180      73231          0
   32          7     151042     151049          0
   38         34    1512071    1512105          0
   54          5     222752     222757          0
   82          4     140799     140803          0
  100          7      64537      64544          0
  134         38         60         98          0
Check total: alloc: 11222 (0.0Mb) hits: 96766114 (92.3Mb)

Example 1: Initial design of the Company and Address classes.

class Address {
   ...
   String    line1, line2, city;
   long      zip_code;
   ...
};
class Company {
   public:
   // Constructor
   Company( String aname, Address
          anAddress );
   // Get/Set address
   Address GetAddress( void );
   void SetAddress( Address
          newAddress );
   protected:
   String    name;
   Address   address;
};

class Address {
   ...
   String    line1, line2, city;
   ...
};
class AddressUS : public Address {
   ...
   long       zip_code;
   ...
};
class AddressUK : public Address {
   ...
   String     post_code;
   ...
};

class Company {
   public:
   // Constructor/Destructor
   Company( String aname, Address
          *anAddress );
   ~Company( void );
   // Get/Set address
   Address *GetAddress( void );
   void SetAddress( Address
          *newAddress );
   protected:
   String     name;
   Address    *address;
};

class Address {
   ...
   String     line1, line2, city;
   long       zip_code;
   ...
};
class Company {
   public:
   // Constructor/Destructor
   Company( String aname, Address
          *anAddress );
   ~Company( void );
   // Get/Set address
   Address *GetAddress( void );
   void SetAddress( Address
          *newAddress );
   protected:
   String     name;
   Address    address;
};

#define         Description

MEMALLOC        Defines how the memory is allocated whenever a
                 new block is needed.
MEMNOFREENULL   When defined, a NULL pointer is never freed or
                 <I>delete</I>d. This will remove a
                 check that is made on every <I>free</I>.
MEMLARGEALLOC   Allows allocation requests for blocks of memory
                 larger than <I>g_memory_size</I> to be
                 passed through the memory manager.
MEMALLNEW       When defined, new versions of global
                 <I>new</I> and <I>delete</I>
                 operators are defined that pass all memory
                 allocations through the memory pool. This
                 option is not compatible with MFC because it
                 defines its own global <I>new</I> and
                 <I>delete</I> operators.

#define        Description

MEMBOUNDS      Adds an 8-byte block to the beginning and the
                end of the memory block. If any of the bytes
                within this checking area have been changed,
                then the entire block is discarded.
MEMFREENULL    When not defined, reports every time a NULL
                pointer is <I>free</I>d.
MEMDOUBLEFREE  Adds a check for each <I>free</I> to
                make sure that the memory block has not been
                <I>free</I>d before.
MEMMINE        Adds a magic number in the memory header so that
                <I>ARFree</I> can check that the memory
                block was allocated by <I>ARAlloc</I>.
MEMTRACKING    Turns on the full memory-tracking service. Stores
                line numbers and filenames when known. To get
                this information for all <I>new</I>s,
                add <I>#define new</I> MEMTRACKNEW
                after you have included all header files and
                defined your classes.