Memory management in games

Memory management in games

[Luke A. Guest]

Hi,

Further to my posts in the game dev thread, I've decided to go back on my
original thoughts and do the game engine in Ada (I can always *cough* port
*cough* gnat *cough* ;-D).

Now, one of my design requirements is that I *must* be able to see *all*
memory allocations and track them, this is so I can build in debugging
tools into my engine. I have just done this in C++ by overriding the
global new/delete operators and using macros to redefine
new/delete/mallo/free/calloc/etc. to point to my new memory management
class. These macros also pass the filename and line number from where the
memory was allocated. Also, this class keeps track of all allocations in a
list template. I currently just dump out the contents of the list on exit.

So, I need to be able to do the same in Ada. Enter Storage Pools, ok, it's
not difficult to write a pool class, I've just written a simple one. But,
what a game engine requires is the ability to allocate a big block of
memory and then allocate other blocks from this, so it's like a
hierarchical pool system.

e.g. Under Linux, I might allocated a block of memory to use for the
entire game (from a start up script), say 50Mb and this will be used for
this session

e.g On a PS2 we have something more challenging, the underlying OS needs
some memory to load the game ELF and have some memory to use for it's own
data structures, so in the game I say, give me 25Mb for this session.

Then from this pool, other pools/objects are allocated. So, I need a way
to override the default memory allocation method for everything, including
library routines. Can this be done portably? I know I can specify the
T'Storage_Pool for a type, will this work for libgnat.a types as well?

I've seen that GNAT provides the System.Memory package, this isn't
standard, so should I just go out of my way and import the memory
allocation functions I require (malloc on Linux, memalign on PS2, etc.)?

Also, what would be the best method of passing the function name where the
allocation call is, through to the allocator, so that I can show where an
allocation was made? I could use gnatprep I suppose, but obviously would
prefer to be portable. FYI, there will be two builds as memory allocation
tracking would not be in the final release mode build as it's extra
overhead.

Thanks,
Luke.

Re: Memory management in games

[David Botton]

Please see these two articles in the advanced section of the AdaPower 
Source Code Treasury

Memory Management with Storage Pools (Anh Vo)
http://www.adapower.com/index.php?Command=Class&ClassID=Advanced&CID=222

Memory Management with Storage Pools - Update (Anh Vo)
http://www.adapower.com/index.php?Command=Class&ClassID=Advanced&CID=223

You probably should look through the advanced section in general for 
other good ideas and practices.

David botton


On 2004-11-27 14:48:48 -0500, "Luke A. Guest" 
<laguest@n_o_p_o_r_k_a_n_d_h_a_m.abyss2.demon.co.uk> said:

> Hi,
> 
> Further to my posts in the game dev thread, I've decided to go back on my
> original thoughts and do the game engine in Ada (I can always *cough* port
> *cough* gnat *cough* ;-D).
> 
> Now, one of my design requirements is that I *must* be able to see *all*
> memory allocations and track them, this is so I can build in debugging
> tools into my engine. I have just done this in C++ by overriding the
> global new/delete operators and using macros to redefine
> new/delete/mallo/free/calloc/etc. to point to my new memory management
> class. These macros also pass the filename and line number from where the
> memory was allocated. Also, this class keeps track of all allocations in a
> list template. I currently just dump out the contents of the list on exit.
> 
> So, I need to be able to do the same in Ada. Enter Storage Pools, ok, it's
> not difficult to write a pool class, I've just written a simple one. But,
> what a game engine requires is the ability to allocate a big block of
> memory and then allocate other blocks from this, so it's like a
> hierarchical pool system.
> 
> e.g. Under Linux, I might allocated a block of memory to use for the
> entire game (from a start up script), say 50Mb and this will be used for
> this session
> 
> e.g On a PS2 we have something more challenging, the underlying OS needs
> some memory to load the game ELF and have some memory to use for it's own
> data structures, so in the game I say, give me 25Mb for this session.
> 
> Then from this pool, other pools/objects are allocated. So, I need a way
> to override the default memory allocation method for everything, including
> library routines. Can this be done portably? I know I can specify the
> T'Storage_Pool for a type, will this work for libgnat.a types as well?
> 
> I've seen that GNAT provides the System.Memory package, this isn't
> standard, so should I just go out of my way and import the memory
> allocation functions I require (malloc on Linux, memalign on PS2, etc.)?
> 
> Also, what would be the best method of passing the function name where the
> allocation call is, through to the allocator, so that I can show where an
> allocation was made? I could use gnatprep I suppose, but obviously would
> prefer to be portable. FYI, there will be two builds as memory allocation
> tracking would not be in the final release mode build as it's extra
> overhead.
> 
> Thanks,
> Luke.

Re: Memory management in games

[Luke A. Guest]

On Sat, 27 Nov 2004 19:53:46 -0500, David Botton wrote:

