I took a closer look at Boost.Pool today to replace some default allocation of small objects. what I found there was a little disappointing, at least for my use case. the object_pool has 2 major downsides: - no dynamic block allocation - destroying one(!) object is O(N), with N being the number of unused objects in the pool so I wrote some code for my own use. I'm not suggesting this code should be added to boost, but something like it. struct A{ ... }; { pool<A,100> pool; A *a; for(int c=0;c<250;++c){ a=pool.new_(); // O(1) } pool.delete_(a); //O(1), destructs } //destruction of 249 objects, O(N) this allocates 3 memory blocks. but it also has one pointer memory overhead per object, to achieve constant time deletion. but you can use that pointer while the object is in use, which was what lead to this code: I needed to store unused boost.intrusive nodes: struct A : intrusive::[s]list_base_hook<>{ ... }; { [s]list_pool<A,[s]list_base_hook<>,100> pool; //same as above } this has no memory overhead, as the list hook can be used by the pool. here's the code: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=intrusive_pool.hpp&directory=Memory&
Have you considered/evaluated dlmalloc? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode On Wed, Sep 23, 2009 at 6:55 PM, Stefan Strasser <strasser@uni-bremen.de> wrote:
I took a closer look at Boost.Pool today to replace some default allocation of small objects.
what I found there was a little disappointing, at least for my use case.
the object_pool has 2 major downsides: - no dynamic block allocation - destroying one(!) object is O(N), with N being the number of unused objects in the pool
so I wrote some code for my own use. I'm not suggesting this code should be added to boost, but something like it.
struct A{ ... };
{ pool<A,100> pool; A *a; for(int c=0;c<250;++c){ a=pool.new_(); // O(1) } pool.delete_(a); //O(1), destructs } //destruction of 249 objects, O(N)
this allocates 3 memory blocks. but it also has one pointer memory overhead per object, to achieve constant time deletion. but you can use that pointer while the object is in use, which was what lead to this code: I needed to store unused boost.intrusive nodes:
struct A : intrusive::[s]list_base_hook<>{ ... };
{ [s]list_pool<A,[s]list_base_hook<>,100> pool; //same as above }
this has no memory overhead, as the list hook can be used by the pool.
here's the code: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=intrusive_pool.hpp&directory=Memory& _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Am Thursday 24 September 2009 23:30:18 schrieb OvermindDL1:
On Tue, Sep 22, 2009 at 7:17 PM, Emil Dotchevski
<emildotchevski@gmail.com> wrote:
Have you considered/evaluated dlmalloc?
Or tcmalloc? (Google's memory pool/alloctor, amazing time efficiency)
external library suggestions are appreciated but besides the point, since this code is part of a boost library proposal. don't you think Boost.Pool is missing something here? something that's not very hard to write, since there is Boost.Intrusive, so you can implement allocation algorithms quite easily. even pools that support allocation of arbitrary sized objects using an intrusive set and an allocation algorithm like the ones deployed by Boost.Interprocess here: http://www.boost.org/doc/libs/1_35_0/doc/html/interprocess/allocators_contai... I've used something similar for a disk space allocator: typedef set_base_hook<tag<by_size_tag> > by_size_hook; typedef set_base_hook<tag<by_offset_tag> > by_offset_hook; struct free_block : by_size_hook,by_offset_hook ... intrusive::multiset<free_block,base_hook<by_size_hook>... intrusive::set<free_block,base_hook<by_offset_hook>... allocation and deallocation of arbitrary sized blocks in O(log N), with block merging and block splitting. in a few hundred lines of code.
On Thu, Sep 24, 2009 at 6:28 PM, Stefan Strasser <strasser@uni-bremen.de> wrote:
Am Thursday 24 September 2009 23:30:18 schrieb OvermindDL1:
On Tue, Sep 22, 2009 at 7:17 PM, Emil Dotchevski
<emildotchevski@gmail.com> wrote:
Have you considered/evaluated dlmalloc?
Or tcmalloc? (Google's memory pool/alloctor, amazing time efficiency)
external library suggestions are appreciated but besides the point, since this code is part of a boost library proposal. don't you think Boost.Pool is missing something here? something that's not very hard to write, since there is Boost.Intrusive, so you can implement allocation algorithms quite easily. even pools that support allocation of arbitrary sized objects using an intrusive set and an allocation algorithm like the ones deployed by Boost.Interprocess here: http://www.boost.org/doc/libs/1_35_0/doc/html/interprocess/allocators_contai...
I've used something similar for a disk space allocator:
typedef set_base_hook<tag<by_size_tag> > by_size_hook; typedef set_base_hook<tag<by_offset_tag> > by_offset_hook; struct free_block : by_size_hook,by_offset_hook ... intrusive::multiset<free_block,base_hook<by_size_hook>... intrusive::set<free_block,base_hook<by_offset_hook>...
allocation and deallocation of arbitrary sized blocks in O(log N), with block merging and block splitting. in a few hundred lines of code.
Actually something like Google's pool allocator is quite simple, I actually created one very much like it years ago, would be quite interesting to create another Boost.Pool that gave similar functionality to it, would round out the Boost.Pool's quite well. :) But yea, Boost.Pool itself does need some enhancements, needed them for a long time, that is why I wrote my own a long time ago, ran much faster.
participants (3)
-
Emil Dotchevski -
OvermindDL1 -
Stefan Strasser