RE: Functions and memory usage

["Michael Flad" <Michael.Flad@...>]

Hi,

i don't know somthing about Albertos implementation but this all sounds
like the typical fixed block allocator - see Stroustups C++ Language
for a sample implementation.

void* alloc( size )
{
  if( size < MAX_POOLSIZE )
 {
   return Pools[size/4].alloc()
 }
 return malloc(size);
}

Where Pools is a array of those fixed block allocs/heaps.

Freeing the memory is, like you mentioned, a source of fragmentation
but really only if there are peak levels with enormous memory
consumption an with very distributed long living objects beeing
created during this time followed by lots of times where only
very few memory is consumed. But i think this isn't a typical
situation - most of the times you alloc/free more or less
constant numbers of objects and so new allocs reuse previously
freed objects. I think most of the time it even is not necessary
to free pages at all because there arent that different situations
during the programs execution (of course I'm talking of typical
game situations, serverapps e.g. may behave very very different)

If you implement the fixed block alloc as separate class/template
it's simple and usefull (like you suggested e.g. for cache coherency) to
use them for some special subsystems.
For instance one can use it for nodes during pathfinding and
simply throw away the whole allocater after the search without
even freeing any of the allocated nodes left after finishing the
search.

Regards,

  Michael

--
Fantastic Realms Interactive GmbH - Germany
Phone: +49 (0)7121 / 947 999 0
Fax:   +49 (0)7121 / 947 999 9


> -----Original Message-----
> From: owner-lua-l@tecgraf.puc-rio.br
> [mailto:owner-lua-l@tecgraf.puc-rio.br]On Behalf Of Nick Trout
> Sent: Friday, October 18, 2002 3:31
> To: Multiple recipients of list
> Subject: RE: Functions and memory usage
> 
> 
> 
> > > What happens when you deallocate/free an object?
> > Instead of keeping track of the pages we keep a linked list 
> > of feer blocks for every chunk size,
> > because they are "empty" we use the block himself as node of 
> > the linked list so no memory overhead.
> > When we create a page, the address of the first chunk is 
> > aligned in a way that allow us to 
> > retrieve the page start address from the chunk address.The 
> > page is ref counted(first 4 bytes).
> > When we allocate a chunk we pop it from the free list and add 
> > a reference to the page.
> > When we free we put it back in the free list and we decrement 
> > the reference if is 0 we free the page.
> 
> So you could have lots of pages allocated that are half full? Eg. If
> longer living objects were mixed with shorter living ones. I don't
> suppose there is an easy way around this. I like the fact that
> fragmentation of the similar size objects is localised. Given that you
> have a general system though and the allocation could go in any of the
> pages I wonder if it would be more efficient for subsystems to be able
> to create their own pages. This might help with cache coherence? Eg. If
> a particle system allocated X pages its update and rendering may
> benefit. The other benefit may be that if you kill it then all its pages
> disappear and you may not have a number of them lingering because they
> have a few chunks still used in them. I think there is a danger in your
> system that after a time you might end up with lots of pages allocated
> containing a few chunks, and fragmentation will become a problem? 
> 
> There are lots of factors. Your method works for your game and platform
> but I'm not sure how well it would work on a more restricted system with
> a very free flowing environment.
> 
> > I've took a quick look at dlmalloc, it looks not so far from 
> > our approach exept for the implementation.
> > I'll test it.
> 
> That would be great. 
> 
> Regards,
> Nick
>