boost::pool

[Hansi Hansi]

Hello,

In my application I have a lot of small objects. For that I thought that
it is the best to use an object pool..I have read the docu of
object_pool...but I don't understand really how I have to use it..

Can one give me some hints?
Another thing that I don't understand..Need I to know already during
compiletime the max. number of objects?

Regards
Hansi

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Steven Watanabe-4]

AMDG

Hansjoerg wrote:
> In my application I have a lot of small objects. For that I thought
> that it is the best to use an object pool..I have read the docu of
> object_pool...but I don't understand really how I have to use it..

{
    boost::object_pool<int> pool;
    for(int i = 0; i < 100; ++i) {
        int* ip = pool.malloc();
    }
} // all allocated objects freed here

> Another thing that I don't understand..Need I to know already during
> compiletime the max. number of objects?

No.  object_pool will allocate more memory on demand.

In Christ,
Steven Watanabe



_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Am Monday 02 November 2009 15:15:00 schrieb Hansjoerg:
> Hello,
>
> In my application I have a lot of small objects. For that I thought that
> it is the best to use an object pool..I have read the docu of
> object_pool...but I don't understand really how I have to use it..

I'd consider using another library, or allocate your objects in bulk yourself
and, e.g. store the unused objects in a boost::intrusive::slist until they're
needed.
boost::object_pool has some major problems, e.g. linear complexity of free().
the library is a decade old and I don't think it would be accepted if it was
reviewed as it is today.
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Diederick C. Niehorster-2]

Hi Stefan,

In that case, wouldn't (shouldn't) it be possible to request a
re-review of libraries alreayd accepted, provided there is good
reason? In other words, as standards evolve, is there a mechanism by
which libraries no longer up to par can be removed from
boost/deprecated/marked as no longer officially endorsed, something
like that (I can see that simply removing them would make people
depending on them very unhappy).

Best,
Dee

On Tue, Nov 3, 2009 at 2:16 AM, Stefan Strasser <strasser@...> wrote:

> Am Monday 02 November 2009 15:15:00 schrieb Hansjoerg:
>> Hello,
>>
>> In my application I have a lot of small objects. For that I thought that
>> it is the best to use an object pool..I have read the docu of
>> object_pool...but I don't understand really how I have to use it..
>
> I'd consider using another library, or allocate your objects in bulk yourself
> and, e.g. store the unused objects in a boost::intrusive::slist until they're
> needed.
> boost::object_pool has some major problems, e.g. linear complexity of free().
> the library is a decade old and I don't think it would be accepted if it was
> reviewed as it is today.
> _______________________________________________
> Boost-users mailing list
> Boost-users@...
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Am Tuesday 03 November 2009 04:08:14 schrieb Diederick C. Niehorster:
> Hi Stefan,
>
> In that case, wouldn't (shouldn't) it be possible to request a
> re-review of libraries alreayd accepted, provided there is good
> reason? In other words, as standards evolve, is there a mechanism by
> which libraries no longer up to par can be removed from
> boost/deprecated/marked as no longer officially endorsed, something
> like that (I can see that simply removing them would make people
> depending on them very unhappy).

this was my personal opinion only, others may find Boost.Pool sufficient. I
don't know what the process is to deprecate a library, but I think the right
way is to submit Boost.Pool2.

I actually considered that, but while recreating the functionality of
Boost.Pool is pretty easy, given that Boost.Intrusive now exists, a generic
pool allocation library is some effort.
some things that come to mind is multiple allocation algorithms to meet
different time complexity and memory overhead needs, pools that allow
allocation of different-sized objects,  maybe even a generic "allocation
algorithm" library that is not limited to chunks of memory, but can be used
for disk space and other arbitrary ranges, like allocating IDs.

> >
> > I'd consider using another library, or allocate your objects in bulk
> > yourself and, e.g. store the unused objects in a boost::intrusive::slist
> > until they're needed.
> > boost::object_pool has some major problems, e.g. linear complexity of
> > free(). the library is a decade old and I don't think it would be
> > accepted if it was reviewed as it is today.

_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Frank Meerkötter]

