Question About Different (Feasible) Methods of Memory Management

[DeXecipher]

As a few of you may know I am working on this one man project, a complex beast. I'm working on my game/media engine. I have implemented such things as smart ptrs and allocator classes, one for new and one for malloc respectively, and reference classes which use smart ptrs, but I've avoided the main problem. My main problem before I can get into the more fun stuff is how to properly do memory management. I know how to wrap new and malloc into a memory pool, in a linked list that has an O(n) worst case access, but im not sure if it is feasible to use in a professional game. My question is, should i allocate memory at startup, define my own new/delete and use that, or should I just work with new and delete and just use a pool?

What are the methods of memory management that are both easy to implement, by one programmer, and semifeasible for a semi-large scale project? Does anyone know what ogre, or irrlicht does for memory management? I see Ogre operator overload the new/delete operator in almost every class, but i dont necessarily want to force the user to use my manager perse', i just want it as an optional component.

[DeXecipher]

somebody help, lol

[DeXecipher]

nobody have enough knowledge to help?

[cire]

I think you should refrain from premature optimization.

[Disch]

Sounds like you are reinventing the wheel.

Smart pointers are already implemented in the C++ standard as of C++11 (in the form of std::unique_ptr, std::shared_ptr, etc) and are supported in all the big mainstream compilers. Plus there isn't really much point in making a smart pointer class which supports malloc, as malloc should never be used in C++ code.


As for memory pools, they can be a solution to the memory fragmentation problem, but only when applied correctly. Dumping all your memory allocations into a single pool will provide absolutely no benefit to you. If you want to provide support for a memory pool, the typical approach is to designate a sector size, then keep track of which sectors are occupied and which are not.

