MicroQuill

All benchtests are not created equal

Benchtest programs for memory managers typically measure the time it takes a loop statement to allocate and free a lot of small blocks. Unfortunately, all benchtest programs are not created equal. Consider the following:

// define a struct
struct Node
{
   Node*	m_pNext;
   char	m_data[46];

   Node() : m_pNext(NULL) { memset(m_data, 0, sizeof(m_data)); }
   ~Node() { m_pNext = NULL; memset(m_data, -1, sizeof(m_data))
};
Node m_firstNode;

/* define a function that either allocates a list of 3,000 nodes 
or deletes the list, depending on whether m_pNext == NULL */
void HeapStuff(void)
{
   long numNodesToAlloc = 3000;
   if (m_firstNode.m_pNext == NULL)
   {
      for (Node* pNode = &m_firstNode; numNodesToAlloc > 0; numNodesToAlloc--)
      {
         pNode->m_pNext = new Node;
         pNode = pNode->m_pNext;
      }
   }
   else
      {
         while (m_firstNode.m_pNext != NULL)
         {
            Node* pNode = m_firstNode.m_pNext->m_pNext;
			delete m_firstNode.m_pNext;
			m_firstNode.m_pNext = pNode;
         }
     }
}
/* use a loop to make 1000's of calls to HeapStuff */
/* GET A START TIME HERE */
for (int heapIter = 0; heapIter < 15000; heapIter++)
   {
      HeapStuff();
   }
/* GET A STOP TIME HERE */
/* benchmark = (stop time - start time) */
}

The problem with this test case is that it does not at all rigorously test heap performance. It simply repeats the following trivial exercise:
  1. allocate 3000 50-byte blocks
  2. free all these blocks in the same order they were allocated
There is no variation in block size, no interspersal of allocs and frees, and no variation in the order of alloc or free; hence, there is no possibility of any heap fragmentation and the heap manager never has to search among free space for a suitably-sized free block. Allocators spend most of their time managing and searching free-lists -- tasks that are not required at all in this test case due to the homogeneous alloc pattern.

The fact that the compiler allocator is faster than the SmartHeap allocator for this test case simply means that the compiler allocator contains fewer instructions for the trivial task of advancing or retracting the end of the heap. A good benchtest should realistically emulate a real app's alloc pattern and put more stress on the allocator -- namely, variable-size allocs inspersed randomly with frees of randomly-chosen blocks.


Tech Support
MicroQuill home
HeapAgent
SmartHeap
Prices/ordering