Re: [boost] [pool] an O(1) implementation of object_pool::destroy()

Subject: Re: [boost] [pool] an O(1) implementation of object_pool::destroy()
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2009-02-06 00:42:40

Steven Watanabe wrote:
> AMDG
> 
> Ben Muzal wrote:
>> I was looking at object_pool and noticed that there is a way to make
>> object_pool::destroy() an O(1) operation instead of an O(n) operation.
>>
>> If I understand the problem correctly, object_pool::destroy() is O(n)
>> because it keep the free list sorted. It keeps the free list sorted so
>> that object_pool::~object_pool() runs in O(n) time instead of in
>> O(n^2) time. However, I believe there is an implementation of
>> object_pool::~object_pool() that will run in O(n) time without
>> requiring a sorted free list.
>>
>> My suggestion is that ~object_pool() could use a mark-sweep strategy:
>> It would first step through the free list and mark each free chunk as
>> such. It would then go back and examine each chunk in the pool and
>> call the destructor on the ones not marked as free. The each chunk's
>> 'next' pointer could be used to store the marked-as-free flag so that
>> no extra memory is needed.
>>   
> 
> Extra memory is needed because only the free list contains
> next pointers.  The chunks that are in use do not.
> 
> What would be possible is to make object_pool::destroy O(1)
> and object_pool::~object_pool O(n log n) by sorting the free list
> only on destruction.
> 

That seems a lot better.

-- 
Michael Marcin