Memory Management

    This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

    • Memory Management

      First of all, hello everyone! I'm new to the forums, since I only recently purchased Game Coding Complete. I'm not through reading it, by a long shot, but I've been obsessing over something ( preventing me from reading further :P ).

      MrMike states in Chapter 3 that a custom memory manager is prett important to a game engine. I hadn't considered this yet, since all i've been doing so far is muck about with the DirectX SDK.

      I understand why it's important, but I can't really get a decent manager going.. Based on some online tutorials I've thrown something together, it's basically a vector of void pointers and a set of functions that allocates new blocks of memory when needed. It works nicely as far as I can tell, I can stick two structs in there, and they'll be packed neatly next to each other.

      However, it doesn't seem to improve the speed of memory allocations, as far as I can tell. There's probably something I can do to improve that, but I'll be damned if I know how ;).

      Basically my question would be, where can I find more information on memory management? MrMike mentions a lot of books in his further reading section at the end of the chapter, is any of those going to help me understand memory management?

      I'd love to read them all, but books can get pretty expensive.. ;)

      *edit* I have done some things to increase speed. I was calculating free bytes in a block at every call of my allocate() function from scrap, wich was silly, frankly. Using a member variable in the memory manager class to keep track of free bytes, and simply updating it based on the requested allocation size has boosted performance significantly ( it's about 10 X faster in fact ).

      However, if anyone has any recommendations regarding information on memory management, I could still really use it, of course :).

      The post was edited 1 time, last by PawnOfEvil ().

    • In my experience, the best bang for your buck comes from pool allocators. The concept is pretty simple: you create a bunch of memory pools of specific sizes (typically rather small), each which allocates a bunch of memory blocks of that size. Whenever you have a small allocation, you find the pool with the smallest size that will still fit your data and return one of the unused blocks instead. When the client releases the memory, you simply mark it as unused.

      The advantage of this over just new & delete is that you're not actually allocating any memory during the main loop; you're doing it all at initialization time. Furthermore, you don't run into issues with memory fragmentation (an absolute killer on console games, especially small consoles like the Gameboy DS). This system also doesn't very much overhead since it's very fast to determine which block needs to be returned.

      All in all, I'm a huge fan of pool allocators. We used them pretty much exclusively on Brain Quest for all of our small allocation (under 1k I think; I forget the exact number). The only real disadvantage is that you do end up wasting some space. It's the classic speed vs size trade-off, although memory pools tend to be more stable as well (once you get them working).

      -Rez
    • Great, thanks for the advice!

      I was thinking of implementing something similar: lists of free spaces in blocks for the most commonly used small allocators. But I supppose your way is faster, since you don't need to check the amount of bytes left in a block and see what list corresponds with that each time an allocation is requested.

      Also, creating a set number of blocks in initialization seems like a brilliant idea. That way you can control the exact amount of memory you'll use (provided that every new and delete goes through your memory manager from there on). And no actuall allocation during the main loop is indeed a great advantage.

      So the pools you create are all for commonly used sizes, I take it? Do you use one pool for larger requests, then?

      In any case, thanks again for the advice, you've given me a lot to think about and work with!
    • No worries. :)

      The size of each chunk and number of chunks allocated per pool really depends on the project and you'll find it changing. I always allow the pools to grow if they need to during run-time and log every allocation made. There's usually a big warning dumped out when a pool has to resize itself. Towards the end of the project, these logs & warnings help me tune the memory pool system to create the appropriate number of pools of the appropriate sizes for that project. Sometimes I also create special pools dedicated to certain purposes (I talk about this in Chapter 17 of Game Coding Complete, 3rd Edition when I suggest using memory pools for pathing nodes).

      Larger allocations are taken on a case-by-case basis. If you need something bigger than 1k (or whatever your upper limit is) per piece, then the chances are good that you need to put a little more thought into it since pool allocations tend to be too wasteful for such things (unless you have a good idea how big they will be).

      If you have a lot of larger allocations, you may want to have everything greater than 1k (or whatever you feel is a good number) default to a different memory manager. That memory manager could have a single chunk of memory and deal with splitting it out and divvying it up to whoever asks for it. It's slower than the pool allocator, but much less wasteful on space and it's almost certainly faster (and safer) than a straight-up new. Then again, if these allocations happen infrequently, maybe defaulting to the new operator is just fine.

      Just remember about the dreaded memory fragmentation issue. If the client allocates three 1 MB chunks, then releases chunk #1 and chunk #3, then asks for a 2 MB chunk, you'll get an out of memory error despite having enough memory left because there's no single contiguous 2 MB chunk. You need to account for that kind of thing.

      Programming is 1 part science, 1 part art, and 1 part luck. ;)

      -Rez
    • Well, I was inspired, so I got straight to work. I made two new memory managers, one with pools of pre-sized chunks and one with one large chunk and pointers to free spots in the chunk.

      However, I've run into a problem with overloading the new global new operator. I've overloaded the new operators for both memory managers. Debugging tells me that somewhere early on in the constructor for the pool manager, the global new operator gets called. This ends in drama, of course, since the global new operator relies on the pool manager, wich isn't initialized yet by that time.. I've tried to track down what's calling on the global new operator, unsuccessfully. I guess what I'm asking is, how the heck do you overload global operators to use a memory manager without the manager trying to use itself to initialize itself? ?(

      Overloading operators on every class in a project seems like kind of a hassle, and maybe even impossible when there are 3rd party SDKs involved..

      edit:

      I've figured out what's causing the errors: When I initialize either one of the memory managers, I call on functions of STL containers vector and list, like push_back() and push_front to add reserved blocks of memory to them. Apparently these functions call my globally overloaded new operator. The new operator in turn calls on my pool manager to allocate space, but the pool manager isn't initialized yet. So, it throws an exception..

      So, should I use som different way to store my pointers? Something like:

      Source Code

      1. struct MEMORY_CHUNK
      2. {
      3. MEMORY_CHUNK *m_NextChunk;
      4. };


      Or is there a way to circumvent the whole problem?

      Any suggestions are greatly appreciated!

      The post was edited 1 time, last by PawnOfEvil ().

    • There are probably a few issues here.

      First, I strongly recommend that you don't use STL or anything else inside the memory pool class. Write any data structures you need yourself. If you must use the STL, you'll need to make a custom allocator.

      Second, inside your memory pool class, you'll want to use the old-school technique of calling malloc() and free(). Why? Because you've already overloaded the global new & delete operators so you can't use those without recursing into oblivion (or exploding since it's trying to call into your memory pool object). The memory you allocate here should just be a block of raw void* (or unsigned char*) data so there's no constructor to call on it; malloc() and free() are perfectly fine. The constructor for the object itself will get called when the client code uses operator new; it's done automatically so all you need to do is return the memory.

      Finally, don't forget to overload the array versions; operator new[] and operator delete[]. They are actually separate functions so if you don't overload them, they'll call the std CRT new[] and delete[].

      Did I miss anything?

      -Rez
    • Looks like I'll have to read up on making your own containers, since I have no idea how a list really works. But the pop_front and push_front functions came in rather handy in the memory pool.

      But other than that, I've used nothing but malloc and free to set aside and release memory. I figured I couldn't make constructor calls in the manager itself, I just didn't account for the fact that lists and vectors do call new.

      Thanks again for the advice, you've been incredibly helpful :)
    • No prob. :) It's worth learning about how vectors, maps, lists, queues, heaps, etc. all work under the covers. That way you can determine the right tool for the job. For example, continuously calling push_back() on a vector is bad because it can cause the entire vector to be reallocated in some instances.

      Good luck. :)

      -Rez
    • Another question on memory

      I've read a bunch of posts on this forum and found many of them helpful. Thanks to all who have posted some really useful answers and for keeping this forum going for so many years. I read the posts on memory management and memory management books and followed some of the links. I understood a lot but I would some clarification from someone just to make sure I'm on the right track.

      From the chapter on Memory Management: Do I have the correct understanding of things here?

      --
      Concept Example: 2 GB of RAM on the Motherboard

      |0GB---------1/2GB---------1GB---------1.5GB--------2GB| RAM
      |----OS JCL---|---myGame----|---'new'---|
      |-Global mem--|--Stack mem--|-Heap mem--|


      Legend:
      Assume all usage is .5GB for ease of numbers.
      |-myGame-| My Compiled Game, another process on the stack
      |-'new'--| The amt of memory I 'new' to store game gfx on the heap
      |-OS JCL-| = OS Code for process control, you call this Global Memory
      JCL = job control language or think of it as process control, OS stuff

      --
      Do I have the stack, heap and global memory labeled correctly on the diagram?

      So every time I new/malloc something I'm playing with heap memory, which is just the tail end of RAM after the stack memory, right? Also when I see games start up and I see the loading bar filling I can assume the game is 'newing' memory in RAM to store bitmaps, sprites, textures, vector data, and 3D objects?

      Also the book suggests writing a memory manager and other posts talk about the implementation of 1k block of memory management and so forth. My next question is when would someone want to write a new memory manager just to code a simple game (my current task). Is the memory manager just for large projects with pretty 3d backgrounds filled with lots of textured objects?

      Finally, in the above example I can technically 'new' up to 1GB of ram before I run into thrashing (from Ram or hard disk) because I hit the 2GB limit?
    • RE: Another question on memory

      Mostly, yes. The key is that the usable memory available to you is split into two main chunks: the stack and the heap. The stack is used for local variables, parameters, etc. The heap is for dynamically allocated memory. There's also a memory mapping segment, a data segment, etc. This provides a good description of memory organization within a computer:
      duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory

      If you're making a small game, you shouldn't worry about memory at all. You will not come close to using it. In fact, building any major system that adds significant complexity to your game should only be done when absolutely necessary. This includes memory managers. Building it should solve a specific problem you are having.

      -Rez