My memory management solution

This is a discussion on My memory management solution within the Game Programming forums, part of the General Programming Boards category; Now let me just say that I know this solution is far from ideal and also that I've read very ...

  1. #1
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709

    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 )

    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
    Last edited by cboard_member; 08-22-2006 at 11:31 AM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

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

    - Mike McShaffry

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

    - Mike McShaffry

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,169
    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.
    Last edited by itsme86; 08-22-2006 at 12:27 PM.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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
    Well at least I'm learning
    Last edited by cboard_member; 08-22-2006 at 12:48 PM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.

  7. #7
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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

    >>
    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?
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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.
    Last edited by VirtualAce; 08-22-2006 at 01:34 PM.

  9. #9
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    Okies.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

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

    - Mike McShaffry

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

    - Mike McShaffry

  12. #12
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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*) &block;
    
        for ( size_t i = 0; i < bytes + sizeof(block); i++ )
            printf( "%x ", *(data + i) );
    
        return ( data + sizeof(block) );
    }
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  13. #13
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    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*) &block;
    
        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;
    }
    Last edited by cboard_member; 08-22-2006 at 03:32 PM.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  14. #14
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    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
    Last edited by Raven Arkadon; 08-22-2006 at 05:23 PM.
    signature under construction

  15. #15
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    ack... my post became so long??? uff... well just ignore it then
    signature under construction

Page 1 of 2 12 LastLast
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, 11:26 AM
  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, 01:15 AM
  5. Memory Management
    By rasdfasfd in forum C Programming
    Replies: 2
    Last Post: 12-03-2002, 07:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21