On Tuesday 03 November 2009 05:45:48 Stefan Strasser wrote:
> Am Tuesday 03 November 2009 04:08:14 schrieb Diederick C. Niehorster:
> I actually considered that, but while recreating the functionality of
> Boost.Pool is pretty easy, given that Boost.Intrusive now exists, a generic
> pool allocation library is some effort.
> some things that come to mind is multiple allocation algorithms to meet
> different time complexity and memory overhead needs, pools that allow
> allocation of different-sized objects,  maybe even a generic "allocation
> algorithm" library that is not limited to chunks of memory, but can be used
> for disk space and other arbitrary ranges, like allocating IDs.

I recently tried to use the std::allocator drop-in replacement from Boost.Pool
in a massively multithreaded program running on a machine with a lot of cores.
The result was very disappointing. I found my threads being serialized along
the std::allocator interface (same problem as with the std::allocator from my
STL).

A nice feature for Boost.Pool would be the ability to scale in multithreaded
environments (like for example the tbb::scaleable_allocator from the Intel
Threading Building Blocks).

KR,
    Frank
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Am Tuesday 03 November 2009 07:17:18 schrieb frank:

> On Tuesday 03 November 2009 05:45:48 Stefan Strasser wrote:
> > Am Tuesday 03 November 2009 04:08:14 schrieb Diederick C. Niehorster:
> > I actually considered that, but while recreating the functionality of
> > Boost.Pool is pretty easy, given that Boost.Intrusive now exists, a
> > generic pool allocation library is some effort.
> > some things that come to mind is multiple allocation algorithms to meet
> > different time complexity and memory overhead needs, pools that allow
> > allocation of different-sized objects,  maybe even a generic "allocation
> > algorithm" library that is not limited to chunks of memory, but can be
> > used for disk space and other arbitrary ranges, like allocating IDs.
>
> I recently tried to use the std::allocator drop-in replacement from
> Boost.Pool in a massively multithreaded program running on a machine with a
> lot of cores. The result was very disappointing.

as is expected. you might want to look into using thread specific pools, that
only synchronize when a new pool block is allocated.

>
> A nice feature for Boost.Pool would be the ability to scale in
> multithreaded environments (like for example the tbb::scaleable_allocator
> from the Intel Threading Building Blocks).

if we could put together a team for Pool2 I'd certainly take part in it, but
it is too much effort for one person, considering that you can write
something like that for your own needs, in a non-generic way, in a few
hundred lines.
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Frank Meerkötter]

Zitat von Stefan Strasser <strasser@...>:

> Am Tuesday 03 November 2009 07:17:18 schrieb frank:
>> On Tuesday 03 November 2009 05:45:48 Stefan Strasser wrote:
>> > Am Tuesday 03 November 2009 04:08:14 schrieb Diederick C. Niehorster:
>> > I actually considered that, but while recreating the functionality of
>> > Boost.Pool is pretty easy, given that Boost.Intrusive now exists, a
>> > generic pool allocation library is some effort.
>> > some things that come to mind is multiple allocation algorithms to meet
>> > different time complexity and memory overhead needs, pools that allow
>> > allocation of different-sized objects,  maybe even a generic "allocation
>> > algorithm" library that is not limited to chunks of memory, but can be
>> > used for disk space and other arbitrary ranges, like allocating IDs.
>>
>> I recently tried to use the std::allocator drop-in replacement from
>> Boost.Pool in a massively multithreaded program running on a machine with a
>> lot of cores. The result was very disappointing.
>
> 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?

KR,
    Frank


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Diederick C. Niehorster-2]

>
> if we could put together a team for Pool2 I'd certainly take part in it, but
> it is too much effort for one person, considering that you can write
> something like that for your own needs, in a non-generic way, in a few
> hundred lines.

Hi Stefan,

I must say this is way beyond my reach (I'm not trained in programming
or CS in general at all). Maybe there should be a place on the Boost
website where these kind of projects or requests for team members
could be put?

There must be more relatively old code that could use a refresh/thorough look.

Best,
Dee
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Nigel Rantor]

Diederick C. Niehorster wrote:

>> if we could put together a team for Pool2 I'd certainly take part in it, but
>> it is too much effort for one person, considering that you can write
>> something like that for your own needs, in a non-generic way, in a few
>> hundred lines.
>
> Hi Stefan,
>
> I must say this is way beyond my reach (I'm not trained in programming
> or CS in general at all). Maybe there should be a place on the Boost
> website where these kind of projects or requests for team members
> could be put?
>
> There must be more relatively old code that could use a refresh/thorough look.

