My memory management solution

Version 2

Results first I think:

Code:

Debug:
  Mine: 2.328 seconds
  CRT: 1.406

Release:
  Mine: 0.875
  CRT: 0.031

Executing this:

Code:

int main( int argc, char* argv[] )
{
    char* mem = NULL;
    int i, k;
    clock_t start, end;

    start = clock();

    for ( i = 1; i < 100001; i++ )
    {
        mem = (char*) Allocate( i );
        Free( mem );
    }

    end = clock();
    std::cout << "Custom Delta: " << (float) ( end - start ) / (float) CLOCKS_PER_SEC << " s\n";

    start = clock();

    for ( i = 1; i < 100001; i++ )
    {
        mem = new char[i];
        delete[] mem;
    }

    end = clock();
    std::cout << "CRT Delta: " << (float) ( end - start ) / (float) CLOCKS_PER_SEC << " s\n";

    if ( _CrtDumpMemoryLeaks() )
        std::cout << "\nMemory leaked. Oh joy.\n";

    std::cin.get();

    return 0;
}

I've taken itsme86's advice as best I could and come up with this. Every block allocated is allocated to a size of <requested> + sizeof(block) (where block is a SMemBlock*). The address of block is written into the first sizeof(block) bytes and a pointer just past that address is returned to the caller.

In SMemBlock I've got the block size and (in debug builds) the __LINE__ and __FILE__ information.

I may as well just give you the code - doesn't need as much explaining as the last one:

Memory.h

Code:

#pragma once

struct SMemoryState
{
    unsigned long   mTotalAllocated;
    unsigned long   mBlockCount;
};

#ifdef _DEBUG
#define Allocate( bytes ) CMemory::MemAlloc( bytes, __LINE__, __FILE__ )
#else
#define Allocate( bytes ) CMemory::MemAlloc( bytes, NULL, NULL )
#endif

#define Free( pointer ) CMemory::MemFree( pointer )

class CMemory
{
public:
    CMemory();
    ~CMemory();

    static void* MemAlloc( size_t bytes, long line, const char* file );
    static void MemFree( void* p );

    SMemoryState GetMemoryState();

private:
    struct SMemBlock
    {
        long        mLine;
        const char* mFile;
        size_t      mSize;
    };

    static unsigned long   mAllocated;
    static unsigned long   mBlocks;

};

Memory.cpp

Code:

#include "stdafx.h"
#include "Memory.h"

unsigned long CMemory::mAllocated = 0;
unsigned long CMemory::mBlocks = 0;

////////
// ctor / dtor
//
CMemory::CMemory()
{

}

CMemory::~CMemory()
{

}

////////
// MemAlloc
//
void* CMemory::MemAlloc( size_t bytes, long line, const char* file )
{
    if ( bytes <= 0 )
        return NULL;

    SMemBlock* block = new SMemBlock;
    char* data = new char[bytes + sizeof(block)];

    memset( data, 0, bytes + sizeof(block) );
    block->mSize = bytes;

    if ( line && file )
    {
        block->mLine = line;
        block->mFile = file;
    }

    mAllocated += (unsigned long) bytes;
    mBlocks++;

    *(unsigned long*) data = *(unsigned long*) &block;

    return ( data + sizeof(block) );
}

////////
// MemFree
//
void CMemory::MemFree( void* p )
{
    SMemBlock* block;
    char* pt = (char*) p - sizeof(block);

    block = (SMemBlock*) *(unsigned __int64*) pt;

//#ifdef _DEBUG
//    printf( "\n[MemFree] Block size: %d\n", block->mSize );
//    printf( "[MemFree] File: %s\n", block->mFile );
//    printf( "[MemFree] Line: %d\n", block->mLine );
//#endif

    mAllocated -= (unsigned long) block->mSize;
    mBlocks--;

    if ( p )
        delete[] pt;

    delete block;
}

SMemoryState CMemory::GetMemoryState()
{
    SMemoryState state;

    memset( &state, 0, sizeof(SMemoryState) );
    state.mTotalAllocated = mAllocated;
    state.mBlockCount = mBlocks;

    return state;
}

I'm not entirely sure where I could make changes to squeeze out some more performance.

Another little speed-up trick I did was to keep a list of what you've called blocks in a linked list. The list would keep up to some configurable number of these blocks in the list. When a MemFree() is called it would check to see if the number of blocks in the list was less than the configurable amount and if it was it would just prepend it to the list instead of freeing the memory for it.

Then when you do MemAlloc() you just see if there are any blocks in that list and you can grab it from there instead of creating a new one. That way for most MemAlloc() calls you only have to do one new and for most MemFree() calls you only have to do one delete.

Something like:

Code:

SMemBlock* CMemory::AcquireBlock()
{
  SMemBlock* block;

  if(AvailableBlocks)
  {
    block = AvailableBlocks;
    AvailableBlocks = AvailableBlocks->next;
    numAvailableBlocks--;
  }
  else
    block = new SMemBlock;

  return block;
}

void CMemory::FreeBlock(SMemBlock* block)
{
  if(numAvailableBlocks == maxAvailableBlocks)
    delete block;
  else
  {
    block->next = AvailableBlocks;
    AvailableBlocks = block;
    numAvailableBlocks++;
  }
}

I believe the time needed for the function call and those 3 simple statements is much less than anything new and delete need to do internally.

