Re: [Algorithms] memory pool algorithms

[Mat N. <mat...@bu...>]

> I believe
keeping a parallel bitfield would be more straight forward than an
unsorted array of free elements.

Yes. Very much so. It also makes iteration in-order very easy.

How often do you need to iterate over things in order of allocation?

MSN
-----Original Message-----
From: Tom Plunket [mailto:ga...@fa...]
Sent: Thursday, April 23, 2009 9:40 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] memory pool algorithms

> Have a allocated/free list that is an array of indices into the memory
> pool array.  The allocated/free list is divided such that the 0 through
> (M - 1) elements are allocated and the M through (N - 1) elements are
> free; just use an index to the start of the free elements.  The
> allocated/free list is initialized with 0 through (N - 1) and the start
> of the free list is index 0. When you allocate, increment the start of
> the free list index, when you free an element, decrement the index and
> swap the two elements.  To iterate over the allocated elements, iterate
> over the 0 through (M - 1) indices, and use the index to look up the
> object.  The problem with this is that you jump around memory when
> iterating.  If you are concerned with thrashing the cache, it would be
> better to just go through the array and skip empty elements.
> I was just wondering if anyone knew of an algorithm/method which
> facilitated simple memory pool allocation of a single type but with
> constant time allocation/deallocation/item retrieval by index and also
> provided a 'nice' way to iterate through the used elements?

That'll work ok, but you can skip the array of allocated/free element
indices if the objects are small enough and you don't need pointers into
them; just copy the "lastAllocated" element into the "newlyFreed" slot
when freeing, and always stick onto the end of the array.

An alternative, if your objects are "large" (so copying is undesirable) or
you need to keep pointers at particular elements, Alexandrescu's small
object allocator does most of this.

Allocate your pool of N elements.  reinterpret_cast the pointer to the
front of each element to an int and put my_index+1 into it.  (I.e. the
first 4 bytes of each element is the index of the next free element.  If
your object size is smaller than 4 bytes then adjust accordingly.)  Store
in the pool object a "first free", and init it to zero.

When you allocate an object, return the (constructed, if that's the way
you roll) first free element and set firstFree to what was in the first
four bytes of that element.

When you deallocate the object, destroy it as necessary, stick the value
of firstFree into the first four bytes and update firstFree to be
myAddress - baseAddress.

Now you can iterate through the free list in "random" order just by
following the indices.  You can't iterate the allocated list with this
setup, but you could certainly allocate a parallel bitfield that flagged
what was allocated and iterate that trivially.  I've done something to
this effect when I had to write a pooling allocator that allocated arrays
of these micro-objects.

The nice thing about this mechanism is that pointers to elements live for
the lifetime of the element as shuffling elements around means that
there's no (easy) way for people to hang onto one that they're interested
in.  On the other hand, if the objects are small and deallocation is rare
and nobody needs to know about one in particular (e.g. a particle system),
then clearly moving things around shouldn't be too terrible.  I believe
keeping a parallel bitfield would be more straight forward than an
unsorted array of free elements.

-tom!


------------------------------------------------------------------------------
Stay on top of everything new and different, both inside and
around Java (TM) technology - register by April 22, and save
$200 on the JavaOne (SM) conference, June 2-5, 2009, San Francisco.
300 plus technical and hands-on sessions. Register today.
Use priority code J9JMT32. http://p.sf.net/sfu/p
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list