Resources:: MarsJupiter Family Shareware

MarsJupiter - Family shareware

Monday, 01 December 2008

A simple non standard allocator for C++ classes

The following code is for a non standard allocator, which like all non-standard allocators is geared towards some peculiarity of the calling code.

Of course this somewhat breaks the "purity" of the code, it ceases to be a transplantable blackbox capable of slotting into any project!

In this case we present an allocator for a class that expects many instances of itself to be allocated, but for the total number of allocations to periodically get back to zero. The code can be compiled in two version, one of which maintains a "free list" so that if the class gets frequently deallocated as well as allocated, the memory usage will not expand excessively. Alternatively you can compile without a free list, in which case when you delete an instance, that memory will not be resused again.

In our tests of using this in a real life product, we gained a 13.5% increase in processing speed without the free list, and 10% with the free list. Given that the code in question has quite a lot of work to do, aside from allocation, this is a pretty impressive increase.

Fragment of the DictionaryLetterArray.h file:



#ifdef NSA_DICTIONARY_LETTER_ARRAY

//

// Code for Non Standard allocator

//

#ifdef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST

#define NSA_DICTIONARY_LETTER_ARRAY_POOL_SIZE 50  // optimal pool size

	static CDictionaryLetterArray  *m_free_list;  // keep a free list



#else

#define NSA_DICTIONARY_LETTER_ARRAY_POOL_SIZE 150   // optimal pool size

	static int m_current_pool_pos;					// simply allocate from current pool

	static CDictionaryLetterArray  *m_current_pool; // current pool

#endif

	static void NewPool();

	static void FreePools();

	static int m_nsa_alloc_count;>				// keep track of instances allocated so we can free pools when zero

	static vectorm_pools;				// remember pool so we can free them

	static CComAutoCriticalSection m_thread_alloc_section; // use a critical section for thread safety

#ifdef DEBUG

	 void * operator new (size_t size/*,const char *file, int line*/)

#else

     void * operator new (size_t size)

#endif

    {	

        	m_thread_alloc_section.Lock();


			CDictionaryLetterArray *pItem;

#ifdef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST

			if (m_free_list)

			{

				// we use a linked list of free items

				// using the memory allocated to the class. Thus it is

				// essential that the class is at least void * in length.

				pItem = m_free_list;

	

				m_free_list = *((CDictionaryLetterArray **)m_free_list);

			}

			else

			{
				NewPool();

				pItem = m_free_list;

				m_free_list = *((CDictionaryLetterArray **)m_free_list);

	

			}

#else

			// if no free list simply return next in pool, creating new pools as needed

			if (m_current_pool_pos == 0)

			{

				NewPool();

			}

			pItem = (m_current_pool + m_current_pool_pos);

			m_current_pool_pos = (m_current_pool_pos +1) % NSA_DICTIONARY_LETTER_ARRAY_POOL_SIZE;


			
#endif	


			m_thread_alloc_section.Unlock();


			m_nsa_alloc_count++;

			return (void *)pItem;

    }


	void operator delete (void * mem)

    {

		CDictionaryLetterArray *pItem = (CDictionaryLetterArray *)mem;

      	m_thread_alloc_section.Lock();

	

#ifdef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST



		void **pFree = (void **)pItem;



		*pFree = m_free_list;



		m_free_list = pItem;

#endif

		m_nsa_alloc_count --;

		if (!m_nsa_alloc_count)

		{

			FreePools();

		}



		m_thread_alloc_section.Unlock();  

    }





#endif

A fragment of the DictionaryLetterArray.cpp file


#ifdef NSA_DICTIONARY_LETTER_ARRAY 

CComAutoCriticalSection CDictionaryLetterArray::m_thread_alloc_section; 

int CDictionaryLetterArray::m_nsa_alloc_count=0; 

vector  CDictionaryLetterArray::m_pools; 

 

#ifndef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST 

 

 

int CDictionaryLetterArray::m_current_pool_pos = 0; 

CDictionaryLetterArray  * CDictionaryLetterArray::m_current_pool = NULL; 

#else 

 

CDictionaryLetterArray * CDictionaryLetterArray::m_free_list = NULL; 

 

#endif 

 

void CDictionaryLetterArray::FreePools() 

{ 

 

 
	
	for (int i = 0; i < m_pools.size();i++) 

	{ 

		void *pPool = m_pools[i]; 

 

		free(pPool); 

	} 

	m_pools.clear(); 

 

#ifndef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST 

	m_current_pool_pos = 0; 

#else 

	m_free_list = NULL; 

#endif 

 

} 

 

void CDictionaryLetterArray::NewPool() 

{ 

	 

	CDictionaryLetterArray *pPool = (CDictionaryLetterArray *) malloc(NSA_DICTIONARY_LETTER_ARRAY_POOL_SIZE * sizeof(CDictionaryLetterArray)); 

 

	m_pools.push_back((void *)pPool); 

#ifdef NSA_DICTIONARY_LETTER_ARRAY_FREE_LIST 

 

	for (int i = 0; i < NSA_DICTIONARY_LETTER_ARRAY_POOL_SIZE; i++) 

	{ 

		CDictionaryLetterArray *pItem = (CDictionaryLetterArray *)(pPool + i); 

		void  **pFree = (void** )pItem; 

		*pFree = (void *)m_free_list; 

		m_free_list = pItem; 

 

	} 

 

	_ASSERT(m_free_list); 

#else 

	m_current_pool = pPool; 

#endif 

} 


 

#endif