Ideally, one sector = one object... which is easiest to accomplish by putting objects of each class into their own pool (ie: if you have two classes Foo and Bar, each class would have its own memory pool -- this is probably what Ogre is doing by overloading new/delete in each class -- it's likely doing that so it can forcibly put instances of those classes into a shared pool). Then the sector size can just be sizeof(class).


Memory pools provide their own set of complications, though. If you allocate more objects than the pool was originally built to hold, you either have to fail (ouch!) or you have to generate an entirely new pool... so managing one pool really means potentially managing several. Obviously this is not ideal, so you'd want to allocate the pool to be large enough at the start. Note that you CANNOT simply reallocate the pool and make it bigger, as this will destroy any existing pointers to the objects in the pool.


Making a memory pool for every class is probably overkill, too. Really you'd only want to do it to classes which are likely to cause fragmentation (classes which are frequently allocated/destroyed). For long-life objects, putting them in a pool probably doesn't do much for you.

I know how to wrap new and malloc into a memory pool, in a linked list that has an O(n) worst case access

Do not use a linked list. Linked lists have non-contiguous memory, which defeats the entire point of having a memory pool (what good is a memory pool if it's scattered all over the heap?)

Implementation for a pool likely should look more like this:

bool* occupied = new bool[ number_of_sectors ];
uint8_t* pool = new uint8_t[ number_of_sectors * sector_size ];

// zero the 'occupied' buffer to indicate that all sectors are available.

// to place an object in sector 'x'
//   note:  simplistic, and assumes sizeof(object) <= sector_size
if( !occupied[ x ] )
{
  uint8_t* p = pool + (x * sector_size);
  // construct object at 'p'
  occupied[x] = true;
}
else
  // find another sector, one which isn't occupied 

If sizeof(object) is greater than the sector_size, you'll have to find available sectors which are contiguous.


You could improve that by using a larger data type (like uint64_t) instead of bool, then you can quickly see if any one of 64 sectors are available by checking a single value, rather than checking only one sector per value.

[DeXecipher]

@Disch, Thank you very much. As for the typing of my allocators, I am using templates for that. What exactly is a fragmentation? As for the boolean types, I can create an arbitrary number of booleans to check each sector, correct? My last question, how exactly do you access individual objects? Would you do it by sector, converting the head of the sector into a pointer to the class and just search, or is it more complex than that. I think ill have to get farther in my classes........

[Disch]

What exactly is a fragmentation?

If you don't know what fragmentation is, why are you making memory pools? ;P

The basic idea is you have an area of memory. To keep this example simple, let's say this block represents all of available memory:
[.............]

Then say you allocate some objects, A, B, C, and D. Note that the objects are all of different sizes:
[AABBBCDDDD...]

Then say objects A and C get deleted, freeing up their space in memory:
[..BBB.DDDD...]

Now say you need to allocate another D object (need 4 spaces). Even though there are more than 4 spaces available... there are not 4 contiguous spaces available, therefore you do not have enough memory to allocate another D. The memory is too fragmented.


Though really, this will only be a problem if you are doing LOTS AND LOTS of allocations. You probably should not worry about it until you see symptoms (it usually presents itself as a memory leak, with the program consuming more and more RAM the longer it runs).

For short-life programs like games, it's usually not much of an issue, and I wouldn't really worry about it unless you have compelling reason to. In which case you don't need to bother with making memory pools, overloading new/delete, making allocators, etc.

My last question, how exactly do you access individual objects?

Not sure what you mean. 'p' in the example of my last post would be returned from the memory pool as the location where the object will be placed (ie, once you construct an object there with placement new, it becomes a pointer to that object).

So after you cast it to whatever type, and construct the object, you can access the object just like normal.

[DeXecipher]

thank you, i bookmarked this. So the number of sectors is equivalent to the number of objects i want, and the sector size is the size of a single object, and if i want to access a single object in the pool i just access sector "x" and cast that memory location into a pointer to the type of object i want. Does this assume that that the size of each sector is the same? Interesting, so if i want to allocate a general purpose memory pool, then the size of each sector must be at least the size of the largest object and can be arbitrarily big as long as the largest object can fit?

[DeXecipher]

@Disch
Is this along the lines of what you mean?

        virtual void* getMemory( unsigned sector, size_t size_object )
        {
            if( !this->isStarted() )
            {
                //...handle exception

                return 0;
            }

            if( sector >= g_nSectors )
            {
                //...handle exception

                return 0;
            }

            //assume that the offset of the object is not greater than
            //the unified sector size.

            if( size_object > g_nSectorSize  )
            {
                //...handle exception

                return 0;
            }

            if( g_bSectorOccupied[sector] == true )
            {
                //...handle exception

                return 0;
            }

            //each sector could be a type of object
            //the size of the  object is the offset into that sector
           //if the caller of this function would like to access
          //an individual object in the sector
          //then all the need to do is cast the data
         //into a pointer of the type they want
        //and access it like a normal array.

            unsigned object_pos = sector * g_nSectorSize;

            if( object_pos >= g_nSectors * g_nSectorSize  )
            {
                //...handle exception
                //out of bounds

                return 0;
            }

            t_word* pHead = &g_pMemory[object_pos];
            g_bSectorOccupied[sector] = true;


            return (void*)pHead;
        }

Edit:
So when i want to free memory for use i just set the boolean to true and reset the memory of that sector, using the global size of each sector?

[Disch]

--slightly reordering your quotes here--

so if i want to allocate a general purpose memory pool

Just to clarify... there is no reason to do this. The heap is already a general purpose memory pool. You might as well just use it directly (ie: just do a normal new/delete). Throwing everything in a common memory pool gives you zero benefit and is purely disadvantageous.

So the number of sectors is equivalent to the number of objects i want, and the sector size is the size of a single object

Ideally, yes. Though it might be possible for an object to span several sectors. It depends on how flexible you want your pool to be.

Sector size gives a direct tradeoff between optimal memory usage and potential for memory fragmentation. IE: larger sectors = more wasted memory, but less possibility for fragmentation. Smaller sectors = less wasted memory, but greater risk for fragmentation.

This is exactly why creating a general purpose memory pool is ill-advised. Striking the correct balance is difficult... and you are extremely unlikely to outperform the heap as far as generic memory management goes.

and if i want to access a single object in the pool i just access sector "x" and cast that memory location into a pointer to the type of object i want.

Well again.. the pool is not accessing objects. It's only distributing memory. I think you might be confusing the two.

The pool will never need to access an object in the pool. And code outside the pool will never need to know that the object exists in a pool.

It works like this:

1) main program calls some kind of 'allocate' function in the pool, telling it how much memory it needs
2) The pool find an available sector (or sectors) large enough to contain that memory
3) It marks those sectors as "occupied" so they don't get allocated to other areas
4) It returns a pointer to the start of the sector back to the main program
5) The main program now has a pointer. It can now construct the object of whatever type it needs at that pointer (with placement new).

6) When the main program is done with the object, it calls its destructor
7) Then it sends the pointer it has back to the memory pool, telling it to free the memory
8) The memory pool takes that pointer, figures out which sector(s) it corresponds to, and marks those sectors as "unoccupied" so they can be used again.

then the size of each sector must be at least the size of the largest object and can be arbitrarily big as long as the largest object can fit?

No, sector size can be smaller than the object size. But then you have to find contiguous sectors, which reintroduces the possibility for fragmentation. ...delicate balance...

[DeXecipher]

I think i got it, i'll post the code if you want to see it. Thanks for the help, a memory pool is very simple. Lol, so Ogre might be creating a static memory pool for every object, that is over kill if that is true.

[Disch]

More likely it's for every class. Not a terrible idea because that way you know every object is the exact same size. But I've never looked at Ogre's source so I can't say for sure.

Though I agree it's overkill.

[DeXecipher]

If you want to see the code, i can PM it to you if you want, it works perfectly. For 256 bytes each sector at 8 sectors in the pool it succeeds in allocating up to 64 ints (max). 64 * 4 bytes (int size) = 256. Thanks man. After testing it, it fails at anything exceeding the maximum sector size, [64*4,....].