> Please see these two articles in the advanced section of the AdaPower 
> Source Code Treasury
> 
> Memory Management with Storage Pools (Anh Vo)
> http://www.adapower.com/index.php?Command=Class&ClassID=Advanced&CID=222
> 
> Memory Management with Storage Pools - Update (Anh Vo)
> http://www.adapower.com/index.php?Command=Class&ClassID=Advanced&CID=223
> 
> You probably should look through the advanced section in general for 
> other good ideas and practices.

Yeah, I did actually read these but didn't see anything that would help me
for my particular circumstances.

Thanks,
Luke.

Re: Memory management in games

[Dmitry A. Kazakov]

On Sat, 27 Nov 2004 19:48:48 +0000, Luke A. Guest wrote:

> Further to my posts in the game dev thread, I've decided to go back on my
> original thoughts and do the game engine in Ada (I can always *cough* port
> *cough* gnat *cough* ;-D).
> 
> Now, one of my design requirements is that I *must* be able to see *all*
> memory allocations and track them, this is so I can build in debugging
> tools into my engine. I have just done this in C++ by overriding the
> global new/delete operators and using macros to redefine
> new/delete/mallo/free/calloc/etc. to point to my new memory management
> class. These macros also pass the filename and line number from where the
> memory was allocated. Also, this class keeps track of all allocations in a
> list template. I currently just dump out the contents of the list on exit.
> 
> So, I need to be able to do the same in Ada. Enter Storage Pools, ok, it's
> not difficult to write a pool class, I've just written a simple one. But,
> what a game engine requires is the ability to allocate a big block of
> memory and then allocate other blocks from this, so it's like a
> hierarchical pool system.

Where is any problem? Secondary pools can be allocated in the first order
pool.

> e.g. Under Linux, I might allocated a block of memory to use for the
> entire game (from a start up script), say 50Mb and this will be used for
> this session
> 
> e.g On a PS2 we have something more challenging, the underlying OS needs
> some memory to load the game ELF and have some memory to use for it's own
> data structures, so in the game I say, give me 25Mb for this session.
> 
> Then from this pool, other pools/objects are allocated. So, I need a way
> to override the default memory allocation method for everything, including
> library routines. Can this be done portably?

I depends on what libraries you mean. Normally a well-designed library does
not privately allocate anything large. So you can estimate the upper bound
of heap memory required for it and then limit the heap (= the pool you
cannot control) at linkage.

And, well, I would say that you should better care about stack if you have
memory constraints.

> I know I can specify the
> T'Storage_Pool for a type, will this work for libgnat.a types as well?

No, it is C++ mindset. In Ada pool is associated not with the type of
objects, but with the type of pointers to objects. I.e. you can have
objects of the same type T allocated in different pools. It is more
flexible. (but also more restrictive if you want to break something written
by other people (:-))

> I've seen that GNAT provides the System.Memory package, this isn't
> standard, so should I just go out of my way and import the memory
> allocation functions I require (malloc on Linux, memalign on PS2, etc.)?

Theoretically you could implement your own pool on the top of the standard
pool or malloc/free, just by routing Allocate / Deallocate there. But it is
cleaner to implement it new, on a chunk of raw memory. Especially if you
need some additional memory tracking / debugging. There are numerous
algorithms and methods. As always, Knuth is a good starting point.

> Also, what would be the best method of passing the function name where the
> allocation call is, through to the allocator, so that I can show where an
> allocation was made?

If you use GNAT then (only for debugging, may not work on some targets!)

with Ada.Text_IO;  use Ada.Text_IO;
with GNAT.Traceback;  use GNAT.Traceback;
with GNAT.Traceback.Symbolic;  use GNAT.Traceback.Symbolic;

procedure Call_Stack is
   TB  : Tracebacks_Array (1..100);
   Len : Natural;
begin
   Call_Chain (TB, Len);
   Put_Line (Symbolic_Traceback (TB (1..Len)));
end Call_Stack; 

This would print the call stack at any point of the program you call to
Call_Stack. Of course you can modify it to store the call chain instead of
printing.

BUT, look, I have an impression that you are paying too much attention to
memory leaks. But Ada is not C++! (:-))

Further to this point, for a game engine I would not use dynamic allocation
too much. Perhaps I would not use it at all, maybe except for a pair or so
user-defined stack pools. For truly dynamic objects like characters etc, I
would use a reference counting garbage collection (an example and a stack
pool implementation can be found ion my page
http://www.dmitry-kazakov.de/ada/components.htm).

> I could use gnatprep I suppose, but obviously would
> prefer to be portable. FYI, there will be two builds as memory allocation
> tracking would not be in the final release mode build as it's extra
> overhead.

Ah, but then you should not care about portability. Debug it with GNAT
only, release it with everything else.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de