Re: [Boost-users] boost::pool

Subject: Re: [Boost-users] boost::pool
From: Nigel Rantor (wiggly_at_[hidden])
Date: 2009-11-03 22:31:25

strasser_at_[hidden] wrote:
> Zitat von Frank Meerkoetter <frank_at_[hidden]>:
> 
>>> as is expected. you might want to look into using thread specific 
>>> pools, that
>>> only synchronize when a new pool block is allocated.
>>
>> could you please elaborate a bit on this? How would i do this with the
>> std::allocator implemenation provided by Boost.Pool?
> 
> the basic idea is to have an object pool for each thread, so that only 
> when the pool runs out of memory std::new is called and a mutex lock is 
> required. thread-local allocations can run concurrently.
> 
> you could use boost.pool for this, if none of your threads ever 
> deallocate an object that was allocated by another thread (and thus be 
> part of another pool). you`d have to write your own allocator I think.
> but boost.pool isn't suitable as a general purpose allocator anyway, 
> because of O(n) free().
> 
> that`s another thing that Pool2 should support. some kind of hierarchial 
> pool structure. when a pool runs out of memory it requests new memory 
> from its parent pool, and also pools deallocations and puts those back 
> into the right pool, so you don`t have the problem described above.
> 
> Zitat von Nigel Rantor <wiggly_at_[hidden]>:
>>
>> I would be really interested to hear more detailed critique of the 
>> current pool library from people who know/have used it.
>>
> 
> there`s nothing "wrong" with boost.pool in the sense that it has errors. 

That's why I carefully chose the word "critique" when asking for 
opinions. :-)

I realise you're coming at it from a time -complexity and generality 
point of view.

 > but it only supports a very limited use case:
 > pools of objects of the same type that are used to allocate objects
 > individually  but deallocated as a pool.

So would you really be suggesting augmenting the current set of 
facilities Pool provides then?

I assume this since it seems to me (please correct me if I'm wrong) that 
the current Pool implementation (based on the docs) does a decent job of 
providing small-object allocation with minimal overhead in terms of 
memory complexity, even if it can be slow for de-allocating individual 
items rather than an entire pool.

> here is (an outdated version of) the code I currently use, with O(1) 
> allocation and O(1) deallocation.
> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=intrusive_pool.hpp&directory=Memory& 
> 
> (don`t use it, that version still had bugs)
> 
> but like boost.pool, it only supports a few (other) use cases, it is not 
> a generic library.
> 
> here is an introduction to two allocation algorithms that pools could 
> use to support arbitrary-sized objects:
> http://www.boost.org/doc/libs/1_38_0/doc/html/interprocess/allocators_containers.html#interprocess.allocators_containers.memory_algorithms 

Reading the above interprocess docs was another reason why I assume 
you're really talking about augmenting Pool. Those allocators appear 
like they'd have significant overhead for small objects, which Pool 
doesn't currently (With the same caveats about me reading the Pool docs 
correctly).

So, if I understand correctly the wishlist is:

- O(1) de-allocation.

- Arbitrary sized allocations from a single pool.

- Better performance for MT.

I am tired so I'm going to be lazy and say that I can see how you could 
have multiple strategies in one library that allow people to pick their 
preference of time vs. space but I'm not immediately sure if you can 
make an allocation scheme that gives constant-time and space for all 
operations. Would need to actually spend some time thinking about it, 
seeing as it's not really my bag.

Regards,

   Nigel