Thread: My memory management solution

  1. #16
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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.
    Last edited by cboard_member; 08-23-2006 at 05:01 AM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  2. #17
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    Last edited by itsme86; 08-23-2006 at 05:14 AM.
    If you understand what you're doing, you're not learning anything.

  3. #18
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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
    Last edited by cboard_member; 08-23-2006 at 05:21 AM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  4. #19
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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.
    Last edited by cboard_member; 08-23-2006 at 05:41 AM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  5. #20
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    If you understand what you're doing, you're not learning anything.

  6. #21
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with insert/delete binary search tree
    By Nazgulled in forum C Programming
    Replies: 39
    Last Post: 03-25-2009, 04:24 PM
  2. Memory management - How/why/when
    By micke_b in forum C Programming
    Replies: 29
    Last Post: 11-07-2007, 12:26 PM
  3. Suggestions on this C style code
    By Joelito in forum C Programming
    Replies: 11
    Last Post: 06-07-2007, 03:22 AM
  4. Shared Memory - shmget questions
    By hendler in forum C Programming
    Replies: 1
    Last Post: 11-29-2005, 02:15 AM
  5. Memory Management
    By rasdfasfd in forum C Programming
    Replies: 2
    Last Post: 12-03-2002, 08:57 PM