Enhance your dynamic memory allocation in C++ with an undocumented MFC class (CFixedAlloc)

• Download C++ source code - 35.3 Kb

Contents

• Introduction
• Why use alternatives to malloc/free, new/delete
• Limitations of other alternatives
• Anatomy of CFixedAlloc
• How to use CFixedAlloc
• Visual C++ 2005 warnings
• Memory deallocation
• CFixedAlloc and inheritance
• The demo program
• Suggestions
• Conclusion
• Bibliography
• History

Anatomy of CFixedAlloc

Let's start by viewing the class declaration:

class CFixedAlloc
{
// Constructors
public:
    CFixedAlloc(UINT nAllocSize, UINT nBlockSize = 64);

// Attributes
    UINT GetAllocSize() { return m_nAllocSize; }

// Operations
public:
    void* Alloc();      // return a chunk of
                        // memory of nAllocSize
    void Free(void* p); // free chunk of memory
                        // returned from Alloc
    void FreeAll();     // free everything allocated
                        // from this allocator

// Implementation
public:
    ~CFixedAlloc();

protected:
    struct CNode
    {
        CNode* pNext;   // only valid when in
                        // free list
    };

    UINT m_nAllocSize;  // size of each block
                        // from Alloc
    UINT m_nBlockSize;  // number of blocks to
                        // get at a time
    CPlex* m_pBlocks;   // linked list of blocks
                        // (is nBlocks*nAllocSize)
    CNode* m_pNodeFree; // first free node
                        // (NULL if no free nodes)
    CRITICAL_SECTION m_protect;
};

As you can see, it is a very simple class. The first thing that we can notice is that the class provides thread safety with a critical section. Next, m_AllocSize contains the object size of the class that will be using its service, and m_blockSize specifies the number of objects each fixed block of memory can contain. Both data members are set at the construction. The remaining unknown is the mysterious CPlex pointer. I will not go in to the details of this class but just know that it is the class that does the actual CRT dynamic allocation calls. It only contains a pointer to another CPlex object in order to create a linked list of CPlex so its size is only 4 bytes. When allocating memory, it requests:

m_allocSize*m_blockSize+sizeof(CPlex)

If you are interested in knowing more about CPlex, I recommend you to read the book MFC Internals which discusses CPlex in more details. With this information, we can already compare the memory overhead difference between CRT and CFixedAlloc. By using CRT, you will have the CRT overhead for each object, while with CFixedAlloc, it is the CRT overhead plus the size of CPlex (4 bytes) divided by the number of allocated objects. When the number of objects is big, the memory overhead is very close to zero, and as you will see with the demo, it can make a huge difference of many MBs. Now, let's look more closely at the two more important CFixedAlloc functions:

void* CFixedAlloc::Alloc()
{
    EnterCriticalSection(&m_protect);
    if (m_pNodeFree == NULL)
    {
        CPlex* pNewBlock = NULL;
        TRY
        {
            // add another block
            pNewBlock = CPlex::Create(m_pBlocks,
                        m_nBlockSize, m_nAllocSize);
        }
        CATCH_ALL(e)
        {
            LeaveCriticalSection(&m_protect);
            THROW_LAST();
        }
        END_CATCH_ALL

        // chain them into free list
        CNode* pNode = (CNode*)pNewBlock->data();
        // free in reverse order to make it
        // easier to debug
        (BYTE*&)pNode +=
            (m_nAllocSize * m_nBlockSize) - m_nAllocSize;
        for (int i = m_nBlockSize-1; i >= 0; i--,
                     (BYTE*&)pNode -= m_nAllocSize)
        {
            pNode->pNext = m_pNodeFree;
            m_pNodeFree = pNode;
        }
    }
    ASSERT(m_pNodeFree != NULL); // we must have something

    // remove the first available node from the free list
    void* pNode = m_pNodeFree;
    m_pNodeFree = m_pNodeFree->pNext;

    LeaveCriticalSection(&m_protect);
    return pNode;
}

void CFixedAlloc::Free(void* p)
{
    if (p != NULL)
    {
        EnterCriticalSection(&m_protect);

        // simply return the node to the free list
        CNode* pNode = (CNode*)p;
        pNode->pNext = m_pNodeFree;
        m_pNodeFree = pNode;
        LeaveCriticalSection(&m_protect);
    }
}

In Alloc(), the code checks if the pool of free memory is empty, if it is then it creates a new block of memory (CPlex) and sets up a list of free nodes. It is interesting to note that there is no wasted space to place node information because it is placed directly into each block. Of course, in order for this scheme to work, m_nAllocSize must be bigger than sizeof(CNode). This is why it is checked in the constructor:

ASSERT(nAllocSize >= sizeof(CNode));

If you want to see the CRT code, with a glimpse of an eye, you can tell that CFixedAlloc is much lighter. From an algorithmic point of view, the main factor for this simplicity is because the memory block's size is fixed (thus the name of the class). In a heap that allows variable size allocation, after many allocations and deallocations, the heap gets fragmented and the heap code has to scan the heap once in a while to merge adjacent small free blocks into big ones to make an efficient use of memory. With my demo program, I got the allocation time shred by a factor of 4 to 5.

And finally, let me introduce to you macros that help to use CFixedAlloc with your classes:

// DECLARE_FIXED_ALLOC -- used in class definition
#define DECLARE_FIXED_ALLOC(class_name) \
public: \
    void* operator new(size_t size) \
    { \
        ASSERT(size == s_alloc.GetAllocSize()); \
        UNUSED(size); \
        return s_alloc.Alloc(); \
    } \
    void* operator new(size_t, void* p) \
        { return p; } \
    void operator delete(void* p) { s_alloc.Free(p); } \
    void* operator new(size_t size, LPCSTR, int) \
    { \
        ASSERT(size == s_alloc.GetAllocSize()); \
        UNUSED(size); \
        return s_alloc.Alloc(); \
    } \
protected: \
    static CFixedAlloc s_alloc \

// IMPLEMENT_FIXED_ALLOC -- used in class implementation file
#define IMPLEMENT_FIXED_ALLOC(class_name, block_size) \
CFixedAlloc class_name::s_alloc(sizeof(class_name), block_size) \

The DECLARED_FIXED_ALLOC() macro overloads the new and delete operators of your class and thus allows you to use CFixedAlloc with absolutely no code change. With the IMPLEMENT_FIXED_ALLOC(), this is where you specify the block size. To complete this section, I will add that you can find more information on this type of allocation scheme in the excellent book of Scott Meyer, Effective C++.

Page 1 2 3 4