RE: [Boost-Users] object_pool, O(N) destroy?
Thanks for the Info Steve, In this case, I am less interested in the pool's destructor as I _should_ have a 1 to 1 on malloc()ing and destroying the individual objects (if all goes well...). The pool will only be destroyed once during the lifetime of the application so I could probably suffer a O(N^2) pool destructor. I will try what you recommend in your postscript. Thanks again.. Kevin\ -----Original Message----- From: scleary@jerviswebb.com [mailto:scleary@jerviswebb.com] Sent: Monday, January 28, 2002 2:10 PM To: Boost-Users@yahoogroups.com Cc: shammah@voyager.net Subject: RE: [Boost-Users] object_pool, O(N) destroy?
From: kevin_godden@agilent.com [mailto:kevin_godden@agilent.com]
I am considering using boost::object_pool for fast allocation and deallocation of likkle container/token objects. I need to make this as fast as possible, to this end I wonder why object_pool seems to use boost::pool::ordered_free() (O(N)) rather than the faster free() (O(1))?
There must be a reason, but I can't seem to find it in the Lib's documentation.
The object_pool keeps its free list ordered because of the requirements of its destructor. Its destructor steps through the free list, calling the destructor for any objects that weren't freed. The current algorithm is O(N) because the free list is ordered; if it wasn't ordered, it would be O(N^2). I'll document this in the code. -Steve P.S. An object_pool without the destructor behaviour may be what you want. Boost.Pool doesn't provide one, but you could just cut & paste the object_pool, remove the destructor, and change ordered_malloc/ordered_free to the regular malloc/free (you also won't need nextof). Just note that if you ever construct something from that pool and don't destruct it, you enter the fun realm of undefined behaviour... :) Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
It sounds like a case where a type trait, identifying the need for the pool to responsible for deletion, would be appropriate. Then objects which did not need to be destroyed (e.g. ptrs, "plain" structs) could be handled by optimized code. But that's more work than cut and paste. Craig Hicks kevin_godden@agilent.com wrote:
Thanks for the Info Steve,
In this case, I am less interested in the pool's destructor as I _should_ have a 1 to 1 on malloc()ing and destroying the individual objects (if all goes well...). The pool will only be destroyed once during the lifetime of the application so I could probably suffer a O(N^2) pool destructor. I will try what you recommend in your postscript.
Thanks again..
Kevin\
-----Original Message----- From: scleary@jerviswebb.com [mailto:scleary@jerviswebb.com] Sent: Monday, January 28, 2002 2:10 PM To: Boost-Users@yahoogroups.com Cc: shammah@voyager.net Subject: RE: [Boost-Users] object_pool, O(N) destroy?
From: kevin_godden@agilent.com [mailto:kevin_godden@agilent.com]
I am considering using boost::object_pool for fast allocation and deallocation of likkle container/token objects. I need to make this as
fast
as possible, to this end I wonder why object_pool seems to use boost::pool::ordered_free() (O(N)) rather than the faster free() (O(1))?
There must be a reason, but I can't seem to find it in the Lib's documentation.
The object_pool keeps its free list ordered because of the requirements of its destructor. Its destructor steps through the free list, calling the destructor for any objects that weren't freed. The current algorithm is O(N) because the free list is ordered; if it wasn't ordered, it would be O(N^2).
I'll document this in the code.
-Steve
P.S. An object_pool without the destructor behaviour may be what you want. Boost.Pool doesn't provide one, but you could just cut & paste the object_pool, remove the destructor, and change ordered_malloc/ordered_free to the regular malloc/free (you also won't need nextof). Just note that if you ever construct something from that pool and don't destruct it, you enter the fun realm of undefined behaviour... :)
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Info: <http://www.boost.org> Wiki: <http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl> Unsubscribe: <mailto:boost-users-unsubscribe@yahoogroups.com>
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
[Non-text portions of this message have been removed]
participants (1)
-
hicks -
kevin_godden＠agilent.com