I have not used pool yet but I'm currently working on a project that,
based on profiling, might benefit from something like pool.

I would be really interested to hear more detailed critique of the
current pool library from people who know/have used it.

At the moment I also have some amount of free time so might be
interested in helping out if it sounds like something I could usefully
work on.

   n
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Zitat von Frank Meerkoetter <frank@...>:

>> 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@...>:
>
> 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. 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.

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


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Nigel Rantor]

strasser@... wrote:

> Zitat von Frank Meerkoetter <frank@...>:
>
>>> 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@...>:
>>
>> 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
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Frank Meerkötter]

Zitat von strasser@...:

> Zitat von Frank Meerkoetter <frank@...>:
>
>>> 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().

Thanks for your explanation. The property that objects that are allocated
in one thread must never be deallocated by a different thread is a show
stopper
for me. My current system is designed as a pipeline.

KR,
    Frank






_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Am Wednesday 04 November 2009 04:31:25 schrieb Nigel Rantor:

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

well, these are the points that _I_ am missing. I did not research this topic,
so there might be many other algorithms with different memory and time
complexity characteristics.
from what I understand there are also other libraries for that task, at least
I was recommended a google library when I brought up this topic earlier. I
didn't look at it though.

after researching what is out there and more "wishlists" other that mine, one
could decide if the current boost.pool interface/concepts is sufficient and
could be kept. I had a short look at the implementation of boost.pool and I
would not try to ammend the implementation. there are easier ways to
implement that sort of thing, particularily using Boost.Intrusive.


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

exactly.

> but I'm not immediately sure if you can
> make an allocation scheme that gives constant-time and space for all
> operations.

no you can't. (if you meant 0 memory overhead)
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Roman Shmelev]

I want the following type of pool in the wishlist:
Allowing to allocate misc-size memory blocks without an ability to
delete them (I mean they will are deleted on pool destruction).
I met some situations where such pool was really what needed.
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Jonathan Franklin]

On Thu, Nov 5, 2009 at 9:31 AM, Roman Shmelev <rshmelev@...> wrote:
> I want the following type of pool in the wishlist:
> Allowing to allocate misc-size memory blocks without an ability to
> delete them (I mean they will are deleted on pool destruction).
> I met some situations where such pool was really what needed.

I actually did this at one time w/ the boost::pool by making my
requested_size 1 byte, then doing an ordered_malloc(num_bytes).

I'm not claiming that this is a good or a bad idea.  But it did work.

Jon
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Roman Shmelev]

> I actually did this at one time w/ the boost::pool by making my
> requested_size 1 byte, then doing an ordered_malloc(num_bytes).
>
> I'm not claiming that this is a good or a bad idea.  But it did work.

Heh. And I've written my own class-bicycle, allocating some fixed-size
big chunks with boost::pool and then cutting needed blocks from them.
But there are many stones and details, like memory aligning, or making
object_pool from such pool.
So, probably professionally-written solution will cover such problems.
_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Stefan Strasser-2]

Zitat von Jonathan Franklin <franklin.jonathan@...>:

> On Thu, Nov 5, 2009 at 9:31 AM, Roman Shmelev <rshmelev@...> wrote:
>> I want the following type of pool in the wishlist:
>> Allowing to allocate misc-size memory blocks without an ability to
>> delete them (I mean they will are deleted on pool destruction).
>> I met some situations where such pool was really what needed.
>
> I actually did this at one time w/ the boost::pool by making my
> requested_size 1 byte, then doing an ordered_malloc(num_bytes).
>
> I'm not claiming that this is a good or a bad idea.  But it did work.
>

I think roman's point was the automatic destruction of different  
object types on pool destruction.
an implementation of that would e.g. look like this:

struct object_base{
   virtual ~object_base() = 0;
   virtual object_base *next() = 0;
};

template<class T>
struct object : object_base{
   T user_object;
   virtual ~object(){}
   virtual object_base *next(); //returns this + 1 and takes care of alignment
};

with new objects just added to the end of the block.


_______________________________________________
Boost-users mailing list
Boost-users@...
http://lists.boost.org/mailman/listinfo.cgi/boost-users