O(1) free in boost::object_pool ?
Hi all, I'm considering using boost::object_pool for my project. Reading the code, I found something that is seemingly suboptimal for my application: destroy in boost::object_pool calls object_pool::free, which calls (eventually) simple_segregated_storage::ordered_free. From the code (and documentation), it seems to me that only simple_segregated_storage::malloc_n uses that ordering. In my application, I don't need malloc_n, so the ordering is redundant. My question is: How can I change the default behavior of object_pool so as to use the simple, unordered O(1) free, which just adds the chunk to the beginning of the list of free chunks? I've (of course) read the documentation, but the only relevant sentences are not very clear: "Memory deallocation may be as simple as adding that chunk to the front of the free list, a O(1) operation. However, more complicated uses of Simple Segregated Storage may require a sorted free list, which makes deallocation O(N)." I.e., since I don't need more complicated uses (I guess that's just malloc_n, please correct me if I'm wrong), I'd like O(1) deallocation. Thank you in advance. Kind regards, -- Domagoj Babic http://www.domagoj.info/ http://www.calysto.org/
AMDG Domagoj Babic wrote:
Hi all,
I'm considering using boost::object_pool for my project. Reading the code, I found something that is seemingly suboptimal for my application:
destroy in boost::object_pool calls object_pool::free, which calls (eventually) simple_segregated_storage::ordered_free. From the code (and documentation), it seems to me that only simple_segregated_storage::malloc_n uses that ordering.
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. In Christ, Steven Watanabe
Steven,
On Tue, Aug 5, 2008 at 3:13 PM, Steven Watanabe
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/
participants (2)
-
Domagoj Babic -
Steven Watanabe