Right I'll get to it.
I really should rename those SMemBlock's too since they, well, aren't.
Misleading.

EDIT: Ah thanks for the example

Holy hell that shaved off loads of time.

Memory.h

Code:

#pragma once

// TODO: Get rid of all this static-ness and have the macros work through a singleton instance

struct SMemoryState
{
    unsigned long   mTotalAllocated;
    unsigned long   mBlockCount;
};

#ifdef _DEBUG
#define Allocate( bytes ) CMemory::MemAlloc( bytes, __LINE__, __FILE__ )
#else
#define Allocate( bytes ) CMemory::MemAlloc( bytes, NULL, NULL )
#endif

#define Free( pointer ) CMemory::MemFree( pointer )
#define MemoryState CMemory::GetMemoryState()

struct SDbgInfo
{
    long        mLine;
    const char* mFile;
    size_t      mSize;

    SDbgInfo*   mNext;
};

class CMemory
{
public:
    CMemory();
    ~CMemory();

    static void Initialise();
    static void Shutdown();

    static void* MemAlloc( size_t bytes, long line, const char* file );
    static void MemFree( void* p );

    static SMemoryState GetMemoryState();

private:
    static SDbgInfo* AcquireFree();
    static void FreeInfo( SDbgInfo* info );
    static unsigned    mNumAvailBlocks;

    static SDbgInfo*        mDIHead;
    static unsigned long    mAllocated;
    static unsigned long    mBlocks;

};

Memory.cpp

Code:

#include "stdafx.h"
#include "Memory.h"

unsigned long CMemory::mAllocated = 0;
unsigned long CMemory::mBlocks = 0;
SDbgInfo* CMemory::mDIHead = NULL;
unsigned CMemory::mNumAvailBlocks = 0;

////////
// ctor / dtor
//
CMemory::CMemory()
{

}

CMemory::~CMemory()
{

}

////////
// Initialise
//
void CMemory::Initialise()
{
}

////////
// Shutdown
//
void CMemory::Shutdown()
{
    if ( mNumAvailBlocks )
    {
        SDbgInfo* walk = mDIHead;
        SDbgInfo* temp = NULL;

        temp = walk->mNext;
        delete walk;
    }
}

////////
// MemAlloc
//
void* CMemory::MemAlloc( size_t bytes, long line, const char* file )
{
    if ( bytes <= 0 )
        return NULL;

    char* data = new char[bytes + sizeof(SDbgInfo*)];
    SDbgInfo* block = AcquireFree();

    *(unsigned long*) data = *(unsigned long*) &block;

    return ( data + sizeof(SDbgInfo*) );
}

////////
// MemFree
//
void CMemory::MemFree( void* p )
{
    SDbgInfo* block;
    char* pt = (char*) p - sizeof(block);

    block = (SDbgInfo*) *(unsigned __int64*) pt;

//#ifdef _DEBUG
//    printf( "\n[MemFree] Block size: %d\n", block->mSize );
//    printf( "[MemFree] File: %s\n", block->mFile );
//    printf( "[MemFree] Line: %d\n", block->mLine );
//#endif

    mAllocated -= (unsigned long) block->mSize;
    mBlocks--;

    if ( p )
        delete[] pt;

    FreeInfo( block );
}

////////
// GetMemoryState
//
SMemoryState CMemory::GetMemoryState()
{
    SMemoryState state;

    memset( &state, 0, sizeof(SMemoryState) );
    state.mTotalAllocated = mAllocated;
    state.mBlockCount = mBlocks;

    return state;
}

////////
// AcquireFree
//
SDbgInfo* CMemory::AcquireFree()
{
    SDbgInfo* info;

    if ( mDIHead )
    {
        info = mDIHead;
        mDIHead = mDIHead->mNext;
        mNumAvailBlocks--;
    }
    else
        info = new SDbgInfo;

    return info;
}

////////
// FreeInfo
//
void CMemory::FreeInfo( SDbgInfo* info )
{
    if ( mNumAvailBlocks == 25 )
        delete info;
    else
    {
        info->mNext = mDIHead;
        mDIHead = info;
        mNumAvailBlocks++;
    }
}

You'll have to forgive the mess - been hacking at it for hours. Uncleanly hacking.

Is 25 a "good" limit do you think?
I'll play with it and see how it affects it.

Results:

Code:

Debug:
My Time: 0.031 seconds
CRT Time: 0.015 seconds

No memory leaks!
Press any key to continue

Release:
My Time: 0 seconds
CRT Time: 0.015 seconds

No memory leaks!

Interesting. 0 seconds. That's the first time I ran the release build so it's as much a surprise to me as it probably is to you.

EDIT: Just ran another release test, this time allocating and freeing 100000 blocks (ascending size 1-100001) and both came out at 0.078 seconds.

Is 25 a "good" limit do you think?

It all depends on the project you're using this for. The TinyMAZE server I built mine for had hundreds of allocations and deallocations every second so my limit was more like 250-500.

It might be good to include a public method called something like InitMemManager that accepts the limit from the calling function just to make it flexible.

Another good method would probably be EndMemManager that cleans up all the objects in that free list before the program closes. It could also probably handle the memory leak reporting.

Well the Shutdown() function is my cleanup but I haven't got it reporting leaks right now. Initialise doesn't do anything yet but t'will soon.

Thanks for all your help guys