Original Post
Helloooo, This is not really a question, I actually want to discuss. I was reading the Enginuity article and such and decided to write the memory manager using some of the ideas in the forum topic about the article series. I'm specifically referring the idea of reuse of old objects from the dead list. So i wrote some code, tested it out, and I wanted to share the results. Basically, the code overrides the new operator and fetches a pointer from a dead list if there is one instead of allocating memory. When an object is deleted it puts the pointer on the dead list. The driver program creates an STL list of pointers and loops through randomly choosing to either allocate memory and add it to this list, or delete memory from the list. The driver program also has a timer to see how fast this is happening. My first iteration was disappointing because i chose to use STL lists for the alive and dead lists which made the overloaded new and delete run about twice as slow as an unoverloaded new and delete. So I went back and implemented my own linked list functionality, and got a nice speed improvement. I found in my tests that the overridden new and delete run about 33% faster than normal allocation. Anyway, I hope that makes sense, heres the code: (To compare with regular allocation, just comment out the new operator new and operator delete) I wrote it in Dev-Cpp but i'm pretty sure it should also run in MSVC. In conclusion, thanks Superpig for the idea and such. Any thoughts? Ideas for optimization?
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <list>
#include <windows.h>
class Base
{
private:
static Base * s_AliveFront;
static Base * s_DeadFront;
Base * m_Prev, * m_Next;
public:
Base( )
{
}
~Base ( )
{
}
inline static void * operator new ( size_t size )
{
Base * mem;
// if dead list is not empty
if( s_DeadFront )
{
mem = s_DeadFront;
DeadListPopFront( );
}
// otherwise create new memory
else
{
mem = (Base *)::operator new( size );
}
AliveListPushFront( mem );
return mem;
}
inline static void operator delete ( void * p )
{
Base * mem = static_cast< Base * >( p );
AliveListErase( mem );
DeadListPushFront( mem );
}
inline static void AliveListPushFront( Base * p )
{
if( s_AliveFront )
{
p->m_Next = s_AliveFront;
s_AliveFront->m_Prev = p;
s_AliveFront = p;
s_AliveFront->m_Prev = 0;
}
else
{
s_AliveFront = p;
s_AliveFront->m_Next = 0;
s_AliveFront->m_Prev = 0;
}
}
inline static void DeadListPushFront( Base * p )
{
if( s_DeadFront )
{
p->m_Next = s_DeadFront;
s_DeadFront->m_Prev = p;
s_DeadFront = p;
s_DeadFront->m_Prev = 0;
}
else
{
s_DeadFront = p;
s_DeadFront->m_Next = 0;
s_DeadFront->m_Prev = 0;
}
}
inline static void DeadListPopFront( )
{
if( s_DeadFront )
{
if( s_DeadFront->m_Next )
{
s_DeadFront = s_DeadFront->m_Next;
s_DeadFront->m_Prev = 0;
}
else
{
s_DeadFront = 0;
}
}
}
inline static void AliveListErase ( Base * p )
{
if( p->m_Next )
{
p->m_Next->m_Prev = p->m_Prev;
}
if( p->m_Prev )
{
p->m_Prev->m_Next = p->m_Next;
}
else
{
if( p->m_Next )
{
s_AliveFront = p->m_Next;
s_AliveFront->m_Prev = 0;
}
else
{
s_AliveFront = 0;
}
}
}
static void Cleanup ( )
{
Base * ptr = s_AliveFront;
if( ptr )
while( ptr->m_Next )
{
ptr = ptr->m_Next;
::operator delete( ptr->m_Prev );
}
s_AliveFront = 0;
ptr = s_DeadFront;
if( ptr )
while( ptr->m_Next )
{
ptr = ptr->m_Next;
::operator delete( ptr->m_Prev );
}
s_DeadFront = 0;
}
static void StatusReport ( )
{
Base * ptr = s_AliveFront;
int count = 0;
if( ptr )
while( ptr->m_Next )
{
count++;
ptr = ptr->m_Next;
}
std::cout << "Alive: " << count << std::endl;
ptr = s_DeadFront;
count = 0;
if( ptr )
while( ptr->m_Next )
{
count++;
ptr = ptr->m_Next;
}
std::cout << "Dead: " << count << std::endl;
}
};
Base * Base :: s_AliveFront = 0;
Base * Base :: s_DeadFront = 0;
int main(int argc, char *argv[])
{
LARGE_INTEGER beforeTime, afterTime;
std::list< Base * > baseList;
int count = 0, totalTime = 0;
srand( time( NULL ) );
for( int i = 0; i < 500; i++ )
baseList.push_back( new Base ( ) );
while( !kbhit() )
{
QueryPerformanceCounter( &beforeTime );
for( int i = 0; i < 500; i++ )
for( int j = 0; j < 500; j++ )
for( int k = 0; k < rand() % 5; k++ )
if( rand() % 2 == 0 )
{
baseList.push_back( new Base ( ) );
}
else
{
if( !baseList.empty() )
{
Base * b = baseList.back( );
delete b;
baseList.pop_back( );
}
else
{
baseList.push_back( new Base ( ) );
}
}
QueryPerformanceCounter( &afterTime );
totalTime += afterTime.LowPart - beforeTime.LowPart;
count++;
std::cout << "Average Time: " << (int)( (float)totalTime / count ) << std::endl;
}
Base::StatusReport( );
Base::Cleanup( );
Base::StatusReport( );
system("PAUSE");
return EXIT_SUCCESS;
}
