Re: [Boost-users] O(1) free in boost::object_pool ?

From: Domagoj Babic (babic.domagoj_at_[hidden])
Date: 2008-08-05 19:40:59

Steven,

On Tue, Aug 5, 2008 at 3:13 PM, Steven Watanabe <watanabesj_at_[hidden]> wrote:
> An object_pool destroys all allocated objects when it is destroyed.
> In order to accomplish this, it uses a sorted free list and on destruction
> iterates over the storage and the free list in parallel destroying all
> objects not in the free list.

That's an interesting choice --- IMHO, it would be better to keep the
list unsorted,
and sort it before deallocation. Let's consider the associated costs:

N=number of calls to destroy()
M=size of the free list
C=total number of used chunks (containing live objects)

[1] current implementation
-----------------------------------
N calls to destroy: O(N*M)
deallocation of all objects: O(C + M)

[2] sorting before deallocation
---------------------------------------
N calls to destroy: O(N)
deallocation of all objects: O(C + M*log(M))

[2] seems like a clear winner to me, especially since destroy() is
probably going
to be called far far more frequently than purge_memory() [deallocates
all objects].
Am I getting this wrong?

Cheers,

-- 
 Domagoj Babic
 http://www.domagoj.info/
 http://www.calysto.org/