My memory management solution

Now let me just say that I know this solution is far from ideal and also that I've read very little on the subject. I'm curious to see what I can come up with myself :)

A singly linked list of these is managed (it's not an STL list):

Code:

---

struct MemBlock_t
{
    bool        mFree;
    MemBlock_t* mNext;
    size_t      mSize;
    char*      mData;
};

---

When an allocation request is made, the list is searched for a MemBlock_t that is marked as free (mFree) and whose size exactly matches the requested amount (in bytes). If no such block exists, a new one is created, setup and linked in.

Calling the free function searches the list for the correct block (more on that in a mo') and simply marks it as free.

Yeah, the searching during a free... at the moment I've got it simply comparing the pointer passed with the mData of each block. It's working fine so far and in all of the tests I've run, but would it be better to allocate 4 extra bytes at the start of each mData block and write a UID there (unsigned long), then use that to compare? Help me out here.

The destructor for the CMemory object iterates the list and destroys each node. Later on I'll have it throw out a warning if any of the blocks were marked as !mFree too.

Oh and yeah, I'm not going to keep all of this code in the ctor / dtor when I put it into my engine (this is a seperate project so I can work on this object alone :)) - I'll write Initialise() / Shutdown()'s.

I did want to work it so that if a block larger than the request is found, it's split and two new blocks are constructed in it's place - is it worth doing that? It's no trouble, but I'm worried about fragmentation.

Then again, with the current method, I'm thinking that there could well be a helluva lot of blocks unused a lot of the time, but then again I could write a CollectGarbage() function to free the mData of any blocks marked as mFree. CollectGarbage() wouldn't actually remove them from the list though, just make it so that if the block is chosen to satisfy a request later on, the allocator needs to allocate it again. Should take the edge off the memory usage, right?

Anyway I'm starting to ramble - take a look at it all. Feel free to shoot me some constructive criticism. You can use it if you want, too ( make sure you tell me so I get that warm fuzzy feeling :p )

Memory.h

Code:

---

#pragma once

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

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

    void* MemAlloc( size_t bytes );
    void* MemAllocZero( size_t bytes );
    void MemFree( void* ptr );

    MemoryState_t GetMemoryState();
    void DumpMemoryBlocks();

private:
    struct MemBlock_t
    {
        bool        mFree;
        MemBlock_t* mNext;
        size_t      mSize;
        char*      mData;
    };

    MemBlock_t* mBlocksHead;

};

---

Memory.cpp

Code:

---

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

////////
// ctor / dtor
//  dtor: Walk the list and free all mData memory if t'was allocated, then the node itself.
//
CMemory::CMemory()
{
    MemBlock_t* dummy = NULL;

    mBlocksHead = dummy;
}

CMemory::~CMemory()
{
    MemBlock_t* walk = mBlocksHead;
    MemBlock_t* temp = NULL;

    while ( walk )
    {
        if ( walk->mData )
        {
            delete[] walk->mData;
            std::cout << "Just freed " << static_cast<unsigned>( walk->mSize ) << " bytes of data\n";
        }

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

////////
// MemAlloc
//  Scan the block list for a block that's big enough to satisy @bytes.
//  If no allocated block can satisfy @bytes,
//  a new block of the correct size is allocated.
//
void* CMemory::MemAlloc( size_t bytes )
{
    MemBlock_t* walk = mBlocksHead;

    // Scan for big enough block
    while ( walk )
    {
        if ( walk->mSize == bytes && walk->mFree )
        {
            // Perfect match. Clear the data and return a pointer to it.
            memset( walk->mData, 0, walk->mSize );
            return static_cast<void*>( walk->mData );
        }

        walk = walk->mNext;
    }

    // If we get here, no block can satisfy @bytes
    // so allocate a new one and link it in
    MemBlock_t* block = new MemBlock_t;

    if ( !block )
        return NULL;

    block->mData = new char[bytes];
    block->mFree = false;
    block->mSize = bytes;

    // Link it in
    block->mNext = mBlocksHead;
    mBlocksHead = block;

    return static_cast<void*>( block->mData );
}

void* CMemory::MemAllocZero( size_t bytes )
{
    return NULL;
}

////////
// MemFree
//  Finds the block associated with @ptr and marks it
//  as free.
//
void CMemory::MemFree( void* ptr )
{
    MemBlock_t* walk = mBlocksHead;
    MemBlock_t* temp = NULL;
    bool found = false;

    // Find it and mark it
    while ( walk )
    {
        if ( walk->mData == ptr )
        {
            found = true;
            printf( "Found it\n" );
            walk->mFree = true;
        }

        walk = walk->mNext;
    }

    if ( !found )
    {
        // Even though ptr could be a naked pointer ( and valid )
        // if it's not in the block list, it's invalid as far as this
        // manager is concerned
        std::cout << "\nMemFree: Invalid pointer given\n";  // Would probably be an exception in the engine
    }
}

MemoryState_t CMemory::GetMemoryState()
{
    MemoryState_t state;
    MemBlock_t* walk = mBlocksHead;
    unsigned long totalSz = 0;
    unsigned long blocks = 0;

    memset( &state, 0, sizeof(MemoryState_t) );

    while ( walk )
    {
        totalSz += static_cast<unsigned long>( walk->mSize );
        blocks++;
        walk = walk->mNext;
    }

    state.mBlockCount = blocks;
    state.mTotalAllocated = totalSz;

    return state;
}

void CMemory::DumpMemoryBlocks()
{
    MemBlock_t* walk = mBlocksHead;

    while ( walk )
    {
        printf( "\nBlock Data\n\n" );
        printf( "Size: %d\n", walk->mSize );
        printf( "Data: %s\n", walk->mData );

        walk = walk->mNext;
    }
}

---

EDIT (I knew I'd forget something): According to _CrtDumpMemoryLeaks(), this is completely leak-less. Just FYI for anyone thinking of using it :)

Ok, I've only run this in a debug build, but check it out:

Code:

---

int main( int argc, char* argv[] )
{
    CMemory* m = new CMemory;
    clock_t start, end;
    float delta = 0;
    float delta2 = 0;
    char* test = NULL;

    start = clock();

    for ( int i = 0; i < 100000; i++ )
    {
        test = static_cast<char*>( m->MemAlloc(100) );
        m->MemFree( test );
    }

    end = clock();
    delta = (float) ( end - start ) / (float) CLOCKS_PER_SEC;

    start = clock();

    for ( int i = 0; i < 100000; i++ )
    {
        test = new char[100];
        delete[] test;
    }

    end = clock();
    delta2 = (float) ( end - start ) / (float) CLOCKS_PER_SEC;

    std::cout << "CMemory: " << delta << "\n";
    std::cout << "CRT: " << delta2 << std::endl;

    delete m;

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

    return 0;
}

---

Results

Code:

---

CMemory: 0.015
CRT: 0.078
Press any key to continue

---

God I'm hot ****!

Quick crappy calculation of average:

Code:

---

int main( int argc, char* argv[] )
{
    CMemory* m = new CMemory;
    clock_t start, end;
    float delta = 0;
    float delta2 = 0;
    float diff = 0;
    float average = 0;
    float results[5] = { 0.0f };
    char* test = NULL;

    for ( int k = 0; k < 5; k++ )
    {
        start = clock();

        for ( int i = 0; i < 100000; i++ )
        {
            test = static_cast<char*>( m->MemAlloc(100) );
            m->MemFree( test );
        }

        end = clock();
        delta = (float) ( end - start ) / (float) CLOCKS_PER_SEC;

        start = clock();

        for ( int i = 0; i < 100000; i++ )
        {
            test = new char[100];
            delete[] test;
        }

        end = clock();
        delta2 = (float) ( end - start ) / (float) CLOCKS_PER_SEC;
        diff = delta2 - delta;
        results[k] = diff;

        std::cout << "CMemory: " << delta << "\n";
        std::cout << "CRT: " << delta2 << "\n";
        std::cout << "Thats a difference of " << diff << " MS!\n";
    }

    // calc average of results
    float all = 0;
    for ( int k = 0; k < 5; k++ )
        all += results[k];

    average = all / 5;
    std::cout << "Average: " << average << "\n";

    delete m;

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

    return 0;
}

---

Results

Code:

---

CMemory: 0.031
CRT: 0.062
Thats a difference of 0.031 MS!
CMemory: 0.016
CRT: 0.109
Thats a difference of 0.093 MS!
CMemory: 0.016
CRT: 0.078
Thats a difference of 0.062 MS!
CMemory: 0.015
CRT: 0.078
Thats a difference of 0.063 MS!
CMemory: 0.016
CRT: 0.078
Thats a difference of 0.062 MS!
Average: 0.0622
Press any key to continue

---

EDIT:

Sure it's not much faster (is it?) but it was good practice, and I'm keeping it. Valuable debug information when I add a few more features to it.
The first paragraph under the "Growing your own" section of this article says it all: http://www.gamasutra.com/features/20020802/hixon_01.htm
You're all members of gamasutra, right?

EDIT2: Yes, I realise my one is using the same block over and over.

I've implemented a memory management system in the past, and I found a significant speed increase while freeing if I used a pointer to the struct instance for that memory chunk during allocation.

So I'd call memalloc() or whatever my allocation function was called. It would allocate (using malloc()) the requested amount of memory plus the size of a pointer. The first <pointer size> bytes would contain a pointer to a structure that contained information such as the size of that chunk of memory. then memalloc() would return a pointer to the allocate memory right after that pointer.

When memfree() was called it would retrieve the pointer that existed right before the memory address that was passed to the function.

I found that method was a zillion times faster than walking through a linked list to find the right node. Especially since I was dealing with hundreds of thousands of allocations at any given time.

I actually wrote it for my TinyMAZE server. This is a snippet of information about the memory management system in case it interests you ;)

Code:

---

@info mem
DreamsMAZE Virtual Memory Status:
Total Size: 5,204,759 bytes
Peak Size : 11,608,200 bytes

Temporary Allocations Status:
Current Allocations : 13 (341 bytes)
Overhead            : 28 bytes (364 total bytes)
Free Links (highest): 187 (200)
Free Links Use      : 5,236 bytes
Heap size          : 1,048,576 bytes

Permanent Allocations Status:
Current Allocations : 159,203 (5,204,418 bytes)
Overhead            : 36 bytes (5,731,308 total bytes)
Free Links (highest): 473 (500)
Free Links Use      : 17,028 bytes

---

It also had a temporary "heap" system where you could dynamically allocate memory without having to free it. Each time through the game loop it just freed that entire heap, so it was very short-lived memory but very useful and efficient.

That sounds a helluva lot better then. I thought I had seen something like that somewhere and I found out where: The C Programming Language. They have an example that uses a similar system.

I just re-ran the test allocating from 1 to 5000 blocks and it was disgusting :eek:
Well at least I'm learning :)

Yes.

Code:

---

if ( walk->mSize == bytes && walk->mFree )
        {
            // Perfect match. Clear the data and return a pointer to it.
            memset( walk->mData, 0, walk->mSize );
            return static_cast<void*>( walk->mData );
        }

---

This looks suspect. I see no need to clear the memory block prior to returning a pointer to it as this adds overhead and is useless since you are not supposed to assume a returned pointer from new or malloc is pointing at zeroed memory.

Try it. Allocate a block with new or malloc and print the block's contents w/o ever touching it. You will find that it is not zeroed.

If you want to zero it not using memset and using pure assembly may also help. Memset is very fast but it does do some copy propogation and up-down down-up memory address checking and picks the correct routine.

Code:

---

void CMemory::ClearBlock32(DWORD *pBlock,DWORD dwSize)
{
  __asm {
    mov esi,pBlock 
    mov ecx,dwSize
    mov eax,0x00000000;
    rep  stosd
    and ecx,03h
    rep stosb
  }
}

---

Again my code doesn't do any checking and I cannot guarantee in all cases that it is faster than memset. You must pass the size of the block as DWORDs.

Here is a clear block function to clear for 8-bit:

Code:

---

void CMemory::ClearBlock32(DWORD *pBlock,BYTE uSize)
{
  __asm {
    mov esi,pBlock 

    mov ecx,uSize
    shl ecx,4

    mov eax,0x00000000;
    rep  stosd

    //Get any hanging data that did not fit in the final DWORD
    //Will only happen if a size is not a factor of 4 which is possible in a mem manager
    and ecx,03h
    rep stosb
  }
}

---

And for copies:

Code:

---

void CopyMemBlock32(DWORD *pSrc,DWORD *pDst,DWORD dwSize)
{
  __asm {
  mov esi,pSrc
  mov edi,pDst
  mov ecx,dwSize
  rep  movsd
  }
}

---

Also aren't you going to simply override new and delete to be specific to your memory manager or are you going to force yourself to call the memory object class? If you choose either you should also make your CMemory class a singleton since there will only be one memory manager.
Having two memory managers would be a bad idea.

Singletons are the end all be all of solutions and they come fraught with problems as well, but in this case I would use one.

For some reason whenever I override the global new and delete, they never get called. Or something. I can't remember exactly but I may re-fiddle with that. On the other hand I could override a class' operator new / delete...

Stuff it, I'll stick with the CMemory singleton I think.

Holy moly, Bubba changed his avatar :eek:

>>

Code:

---

void CMemory::ClearBlock32(DWORD *pBlock,DWORD dwSize)
{
  __asm {
    mov esi,pBlock 
    mov ecx,dwSize
    mov eax,0x00000000;
    rep  stosd
    and ecx,03h
    rep stosb
  }
}

---

I'm not particularly good at assembly, but doesn't edi need to be set to something?

No EDI is not used in a stosd. STOS(B | W | D) stores eax at ES:EDI. The instruction that uses EDI or destination index is MOVS(B | W | D).

ESI - source index
EDI - destination index
ECX - count register, can also be used a general purpose register - but REP uses this as a count register

MOVSD - copies 1 DWORD at ESI to EDI.
REP - is a prefix for string operations which will execute the instruction it precedes for ECX count.

ECX will decrement/increment based on the DF or direction flag. You should add code to specifically set the direction flag to forward (STD) in order to ensure proper copy direction.

Okies.

Ok how the hell do you write an address into a char buffer? I've tried (and erased) a million different ways and I can't do it. Do I need to split the address up into bytes and write them in individually?

I want to write the address of block:

Code:

---

MemBlock_t* block = new MemBlock_t;

---

Actually I think I've just inline assemblied it. Gimmie a couple of minutes if you happen to responing.
Nope. I can get the address in there by the looks of it, with this:

Code:

---

void* CMemory::MemAlloc( size_t bytes )
{
    MemBlock_t* block = new MemBlock_t;
    char* data = new char[bytes + sizeof(block)];

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

    __asm
    {
        mov eax,block
        mov ebx,data
        mov ecx, dword ptr[eax]
        mov dword ptr[ebx],ecx
    }

    for ( size_t i = 0; i < bytes + sizeof(block); i++ )
        printf( "%d ", *(data + i) );

    return ( data + sizeof(block) );
}

---

Getting it back into a MemBlock_t* is proving difficult.

Ah got the address in. It's so simple!

Code:

---

void* CMemory::MemAlloc( size_t bytes )
{
    MemBlock_t* block = new MemBlock_t;
    char* data = new char[bytes + sizeof(block)];

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

    *(unsigned long*) data = *(unsigned long*) █

    for ( size_t i = 0; i < bytes + sizeof(block); i++ )
        printf( "%x ", *(data + i) );

    return ( data + sizeof(block) );
}

---

I do believe I've done it. Panic over :)

Code:

---

////////
// MemAlloc
//  FIXME: This is as ugly as .........
//
void* CMemory::MemAlloc( size_t bytes )
{
    MemBlock_t* block = new MemBlock_t;
    char* data = new char[bytes + sizeof(block)];

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

    *(unsigned long*) data = *(unsigned long*) █

    for ( size_t i = 0; i < bytes + sizeof(block); i++ )
        printf( "%x ", *(data + i) );

    return ( data + sizeof(block) );
}

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

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

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

    if ( p )
        delete[] pt;

    delete block;
}

---

my solution of a memory manager worked that way:

basically memory management reduces to managing blocks with certain offsets and certain sizes.

the methods of the memory manager for now

Code:

---

Offset allocate(Size s); // allocates a block of size n
void free(Offset o);

---

a realloc method can be added if needed.

Code:

---

class Block {
  Offset offset;
  Size size;
  // since we're going to use a std::(hash)map, we define the operator < here:
  // blocks will be sorted by offsets
  bool operator(const Block &r_rhs) const { return offset < r_rhs.offset; }
};

---

ok, now lets define our UsedBlockMap, which is simply a container for all allocated blocks (blocks-in-use).
of course hash-maps would be better, but i havent thought about a good hash func yet (probably the offsets would suffice to do better than the ordinary map - but so what, thats off topic anyway now).

Code:

---

typedef std::map<Block, YourData> UsedBlockMap;

---

(i used a map to map a Block to YourData. i'm not sure right now, why i havent used a map<Offset, YourDataAndBlockSize> instead - since actually i just want to map the offset... anyway)


ok, now lets simply make a low_level_malloc function which takes the offset and size as arguments (note that this malloc function won't figure out the offset of a free block by itself - it will simply try to allocate a block with a given offset and a given size).
the implementation of low_level_malloc will simply check using lower_bound(*) what offset of a block in the map-container is less-equal to the specified offset and return an interator to that element (or .end() in case there is none).
now what have we won then?

well, we know block just before the point we want to insert our new block.
but when we increment the iterator returned by lower_bound we get an interator to the block following the point where we want to insert our new block.
so we can easily check now, wheter our new block fits into that slot.
so the offset of the new_block must be greater then the offset of the previous block + its size, and less than the offset of the following block.
in case the block fits, we already know an iterator we could pass as a hint to the map-container (the iterator to the next block) to insert in basically constant time.

note that lookups in a map only take O(log(n)) time - and for hash-maps between O(log(n)) and O(1) (i'm not sure if a bad hash function might make it worse than that)
(that means if you have e,g, 2^10 = (1024) blocks finding the spot of where to insert the new block will only take log(2^10) = 10 steps to find it.

ok, how do we free? thats simple:

Code:

---

void free(Offset offset);
  UsedBlockMap::iterator it = used_block_map.find(Block(offset));
  if(used_block_map.end() == it)
    error;
  else
  used_block_map.erase(it);

---

again, free only takes O(log(n)) steps.



now the question is: how do we get an offset for our low_level_malloc?
i mean when i allocate memory i don't want to care about where it's offset should be.

well, a second map can be used, which maps Sizes to Offsets.
so this second map should map length of every hole in the UsedBlockMap to the offset, where this hole begins.
the holes in the UsedBlockMap are stored in the FreeBlockMap.
initially there are no used blocks, so the free block list contains just one big block. (e.g. rangeing from 0 to the maximum integer)
since there can be multiple free blocks of the same size, but of course with different offsets, a map doesnt suffice - we need a multimap here.
since elements in a map are sorted, we need to think about how to order them.
the fasted option would be to have biggest size first, smalles offset first.
so when we call our final malloc method, simply the first entry in the free block list is checked, and if it is too small we already know that we're out of memory (since all other blocks in the free block list are at most the same size). if the block is big enough, then we simply use that offset as the offset for our low_level_malloc.

unfortunately free blocks are usually split up into a used portion and a free portion.
also, when freeing a used block, there might be 2 free blocks surrounding it, which have to be merged again.
so there is some overhead to keep the 2 maps in a consistent state, which is a bit complicated to manage.
but its still very fast, since remember: lookups take O(log(n)) time!

so even if we have e.g. a million elements (2^16) and we need a total of 3-4 lookups in all those maps for each (de)allocation-request, we can allocate and free blocks of memory with checking fewer than about 4*log(2^16) = 4 * 16 = 64 elements of our maps.

(so the thing is: in that solution you have NO LINEAR searches anywhere, so it works extremly fast with many allocations)

(*) i'm never sure if its lower_bound or upper_bound which does the thing i described :)

ack... my post became so long??? uff... well just ignore it then :D

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.

Quote:

---

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 :)