Re: [Algorithms] memory pool algorithms

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

Is the memory pool contiguous? If not, then it's kind of scary/impossible to have indexable access, but who knows? If it is contiguous, however, then you can use variants of a page table where the page size is the size of the type.

Also, you don't necessarily need a linked list for individual elements for iteration; you just need a way to know if a given slot is in use and the identifier used to access that slot. You can link those structures together if you allocate the storage for this pool in chunks (in the case of non-fixed pools).

Google "chris butcher index salt" without the quotes for some high level info as to how we do it.

MSN
-----Original Message-----
From: Pau...@sc... [mailto:Pau...@sc...]
Sent: Thursday, April 23, 2009 9:05 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] memory pool algorithms

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

> I think this will work:
>
> 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.

Thanks Jeremiah, thats excellent :) No linked lists, constant time
alloc/dealloc, element look up by index and its iterable (if there is such
a word). I guess the only thing is the order of elements as you iterate
through changes each time you dealloc, but thats unavoidable...

Cheers, Paul.
**********************************************************************
This email and any files transmitted with it are confidential and intended
solely for the use of the individual or entity to whom they are addressed.
If you have received this email in error please notify pos...@sc...
This footnote also confirms that this email message has been checked for
all known viruses.
Sony Computer Entertainment Europe Limited
Registered Office: 10 Great Marlborough Street, London W1F 7LP, United
Kingdom
Registered in England: 3277793
**********************************************************************
P Please consider the environment before printing this e-mail

-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.9.1 (Build 287)
Charset: US-ASCII

wsBVAwUBSfCQk3ajGqjtoMHxAQjk/QgAqBwe74v42L2XJJQeDgSNQVEb2gpiiD4C
rr/0OOE4yMnUuSWfJXfjSDMq0Q9uoqProyJKrB7oLkc8CDrQ02Qc605a53uKab2p
IbJQthcxSOvcbn7SsEgH8nu/zEyD/0TbhZRLa4ZwBM/W50tm2Q6z0zhRpLLApx59
OJ39xtu1fkuzIoz1+fRnijNN1U7c6z/1re6x4eUZAKQLI9SavKqehmt0yzZqr7s7
o8kwtF2R/VzkWjaqilgbecBwbA4GO2ZjL417Qq3Obmr51l0G5WKLOfQZG7lfFAms
QV/DL0g+wJ9t7fogopnUQhSW6cSFpCACzQSpIx8T/cyKa8qMIh+BJQ==
=AxZj
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
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