Thread: [Algorithms] memory pool algorithms
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: <Pau...@sc...> - 2009-04-23 12:44:18
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hi Guys, 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? We have a class which gives us everything but the last two together. We can add a linked list of used elements (giving us the iteration) but then you can't retrieve by index in constant time. Or we can retrieve by index in constant time but then you can't iterate cleanly because there will be holes in the memory pool. 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 wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N 11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H 6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ== =8a/D -----END PGP SIGNATURE----- |
|
From: Jeremiah Z. <jer...@vo...> - 2009-04-23 13:57:13
|
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. -----Original Message----- From: Pau...@sc... [mailto:Pau...@sc...] Sent: Thursday, April 23, 2009 7:06 AM To: gda...@li... Subject: [Algorithms] memory pool algorithms -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 Hi Guys, 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? We have a class which gives us everything but the last two together. We can add a linked list of used elements (giving us the iteration) but then you can't retrieve by index in constant time. Or we can retrieve by index in constant time but then you can't iterate cleanly because there will be holes in the memory pool. 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 wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N 11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H 6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ== =8a/D -----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-lis t |
|
From: <Pau...@sc...> - 2009-04-23 16:00:32
|
-----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----- |
|
From: Mat N. <mat...@bu...> - 2009-04-23 16:32:54
|
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 |
|
From: Alen L. <ale...@cr...> - 2009-04-23 19:38:38
|
Thursday, April 23, 2009, 6:32:35 PM, Mat wrote: > Is the memory pool contiguous? If not, then it's kind of > scary/impossible to have indexable access, but who knows? Unless you keep a separate index table which can be contiguous. If the objects are large and/or you cannot afford to move them around, because someone has pointers to them, it is useful to allocate the objects any way you fancy, and then keep a contiguous table of index-to-pointer mappings in the ways previously described. If you are doing random deletion, you will need to store pointer-to-index mapping together with the object in that case. Alen |
|
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 |
|
From: Tom P. <ga...@fa...> - 2009-04-23 16:52:41
|
> 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! |
|
From: Mat N. <mat...@bu...> - 2009-04-23 17:24:53
|
> 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 |
|
From: Alan L. <ram...@gm...> - 2009-04-23 22:12:06
|
Adding hierarchy to your "free" bit-vector can make this really fast, and touch only a few cache-lines per alloc/free (even for huge pools). You need hardware clz tho. Alan. ----- Original Message ----- From: "Mat Noguchi" <mat...@bu...> To: "Game Development Algorithms" <gda...@li...> Sent: Friday, April 24, 2009 3:24 AM Subject: Re: [Algorithms] memory pool algorithms >> I believe > keeping a parallel bitfield would be more straight forward than an > unsorted array of free elements. |
|
From: <Pau...@sc...> - 2009-04-24 08:49:32
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > 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. Ahh yes, the old particle system trick :) > 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. So with the parallel bit-field, each bit indicates whether the element has been allocated, and when you iterate over all elements you skip elements without a set bit? 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 wsBVAwUBSfF21XajGqjtoMHxAQhB/AgAqmD3jNwpjDdAx818d8KrwC3vs91b6nxw gQ7T+2wUN2xjtaG24U8Xt/s80VmZbkKd63EVhCn9cjqcT8qy3gSoMH3NvG9W15Jr qRPFGeWZDsv0WFad9Ir0OPuSNDmIc/yX5VmgqducxopuK81laD6MLC+GPZ9KYd/f nH92g25fzr3lKWgN+ML7oGcpxHOjFj92U/bS7hy16nRDOtKXIaRt00acku+zhmu3 J56YMeQFGZ6sfBF+QusSvF4R+c+UZej4MP3rzuJymY2IXRWBzO3Igy5tMLiyOXDp n+XrJm2A7+L8bJ21oGgxLEQhLsPrOIv4r6umFQDZiFUYZkekUHbSVw== =uvC5 -----END PGP SIGNATURE----- |
|
From: Tom P. <ga...@fa...> - 2009-04-24 16:09:32
|
>> 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. > > So with the parallel bit-field, each bit indicates whether the element has > been allocated, and when you iterate over all elements you skip elements > without a set bit? That was my thinking, with the 30 seconds I spent on the problem. ;) I'm not sure if it's ideal, and I'm sure its power would show off differently in sparse vs. not allocation patterns, but compared to an array of integers that would require traversing the allocations in arbitrary order I think it would considerably outperform this. However, I'm also aware that setting bits in bitfields is horrifically slow on some platforms, so you'd probably want to write whatever your solution was in assembler so that you could optimally schedule memory reads and writes. (I did battle with a certain compiler this week on just this front, but my solution was to remove the need for the set bits at all.) -tom! -- |
|
From: Alan L. <ram...@gm...> - 2009-04-24 16:52:44
|
unless you add hierarchy to the bit-vector.. ----- Original Message ----- From: "Tom Plunket" <ga...@fa...> To: "Game Development Algorithms" <gda...@li...> Sent: Saturday, April 25, 2009 2:09 AM Subject: Re: [Algorithms] memory pool algorithms >>> 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. >> >> So with the parallel bit-field, each bit indicates whether the element >> has >> been allocated, and when you iterate over all elements you skip elements >> without a set bit? > > That was my thinking, with the 30 seconds I spent on the problem. ;) > > I'm not sure if it's ideal, and I'm sure its power would show off > differently in sparse vs. not allocation patterns, but compared to an > array of integers that would require traversing the allocations in > arbitrary order I think it would considerably outperform this. However, > I'm also aware that setting bits in bitfields is horrifically slow on some > platforms, so you'd probably want to write whatever your solution was in > assembler so that you could optimally schedule memory reads and writes. > (I did battle with a certain compiler this week on just this front, but my > solution was to remove the need for the set bits at all.) > > -tom! > > -- > > > > ------------------------------------------------------------------------------ > Crystal Reports - New Free Runtime and 30 Day Trial > Check out the new simplified licensign option that enables unlimited > royalty-free distribution of the report engine for externally facing > server and web deployment. > http://p.sf.net/sfu/businessobjects > _______________________________________________ > 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 > |
|
From: Mat N. <mat...@bu...> - 2009-04-24 17:10:10
|
You still pay the cost for a variable shift when setting a bit on some platforms. MSN -----Original Message----- From: Alan Latham [mailto:ram...@gm...] Sent: Friday, April 24, 2009 9:53 AM To: Game Development Algorithms Subject: Re: [Algorithms] memory pool algorithms unless you add hierarchy to the bit-vector.. ----- Original Message ----- From: "Tom Plunket" <ga...@fa...> To: "Game Development Algorithms" <gda...@li...> Sent: Saturday, April 25, 2009 2:09 AM Subject: Re: [Algorithms] memory pool algorithms >>> 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. >> >> So with the parallel bit-field, each bit indicates whether the element >> has >> been allocated, and when you iterate over all elements you skip elements >> without a set bit? > > That was my thinking, with the 30 seconds I spent on the problem. ;) > > I'm not sure if it's ideal, and I'm sure its power would show off > differently in sparse vs. not allocation patterns, but compared to an > array of integers that would require traversing the allocations in > arbitrary order I think it would considerably outperform this. However, > I'm also aware that setting bits in bitfields is horrifically slow on some > platforms, so you'd probably want to write whatever your solution was in > assembler so that you could optimally schedule memory reads and writes. > (I did battle with a certain compiler this week on just this front, but my > solution was to remove the need for the set bits at all.) > > -tom! > > -- > > > > ------------------------------------------------------------------------------ > Crystal Reports - New Free Runtime and 30 Day Trial > Check out the new simplified licensign option that enables unlimited > royalty-free distribution of the report engine for externally facing > server and web deployment. > http://p.sf.net/sfu/businessobjects > _______________________________________________ > 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 > ------------------------------------------------------------------------------ Crystal Reports - New Free Runtime and 30 Day Trial Check out the new simplified licensign option that enables unlimited royalty-free distribution of the report engine for externally facing server and web deployment. http://p.sf.net/sfu/businessobjects _______________________________________________ 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 |
|
From: Alen L. <ale...@cr...> - 2009-04-23 14:17:28
|
Depends on what you call a pool, but if you use a linear part of
memory for a pool, I believe you can use a two-way mapping between
addresses (with holes) and indices (without holes) to burn some extra
memory up front and gain O(1) in return: (warning, untested code!)
- n - max size
- P[n] - pool of preallocated elements
- I2A[n] - array of index to address mappings
- A2I[n] - array of address to index mappings
- F[n] - array of free addresses
- cf - count of free indices
- c - current allocated count
initialize:
fill F with 0..n-1 (or reverse, if you prefer)
cf = n
c = 0
allocate:
a = F[--cf]
I2A[c] = a
A2I[a] = c++
return a
freebyaddress(a)
F[cf++] = a
i = A2I[a]
I2A[i] = I2A[--c]
// iteration...
for(i=0;i<c;i++) {
whatever(P[I2A[i]])
}
NOTE: address of an element is constant through its lifetime (between
alloc and free), while index can change.
There are probably some errors by one above, but I hope the idea makes sense.
:)
HTH,
Alen
Paul wrote at 4/23/2009:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
> Hi Guys,
> 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?
> We have a class which gives us everything but the last two together. We
> can add a linked list of used elements (giving us the iteration) but then
> you can't retrieve by index in constant time. Or we can retrieve by index
> in constant time but then you can't iterate cleanly because there will be
> holes in the memory pool.
> 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
> wsBVAwUBSfBYiXajGqjtoMHxAQjWewf+IQzmRj6+gox+qbzxG7tZ+AktKgCTDC+N
> 11Wgf8Pjo7szCdWTa3fk00T9mbNmNAtfuyFlo6tFUC310ggVETI7uItg1Enjy7/H
> 6unAfH1Nt14yUBI3bNZjOENXiB3ypP7EEY1wnFtSLeOTugNjUS8/xEyngv0JSiqV
> KXwg85XYpvJK5UoR4IrW3obyvaDJ+rWArRNAb167xCH80KlrrXFleVDLgPrjGRmJ
> vO202p2FNCNB6BsmuEK0LHWxG1n/A7sJKHlvPF32Ow5ADoMo2MxuzN7bos5hw3Yy
> CVrTKImbAP6Y3wf/vIE9HYUlZW9lwWctGOVziOLXQRAMSHkPwyNxbQ==
> =8a/D
> -----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
--
Alen
|
|
From: <Pau...@sc...> - 2009-04-23 16:56:35
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 > NOTE: address of an element is constant through its lifetime (between > alloc and free), while index can change. > > There are probably some errors by one above, but I hope the idea makes sense. > :) Thanks Alen, I *think* this is the same solution that Jeremiha posted and looks like it will suit my purposes nicely :) 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 wsBVAwUBSfCXf3ajGqjtoMHxAQhieQf/VY6t9XBSm7Icwcqgqy/nQI+NXDvRRkYP Trbgmv7+lbcIB5ZMbZHwnOcWJTTtujXCUIN8Lc5WN6ftvLLntkt3FZXKyMXfSiGQ SxGjYjdVHa7EW9/5IbYC2ZvnmhQ9DoZncv/hq60WYAxJSwmQy1NVgxjSKwYehjRp vEcZAWJUQADynEs/Up2MdoBnSPFfkl97lY2Bq0C1llqrHz0bGeo5B2Q71LUNJgBB 6Khq2pdEX+K7ORLVKTBJWud1rnmZXCqA9b9JaugK6EKQwym7GTMoah4XrKAEIsug 8uOz5dpl2O1FmsVpk61NBo6IInXnX08gTJSLOOzpNXd2lrChkCdNHA== =U1Xi -----END PGP SIGNATURE----- |
|
From: Alen L. <ale...@cr...> - 2009-04-23 19:54:31
|
Thursday, April 23, 2009, 6:34:16 PM, Paul wrote: > Thanks Alen, I *think* this is the same solution that Jeremiha posted and > looks like it will suit my purposes nicely Yes, I think it is the same. My ISP was down, so I didn't see Jeremiah has posted already before me. :) I like the neat trick of joining the used and free arrays into one. Also note the difference in the address-to-index mapping. That mapping is necessary if the objects are going to be referenced from the outside, because the indices change at deallocation. If you are going to reference and delete the objects only through iteration, then you don't need it. Cheers, Alen |
|
From: Olivier G. <gal...@po...> - 2009-04-23 15:02:20
|
On Thu, Apr 23, 2009 at 01:05:39PM +0100, Pau...@sc... wrote: > 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? > > We have a class which gives us everything but the last two together. We > can add a linked list of used elements (giving us the iteration) but then > you can't retrieve by index in constant time. Or we can retrieve by index > in constant time but then you can't iterate cleanly because there will be > holes in the memory pool. Could you define "retrieve by index" further? Do you mean that if "n" elements are allocated they must be reachable by a number with 0 and n-1? If yes, you obviously can't have constant-time deletion, since you'll have a mean of n/2 references to change for every deletion. And if you allow holes to get constant-time deletion, what properties do you want from your index that a pointer would not have? OG. |
|
From: Tom P. <ga...@fa...> - 2009-04-23 18:44:10
|
> Could you define "retrieve by index" further? Do you mean that if "n" > elements are allocated they must be reachable by a number with 0 and > n-1? If yes, you obviously can't have constant-time deletion, since > you'll have a mean of n/2 references to change for every deletion. > And if you allow holes to get constant-time deletion, what properties > do you want from your index that a pointer would not have? You only need to swap the last element into the deleted element, unless the order of the elements need to match the order of allocation. Hence O(1) for all operations, and it can be highly memory-efficient as well. -tom! |
|
From: Niklas F. <ni...@gr...> - 2009-04-23 16:40:46
|
Pau...@sc... wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> Hi Guys,
>
> 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?
Something like this perhaps. Constant time allocation, deallocation,
retrieval and cache-friendly iteration with no holes. Code sketch in ruby:
(Note: Written for clarity rather than completely optimized. In an
optimized version the freelist would be stored in-place in the @indices
array, for instance.)
class IDArray
def initialize
@objects = []
@ids = []
@indices = []
@freelist = []
end
def insert(o)
i = @objects.size
if @freelist.empty?
id = @indices.size
else
id = @freelist.pop
end
@objects.push(o)
@ids.push(id)
@indices[id] = i
return id
end
def lookup(id)
return @objects[@indices[id]]
end
def remove(id)
i = @indices[id]
@objects[i] = @objects.last
@ids[i] = @ids.last
@objects.pop
@ids.pop
@indices[@ids[i]] = i
@indices[id] = nil
@freelist.push(id)
end
def each()
@objects.each {|o| yield o}
end
end
// Niklas
|
|
From: Jon W. <jw...@gm...> - 2009-04-23 17:52:30
|
Why can't you use both an index and a list? Would the overhead be prohibitive? Sincerely, jw Pau...@sc... wrote: > 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? > > We have a class which gives us everything but the last two together. We > can add a linked list of used elements (giving us the iteration) but then > you can't retrieve by index in constant time. Or we can retrieve by index > in constant time but then you can't iterate cleanly because there will be > holes in the memory pool. > > |
|
From: Jon W. <jw...@gm...> - 2009-04-23 17:58:35
|
Olivier Galibert wrote: > Could you define "retrieve by index" further? Do you mean that if "n" > elements are allocated they must be reachable by a number with 0 and > n-1? If yes, you obviously can't have constant-time deletion, since > A hash table actually gives you all of the above, no? And, in fact, a hash table with chaining and a proper iterator can give you iteration of all the members, too (although in random (hash) order). Sincerely, jw |
|
From: Tom P. <ga...@fa...> - 2009-04-23 18:58:38
|
> A hash table actually gives you all of the above, no? And, in fact, a > hash table with chaining and a proper iterator can give you iteration of > all the members, too (although in random (hash) order). Hash what? A linked list would be the same thing if you assume order is irrelevant, but I would think the memory incoherency would be undesirable if trivially avoidable. -tom! -- |
Thanks for helping keep SourceForge clean.
X