Re: [Algorithms] memory pool algorithms
Brought to you by:
vexxed72
Menu
▾
▴
Re: [Algorithms] memory pool algorithms
|
From: Mat N. <mat...@bu...> - 2009-04-23 16:34:29
|
Or go here: http://www.bungie.net/images/Inside/publications/presentations/publicationsdes/engineering/butcher_gametech04.pdf This is a presentation on Halo 2's architecture which has a few slides on how we handle what you are describing. MSN -----Original Message----- From: Mat Noguchi Sent: Thursday, April 23, 2009 9:33 AM To: Game Development Algorithms Subject: RE: [Algorithms] memory pool algorithms 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 |
