RE: [Boost-Users] object_pool, O(N) destroy?

From: scleary_at_[hidden]
Date: 2002-01-28 09:10:15

> From: kevin_godden_at_[hidden] [mailto:kevin_godden_at_[hidden]]
> 
> 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... :)